News for hackers. Stuff that matters.

A comment on Ask HN: How would you store a number with a 10^6 digits and all numbers .

Re:Ask HN: How would you store a number with a 10^6 digits a... by Petrushka on Thursday December 20, 2012 @09:51AM (#4947948)
Knuth's up-arrow notation and the Ackermann function are both designed to make very large numbers easy to notate, but unfortunately I don't know how difficult it would be to write a program to find an expression for any number in one or the other (I'm sure there are plenty of others on HN who can). Might still be worth looking into however.

http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

http://en.wikipedia.org/wiki/Ackermann_function

[ Parent | on HN ]
Re:Ask HN: How would you store a number with a 10^6 digits a... by strangestchild on Thursday December 20, 2012 @11:07AM (#4948351)
In principle, not every number can be directly expressed as the result of a nontrivial Ackermann function or Knuth operator (just as not every number is a square or a cube) - although there is a section in the Knuth page you linked on how to represent any nonnegative integer as a series of Knuth-type operations.

I would imagine, though, that to represent an arbitrary integer between 0 and n still needs ceil(log_2(n+1)) bits - since you have to distinguish between n+1 choices, whichever notation you use.

[ Parent | on HN ]