Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How do computers and websites work out huge numbers?

  1. Feb 11, 2016 #1
    I was just wondering when you type some numbers into your computers calculator or into a website, how does it find the answer? Obviously for very small numbers like 4x12 it could do this just by addition. What about for massive calculations? For example 102!

    I typed this into Wolfram Alpha and it gave the answer
    961446671503512660926865558697259548455355905059659464369444714048531715130254590603314961882364451384985595980362059157503710042865532928000000000000000000000000

    Which is the exact answer... How does to calculate what 88! * 89 is in the sequence? Then 89! * 90 etc. Each of these alone is an astronomically large number.

    Thanks.
     
  2. jcsd
  3. Feb 11, 2016 #2

    jedishrfu

    Staff: Mentor

  4. Feb 11, 2016 #3
    But ultimately the code is read by the CPU which then does the calculation correct? Which is all 1's and 0's so that is why I'm not sure how it can find the answer to 102! in literally 1 second.
     
  5. Feb 11, 2016 #4
  6. Feb 11, 2016 #5

    phinds

    User Avatar
    Gold Member
    2016 Award

    You are thinking in human terms. For doing simple calculations like this, computers are, as rootone pointed out, MANY orders of magnitude faster than humans. So much so that it is really outside our realm of direct comprehension.
     
  7. Feb 11, 2016 #6
    So are you saying that a computer can calculate 102! in 1 second just because it's fast? Even if a computer could count 1trillion numbers per second it would still take an absurd amount of time to calculate 102!
     
  8. Feb 11, 2016 #7

    phinds

    User Avatar
    Gold Member
    2016 Award

    Any yet you yourself have observed it happening. So you don't believe your eyes?

    Computing 102! hardly takes anything like a trillion operations. I doubt it would even come close to a billion, much less a trillion.
     
  9. Feb 11, 2016 #8

    rcgldr

    User Avatar
    Homework Helper

    The big number algorithms are highly optimized. This web site includes source code and somewhat of an explanation of how this is done.

    http://www.apfloat.org/ntt.html
     
  10. Feb 12, 2016 #9

    Mark44

    Staff: Mentor

    In fact, all it takes is 100 multiplications. Of course some of these multiplications are too large to be done in registers of the CPU, but it takes a lot less than a billion operations to compute the product.
     
  11. Feb 12, 2016 #10
    They probably just look up factorials in a table.
     
    Last edited: Feb 12, 2016
  12. Feb 12, 2016 #11

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Wow! That is a fascinating article you referenced. The math is much more sophisticated than the "brute-force" approach I had imagined. I wish I could understand more of it.
     
  13. Feb 12, 2016 #12

    jedishrfu

    Staff: Mentor

    I contemplated at one time to implement the Trachtenberg method of multiplication because it could handle arbitrarily large numbers but never had a real need for it. It was something

    I first learned about the Trachtenberg system in grade school as part of my imaginations of becoming a great math prodigy like my hero Albert Einstein. It would have curious though to see how fast the system would fare against the prevailing libraries of today.

    https://en.wikipedia.org/wiki/Trachtenberg_system
     
  14. Feb 12, 2016 #13
    I guess I just didn't think a computer's cpu was capable of multiplying gigantic numbers in milliseconds. So a cpu will do something like the following.

    1x2 = 2
    1x2x3 = 6
    1x2x3x4 = 24
    1x2x3x4x5 = 120

    but between each of this calculations the cpu must calcua
    I thought this bu then you can type in any arbitrary number like 87.53! and it will know it so I doubt it's listed every factorial in a table.
     
  15. Feb 12, 2016 #14
  16. Feb 13, 2016 #15
    102! is nothing. Using Java's BigInteger my computer can calculate the exact solution for 100000! (a number with 456574 digits) in 3 seconds, if I use only one single CPU core that is.
     
  17. Feb 13, 2016 #16
    Sure, but I want to know how they compute those solutions.
     
  18. Feb 13, 2016 #17

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

  19. Feb 14, 2016 #18
    For a computer, first the numbers are encoded in binary. So 102 is encoded as 1100110. The computation 101 x 102 becomes 1100101 x 1100110. This will be done in the arithmetic logic unit (ALU) of the computer in a single step. At the basic level, you can multiply two bits with an AND gate: 1x1=1, 1x0=0, 0x1=0, 0x0=0. Let's say that the ALU is wired for 32 bit arithmetic - so it will have a 32x32 grid of AND gates. Conductors along rows will handle one operand and separate conductors along columns will hold the other operand. Where the conductors cross, there will be and AND gate. Extending to 32 bits, our rows will be 00000000000000000000000001100101 and our columns will be 00000000000000000000000001100101. Next the output of the AND gates will be added along the diagonals - 1+1=0, with one to carry. It actually takes about 5 gates to add three 1 bit value and put out a sum and a carry - and at you have one of these adders at every AND gate, one of the three inputs for the AND gate result, one for the sum of previous AND gate sums, and one for the carry bit from and adjacent adder.

    The result is a 64-bit product - calculated in a matter of nanoseconds. This is repeated for 100 x 99 x 98 x ... When you can't store the number in 32-bit, the software starts using multiple 32-bit words, multiple 32x32 bit multiplies, and adds and handles carries at the word level in much the same way that the hardware did at the bit level. The final answer is then encoded to decimal (by repeated division by 10, and capturing the remainder) and presented on the display or GUI.
     
  20. Feb 16, 2016 #19
    Now that's the kind of answer I was looking for. Cheers!
     
  21. Feb 16, 2016 #20
    Arbitrarily large numbers are not stored in IEEE integer format, they are stored in structure, which are specific to the library that you are using. Here is an example

    Code (C):
    mpz_t p;  /* Notice: Not a built in C[++] type, comes from GNU */
    mpz_init_set_ui(p,1); /* p = 1 */
    for (i=1; i <= n ; ++i){
         mpz_mul_ui(p,p,i); /* p = p * i */
    }
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How do computers and websites work out huge numbers?
  1. How a computer works (Replies: 5)

  2. How do programs work? (Replies: 5)

Loading...