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

Easy algorithms to produce big numbers

  1. Feb 8, 2012 #1
    How can a novice simply generate a large number > 1010 in a few steps?
  2. jcsd
  3. Feb 9, 2012 #2
    By writing down a '1', followed by nine '0's, followed by a '1' ?

    Not sure of what you really want, though.
  4. Feb 9, 2012 #3
    There are simple means of generating a series which, by the third step say, creates a huge number, on the order of greater than 10100. In other words, how are the significant, very big numbers created, other than pasting together some smaller numbers?

    I recall one of the best such algorithms was created by a Turing-like machine. Within three steps it easily reached over 10100.
  5. Feb 9, 2012 #4
    9^9^9 has 369'693'100 decimal digits
  6. Feb 9, 2012 #5
    It's probably not a coincidence that string-processing machines are able to make exponentially bigger numbers; adding a digit to a string is like incrementing its order of magnitude on each step... which is like adding one to its logarithm, thus multiplying by a constant on each step... thus exponentiation. (... Now imagine a machine doubling the number of digits on each step.)
  7. Feb 9, 2012 #6
    f(x) = 1010 + 1

    That's how you would do it mathematically. You have a function that outputs a number that's literally greater than 1010 for any input.

    Can you explain what you mean by "generate?" For example if you are using a computer, you would perhaps first install a bignum package -- specialized software to handle arbitrary-sized numbers. Then you could just write a loop to count up to your large number by 1; or you could just take your large number and store it in memory.

    It's not clear to me what else you might be asking.
  8. Feb 9, 2012 #7
    As I indicated, f(x) = 10100 does it in one step.

    But perhaps you are thinking of the Busy Beaver function. or the Ackermann function.



    Those are functions used in computer science that grow very quickly. Ah you must be talking about functions that GROW very quickly, not just functions that output large numbers. Got it!

    You see, f(x) = 10100 doesn't grow at all. So it's big, but it doesn't get any bigger.

    Check out the Wiki links above, I think that's what you're talking about.
  9. Feb 9, 2012 #8
    You got it! Noncomputable growth. Busy beaver.

    Thanks SteveL27.
  10. Feb 9, 2012 #9
    [itex]googleplex^{googleplex^{...}}[/itex], where there are a googleplex

    number of tiers is something I was thinking of recently.
  11. Feb 10, 2012 #10
    Does this make sense:

    What is the most "efficient" algorithm for generating a largest possible (computable) number?
  12. Feb 10, 2012 #11


    Staff: Mentor

    In math, there's some large number generators like knuth's arrows, bowers operators, Graham's numbers and friedmans TREE sequence. Each of these is dwarfed by the one following for generating large numbers.
  13. Feb 13, 2012 #12


    User Avatar
    Science Advisor

    oh my goodness TREE(3) is huge!
  14. Mar 5, 2012 #13
    There's an interesting sequence that creates tons of large numbers before reaching zero:

    -Take an arbitrary number N and express it in base-2 hereditary notation (that all coefficients are less than or equal to 2, eg 35= 25+21+1 however the exponent 5 is greater than 2, we will express that part as 22+1 giving instead 222+1+21+1)

    -Then take all 2's and replace them with 3's and subtract 1 from the result, expressing this in base-3 hereditary notation
    -Then take all Ns and replace them with N+1s and subtract 1, expressing them in base-N+1 hereditary notation (3 to 4, 4 to 5, 5 to 6...)

    Eventually you'll reach one but you'll hit enormous numbers on the way.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook