how would one automate the process of doing a massive number of multiplicative problems

Discussion in 'Physics & Math' started by !!!!!batman!!!!!, Oct 19, 2014.

1. !!!!!batman!!!!!Registered Member

Messages:
30
i have an interest in taking fifty million different numbers and finding the result of multiplying every possible combination of those numbers together. is there a calculator of sorts where i could just punch in the list of numbers and the computer would do the tedious work of trying every possible variation.

3. PhysBangValued Senior Member

Messages:
2,422
You could try mathematica or maple or learn to program in pretty much any programming language and use the computer you have right now.

5. Russ_WattersNot a Trump supporter...Valued Senior Member

Messages:
5,051
Not sure what you would want to do with the output, but it will take a lot of computer power and a long time to run a program like that. What is the purpose of this?

7. leopoldValued Senior Member

Messages:
17,455
the problem i see is coming up with the random numbers.
a computer can only handle a finite set of numbers without losing precision
a computer would be great for perfecting the algorithm though.
i doubt if you will find a hardwired piece of logic that will perform the OP.

8. rpennerFully WiredValued Senior Member

Messages:
4,833
Is every possible variation, every possible pair? ( About $10^{15}$ multiplications if you exploit the law of complex numbers that says $a \times b \, = \, b \times a$ or twice that if you do not. This can be done in about a day by a modern top-of-the-line machine with hand-written multi-threaded code that exploits the GPU. But if you had those skills, you wouldn't be talking about a calculator. )

The following command line program does exact integer multiplication for any top number and doesn't store the entries so won't run out of memory or diskspace. Here I use 1000 so I can finish in seconds.

Code:
python -c 'top = 1000;exec """\nfor x in xrange(1, 1+top) :\n\tfor y in xrange(x, 1+top) :\n\t\tprint x, u"\u00d7", y, "=", x * y\n"""'
Python is free, works on Windows, Unix and MacOS, is preinstalled on many Linux distributions and is either pre-installed on Macintosh or comes with Xcode, I forget.

If written in a file, the above code is:
Code:
top = 1000
for x in xrange(1, 1+top) :
for y in xrange(x, 1+top) :
print x, u"\u00d7", y, "=", x * y
where u"\u00d7" is the unicode encoding of the common times symbol $\times$.

Approximate timings:
$\begin{array}{c|c} \textrm{top} & \textrm{time (s)} \\ \hline \\ 1000 & 3.5 \\ 2000 & 13.8 \\ 5000 & 86.3 \\ 10000 & 345 \\ 5 \times 10^7 & 8.75 \times 10^9 \end{array}$ ($8.75 \times 10^9 \, \textrm{seconds}$ is about 277 years)
You can cut this down to about 5.5 years if you avoid printing out the multiplication, but really that's just wasting electricity. Skipping printing and writing the whole program in C (a language which is compiled to something close to maximally efficient machine code) could be done in about 41 days -- and less if it is made multi-threaded on a modern multiple-core machine.

Code:
int main(int argc, char **argv) {
long top = 50000000;
long x, y, z;
for(x= 1; x <= top; x ++) {
for(y= x; y <= top; y ++) {
z = x * y;
}
}
}
But if you mean every possible product of every possible subset of the numbers from 1 to 50 million, then that's a task that no computer could do since that's $50000000! \approx 2.34538 \times 10^{363233780}$ combinations which is a number ridiculously larger than all the electrons in the visible universe (about $10^{80}$) times all the picoseconds since the Big Bang (about $10^{29}$).

Last edited: Oct 19, 2014
9. PhysBangValued Senior Member

Messages:
2,422
Best post here ever.

10. rpennerFully WiredValued Senior Member

Messages:
4,833
Because of the general commutative property of multiplication of complex numbers, and knowledge that 1 is the multiplicative identity, every possible distinct subset the numbers 2 through 50 million can be covered in only $2^{49999999} \approx 3.03507246 \times 10^{15051499}$ products which is still impossibly large for a task for a visible universe to do.

11. !!!!!batman!!!!!Registered Member

Messages:
30
to russ_waters the purpose of this has to do with how semi-primes play into modern encryption. to rpenner yes i mean every possible pair. and in terms of the extreme time scale it would take to do this, what would be the feasibility of borrowing a super computer, or making use of distributed computing such as what seti does

12. EnmosValued Senior Member

Messages:
43,184
You would just punch in 50 million numbers? Good luck.

Doing on average 1 number every second, it would take you a little over one and half years. That is if you work day and night, never taking a break, day in day out...
Like I said, good luck... lol

Last edited: Oct 20, 2014
13. rpennerFully WiredValued Senior Member

Messages:
4,833
$50000000 < 2^{26}$ The primes used in RSA public key encryption are generally much larger. Usually the product is 1024 or 4096 bits long, not 52 bits.

There are all sorts of schemes to factor numbers larger than $10^9$.

I take a random large number RandomInteger[2^56] -> 13942537464049003 as input and need less than 1 second to factor it into its three prime factors 19×1087×675085336951.

128709739774844943 is quickly factored into 3×11×13×19×293×160603×335567
NextPrime[RandomInteger[2^30]]*NextPrime[RandomInteger[2^30]] gives me 491565445697169317 which is a challenge 645652681×761346557.

544387009500837613355269 takes 0.2 seconds to factor into 719582936701 × 756531292969 which is not only far beyond where the OP would take us, and far beyond practical storage requirements for a comprehensive multiplication table, but it is also far less than typical numbers used in public key cryptography.

Factoring 123456789123456789123456789123456789123456789123456789123456787 took 4.3 seconds, so I will leave it as an exercise for the reader.

Last edited: Oct 19, 2014
14. !!!!!batman!!!!!Registered Member

Messages:
30
ahh yes rather enlightening, shall keep me busy for a while as i further my learning curve on such subject matter. thanks to all who have posted and to those who may post in the future to further this thread.

15. leopoldValued Senior Member

Messages:
17,455
perfecting the algorithm then implementing it in hardware will decrease execution time.
gate delays would be the limiting factor, on the order of picoseconds.
not printing or storing the results will also decrease execution time.

16. rpennerFully WiredValued Senior Member

Messages:
4,833
Insane person, I contemplated electrons as full-function multipliers and execution times from picoseconds all the way down to Planck times. You can't always get what you want. This is one of those examples.

17. leopoldValued Senior Member

Messages:
17,455
why are you referring to me as an "insane person"?
i would like an explanation before i report your post
fuck it, explain it to the mods.

18. RJBeeryNatural PhilosopherValued Senior Member

Messages:
4,222
Decent thread. Good luck on your journey, Batman. I worked through number theory about 15 or 20 years ago and enjoyed it.