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.
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. PhysBang Valued 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.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Russ_Watters Not 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?
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. leopold Valued 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. rpenner Fully Wired Valued 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. PhysBang Valued Senior Member

    Messages:
    2,422
    Best post here ever.
     
  10. rpenner Fully Wired Valued 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. Enmos Valued 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. rpenner Fully Wired Valued 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\).

    Take this page (Java required): http://www.alpertron.com.ar/ECM.HTM Another site is Wolfram Alpha.

    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. leopold Valued 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. rpenner Fully Wired Valued 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. leopold Valued 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. RJBeery Natural Philosopher Valued 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.
     

Share This Page