[HN Gopher] The largest number representable in 64 bits
___________________________________________________________________
The largest number representable in 64 bits
Author : tromp
Score : 60 points
Date : 2023-11-25 16:01 UTC (2 days ago)
(HTM) web link (tromp.github.io)
(TXT) w3m dump (tromp.github.io)
| kloch wrote:
| "18 Billion Trillion" is the approximation I use when referring
| to the absurdly large "standard" subnet size of /64 in IPv6
| fanf2 wrote:
| Only off by a factor of 1000
| vlmutolo wrote:
| So maybe "18 thousand million billion"
| tromp wrote:
| Note that 'billion' itself has multiple meanings [1], even
| though most people use only the short scale.
|
| [1] https://en.wikipedia.org/wiki/Billion
| addaon wrote:
| The article discusses different encodings of numbers to give non-
| dense representations of numbers exceeding (2^64)-1. (These
| representations are inherently non-dense by the pigeonhole
| principle.) But I feel like this is missing a key point. A 64-bit
| string that we agree represents only numbers can represent
| 18446744073709551616 different numbers. The choice of what
| numbers are represented is completely up to us. If we want
| certain properties (dense integers) we end up with the highest
| being 18446744073709551615. If we want other properties (nearly
| logarithmic distribution, signedness, and good mapping to
| hardware for arithmetic) we might end up with FP64 with a maximum
| value around 10^308. And if we want no interesting property
| constraints except being dual to a program on a Turing machine,
| we end up with a busy beaver number. But... remember, we can
| choose any 18446744073709551616 values we want to be
| representable. There's no restriction on the interpretation of
| these strings; or, equivalently, the amount of external
| information required to explain the interpretation of these
| strings is unbounded. As a result, we can choose any computable
| number to be encoded by the string 64'b1, or by any other string,
| and exceed any desired bounds.
| tromp wrote:
| > we can choose any computable number to be encoded by the
| string 64'b1
|
| First of all, every finite number is computable by definition.
|
| And second, your encodings will, unlike those in the lambda
| calculus, be completely arbitrary.
|
| PS: in my self-delimiting encoding of the lambda calculus,
| there are only 1058720968043859 < 2^50 closed lambda terms of
| size up to 64 [1].
|
| [1] https://oeis.org/A114852
| addaon wrote:
| > every finite number is computable by definition
|
| Every finite integer is computable. We often represent non-
| integer numbers.
|
| > your encodings will, unlike those in the lambda calculus,
| be completely arbitrary
|
| Well, they /may/ be completely arbitrary. They may not be.
| The key is to choose encodings that are useful for the
| problem domain. Admittedly if the problem domain is "winning
| at the schoolyard game of saying a bigger number," those
| encodings may look arbitrary for most other purposes.
|
| But there's actually an intent to my original comment besides
| being pedantic. The most general way to think of a 64-bit
| numeric representation is as a list of 2^64 numbers, feeding
| into a 2^64:1 mux, with the 64-bit string being the select
| bits of the mux. (Or, equivalently, a 2^64 entry x arbitrary
| width ROM with one number per entry, with the 64-bit string
| being the address input of the ROM. Same thing.) The two
| questions you must answer, then, are (a) which 2^64 numbers
| are most useful in your problem domain; and (b) are there
| hardware optimizations to reduce the (ridiculous) scale of
| the mux/ROM model that are so valuable that you're willing to
| make compromises on which numbers you select?
| Kranar wrote:
| >First of all, every finite number is computable by
| definition.
|
| You likely mean every integer or rational is computable
| (although not by definition). There are finite real numbers
| that are not computable, in fact most of them are not.
| tshaddox wrote:
| It's interesting that you are counting how many lambda
| calculus terms can fit into 64 bits given a particular
| encoding, but you're not making room in the 64 bits for an
| explanation of how your encoding works (let alone how lambda
| calculus works!). Of course, any encoding you used to include
| an "explanation" in the 64 bits would itself require some
| explanation. I guess what I'm getting at is that I'm not sure
| that your approach is any less arbitrary than any other
| approach.
| tromp wrote:
| Before I can understand your comment, could you please add
| an explanation about how the English language works? And
| for whatever language you use to explain that (obviously
| not English), please provide an explanation for that
| language as well... sorry; couldn't resist /s
| pmayrgundter wrote:
| came here and searched for "busy". good job :)
|
| To the sibling comment about arbitrariness, we could use a
| hybrid where we trade off some bits from IEEE FP to introduce
| far reaches and also some precision there.. so like, keep 32
| bits or 54 bits for IEEE compatibility, then switch to
| "extended" ranges for e.g. BB numbers, higher alephs, etc..
|
| There was this one system for calculation with infinities that
| avoided the Hilbert Hotel problem.. can't find it but was
| called smth like Infinioid or some other play on the name.
| Would be neat to bolt those on too :)
|
| Edit: "grossone" is the calculus for infinities.. love this
| work! https://www.theinfinitycomputer.com/
| chriswarbo wrote:
| > To the sibling comment about arbitrariness, we could use a
| hybrid where we trade off some bits from IEEE FP to introduce
| far reaches and also some precision there.. so like, keep 32
| bits or 54 bits for IEEE compatibility, then switch to
| "extended" ranges for e.g. BB numbers, higher alephs, etc.
|
| This sort of trick/hack is the reason why theorems in
| (algorithmic) information theory involve constant factors.
| For example, we can define an image compressor which outputs
| a single `1` when given the Lenna test image[0], and
| otherwise acts exactly like PNG except prefixing its output
| with a `0`. To decode: a `1` decodes to the Lenna image, and
| anything starting with `0` gets decoded as PNG without the
| leading `0`. This gives perfect compression with no loss of
| quality, when tested on that Lenna image ;)
|
| [0] https://en.wikipedia.org/wiki/Lenna
| ithkuil wrote:
| Furthermore this method can be scaled up to cover more and
| more test images, with a modest increase of prefix bits
| teknopaul wrote:
| Came here to say that.
|
| People sometimes mistakenly think that numbers or data in
| computers exist in some meaningful way.
|
| Everything in a computer is a model or record or representation
| that serves a purpose. All bugs and limits are features.
| Sharlin wrote:
| The lower bound on the information content of a string is the
| length of the shortest program that can output the string (and
| halt), this is called its Kolmogoroff complexity. Lambda
| calculus is (one of) the most compact ways to encode programs
| and requires the least context to interpret. Thus it's totally
| fair to say that the largest number encoded in LC in some
| number of bits is much more fundamental and less arbitrary a
| candidate than just randomly deciding that "1" now refers to
| some externally defined large number.
| IshKebab wrote:
| Meaningless question. If you allow arbitrary number formats you
| can just define 1 to be an arbitrarily large number.
| happytoexplain wrote:
| This is pedantic. Even mathematicians - famous pedants -
| embrace the subjective concept of "non-trivial" answers.
| robocat wrote:
| To be pedantic, calling it pedantic is pedantic.
|
| If the number representation is encoded outside the 64 bits
| then you have removed the 64 bit restriction. Of course it is
| hard to calculate how many bits of information are required
| to define the type. But "uint64" is pretty small and just
| requires our current human context (quite a few more bits of
| information) to make sense!
| tshaddox wrote:
| > If the number representation is encoded outside the 64
| bits then you have removed the 64 bit restriction.
|
| The explanation for how to interpret the 64 bit string is
| always outside of the 64 bit string. It's going to be tough
| to compare how big two explanations are since that's going
| to depend a lot on what each person considers to be a
| sufficient explanation.
|
| I'm personally quite rusty on lambda calculus, and from
| glancing at the author's papers about lambda calculus
| encodings I suspect it will take a rather large number of
| bytes to represent an explanation that will make it through
| my thick skull!
| tromp wrote:
| But the lambda calculus is far from an arbitrary format. It's
| about the oldest and least arbitrary formalism for computation.
| LegionMammal978 wrote:
| Perhaps the lambda calculus proper is the oldest, but the
| choices made in encoding the binary lambda calculus are
| somewhat arbitrary: for instance, why use de Bruijn indices
| for symbols, instead of some other scheme, such as the index
| of the lambda in the string? And why encode de Bruijn indices
| in unary, and not in any other 1-prefixed self-delimiting
| format? And why use a self-delimiting format in the first
| place? Obviously, these choices are quite reasonable and make
| for a simple implementation, but they're totally distinct
| from the formalism that Church first described. (And for that
| matter, Church originally only used lambda notation in the
| context of an overarching logical formalism that later got
| struck down.)
|
| Indeed, if we look at Church's paper, we'd find that the term
| is 80 symbols written fully, {l _t_ [{{{{{ _t_ }( _t_ )}(l
| _h_ [l _f_ [l _n_ [{{{ _n_ }( _h_ )}( _f_ )}( _n_ )]]])}( _t_
| )}( _t_ )}( _t_ )]}(l _f_ [l _x_ [{ _f_ }({ _f_ }( _x_ ))]]),
| or 44 symbols when abbreviated, {l _t_ _t_ ( _t_ , (l _h_ l
| _f_ l _n_ _n_ ( _h_ , _f_ , _n_ )), _t_ , _t_ , _t_ )}(l _f_
| l _x_ _f_ ( _f_ ( _x_ ))), which aren't too impressive given
| the alphabet of 11 or 12 symbols.
| matja wrote:
| IEEE754 64-bit representation already has infinity:
| uint64_t x = 0x7ff0000000000000ULL; printf("%f\n",
| *(double *)&x);
|
| output: inf
|
| But you could use a representation where 0 is 0, and 1 is
| infinity, saving 63 bits...
| tromp wrote:
| I don't consider infinity to be a number though. Especially not
| in a largest number contest.
| lowq wrote:
| Let 0 correspond to zero, and 1 corresponded to Rayo's
| number. Crisis averted!
| danbruc wrote:
| Let all values encode Rayo's number. 64 bits saved!
| tromp wrote:
| I find Loader's number [1] more interesting, as it is
| actually computable, yet far far larger than other famous
| computable numbers, like Friedman's TREE(3) or SCG(3). I'm
| looking forward to one day programming it in the lambda
| calculus, and seeing how much smaller than the existing
| ~500 bytes of C-code it can be.
|
| [1] https://www.youtube.com/watch?v=q6Etl4oGL4U&list=PL-R4p
| -BRL8...
| toxik wrote:
| Fair, but also an uninteresting answer.
| pphysch wrote:
| It's about as interesting as the other answers proposed in
| TFA, and it gets to the meat of it: they are all just
| representations invented by people, and there's nothing
| stopping us from inventing our own representations that fit
| into 64 bits (or 1 bit).
| toxik wrote:
| No, it doesn't. The question is "what is the largest non-
| trivial number you can represent with some constraint on
| size of its expression". It's a really old question, and
| saying "infinity" as an answer misses the point. Saying you
| can invent an arbitrary number system also misses the point
| by simply not answering. If you need to spend a bunch of
| bytes explaining your new system, did you really use 8
| bytes?
|
| It just feels really bad faith.
| pphysch wrote:
| What is "really bad faith" about saying "An ON bit
| indicates the value 'googolplex'?"
|
| Computing is fundamentally about decoding bit strings as
| different arbitrary representations that are meaningful
| to humans.
| tromp wrote:
| Even the word "googolplex" is quite a bit longer than the
| lambda calculus program in question...
| 8note wrote:
| The actual bit is just 1 though, the word "googolplex" is
| in the accompanying documents for interpreting the bit.
|
| The course on reading and using lambda calculus is
| similarly longer than than the actual lambda calculus
| expression
| dumbo-octopus wrote:
| Not really. The specialness of TFA's constructions is that
| the interpreter does not need to have any knowledge of the
| large numbers a priori.
| 8note wrote:
| Alternative contructions don't have to either - eg. "The
| bit 1 represents running the algorithm from TFA"
| summerlight wrote:
| That doesn't qualify the explicitly stated condition "a largest
| (finite) representable value".
| Sharlin wrote:
| Well, you can certainly count on HN commenters to deliver the
| most pedantic, point-missing "ackshually" comments to articles
| like this!
| tromp wrote:
| I originally wrote this article back in March on the googology
| website, and it received some discussion at
| https://news.ycombinator.com/item?id=35677148
|
| Since some commenters pointed out how awfully spammy that website
| is (which I had failed to notice due to my browser's adblockers),
| I recently decided to slightly rewrite and expand the article to
| host it on my newly formed personal blog.
| kstrauser wrote:
| I'm going with '9||9', which is 64 bits of UTF-8. (See
| https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation)
| Pharaoh2 wrote:
| The article's result is large than that
| kstrauser wrote:
| Awww, rats. I managed to miss seeing Knuth already mentioned
| in there. :facepalm:
| tromp wrote:
| This is much less than the Ackerman value ack(9,9) that is
| discussed in the article, which equals 2|||||||12 - 3.
| flavius29663 wrote:
| I will go with 0-1 in whatever numerical system you have
| implemented, assuming only positive numbers.
| 4death4 wrote:
| The problem, as stated, provably has no answer. Assume such a
| number exists. Call it n. Now define a new 64-bit numbering
| scheme such that each number x is interpreted as n+x. n+x > n,
| which invalidates the hypothesis. There needs to be more
| constraints for this to be interesting. Like largest number
| representable where the representation is closed under addition
| and multiplication, or something like that.
| cyanydeez wrote:
| r u Godel?
___________________________________________________________________
(page generated 2023-11-27 23:00 UTC)