9 ms·
The largest number representable in 64 bits
- tromp 3y agoI originally wrote this article back in March on the googology website, and it received some discussion at https://news.ycombinator.com/item?id=35677148 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.
- tedunangst 3y agoI thought it sounded very familiar, so much so I checked the date twice.
- kstrauser 3y agoI'm going with '9↑↑9', which is 64 bits of UTF-8. (See https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation) https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation)
- flavius29663 3y agoI will go with 0-1 in whatever numerical system you have implemented, assuming only positive numbers.
- 4death4 3y agoThe 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 3y ago[flagged]
- sva_ 3y agoI think that answer is pretty obvious with some basic mathematical training.
- quickthrower2 3y agoThe computer science version is: how much data can you compress to 64 bits? Well you can come up with any payload, create a compression algorithm that returns 0 if it matches that pay load and 1 ++ payload otherwise, then compress that payload. If the “number” is the binary number expressed by the payload that is your maximum number. You can go as high as you like.
- chriswarbo 3y agoThat's why you should include the size of the decompressor (AKA using a self-extracting archive). That's what the Hutter Prize does, for example http://prize.hutter1.net http://prize.hutter1.net The encodings in this article are self-extracting archives; although they don't use a bloated, arbitrary format like e.g. x86_64 Linux ELF executables. Instead they use Binary Lambda Calculus, which has a variety of interpreters (the smallest being 206 bits, written in BLC itself)
- ledauphin 3y ago
- firebot 3y agoYou just need posits! John Gustafson will teach you how. Amazing concept. It would be amazing to see it in more hardware. It's especially good for AI and numerous other applications. Puts floats to shame. Of course this guy starts with integers, which are great, but for floats posits are amazing especially if you can control the bits dedicated to each 'fraction'.
- chriswarbo 3y agoTheir range (excluding infinity) is slightly higher than floats, but still abysmally tiny compared to the BLC encodings used in the article. PS: I still prefer type 1 unums, due to their fallback to intervals :)
- firebot 3y agoNot really. I don't think you've read his papers. The implementations in hardware lack range, but soft posits can expand to ridiculous ranges, and comparing the math, posits are superior(imo, granted, they're more or less similar) to BLC, depending on how they're implemented, of course.
- chriswarbo 3y ago> posits are superior(imo, granted, they're more or less similar) to BLC, depending on how they're implemented, of course I'm very confused that you say posits are "more or less similar" to Binary Lambda Calculus. Posits are an inert data encoding: to interpret a posit as a number, we plug its parts (sign, regime, exponent and fraction) into a simple formula to get a numerical value. Those parts can have varying size (e.g. for soft posits), but the range of results is fundamentally limited by its use of exponentials. In constrast, BLC is a Turing-complete, general-purpose programming language. To interpret a BLC value as a number, we: - Parse its binary representation into lambda abstractions (00), function calls (01) and de-Bruijn-indexed variables (encoded in unary) - Apply the resulting term to the symbol `one-more-than` and the symbol `zero` - Beta-reduce that expression until it reaches a normal form. There is no way, in general, to figure out if this step will finish or get stuck forever: even if will eventually finish, that could take trillions of years or longer. - Read the resulting symbols as a unary number, e.g. `one-more-than (one-more-than zero)` is the number two Posit-style numbers can certainly be represented in BLC, by writing a lambda abstraction that implements the posit formula; but BLC can implement any other computable function, which includes many that grow much faster than the exponentials used in the posit formula (e.g. this has a nice explanation of many truly huge numbers https://www.reddit.com/r/math/comments/283298/how_to_compute_a_very_large_number https://www.reddit.com/r/math/comments/283298/how_to_compute... )
- andrewstuart 3y agoIf you say "well ha ha, you could put a function in that represents more than 64 bits!", then you may as well just say it contains a pointer to the biggest number ever. It's sort of a word game, being smart.
- tzs 3y agoI have no idea offhand how this compares to any of those, but my try would be 0xf090a8802dcf8900, which when interpreted as a UTF-8 encoded C style string is 𐡀-ω, which is the supremum of the set {A₀, A₁, A₂, ...} (Pretend all those 'A's are '𐡀's, because I couldn't figure out how to get a subscript to the right of an 𐡀. The 𐡀 symbol is from a right-to-left alphabet and whenever I'd try to add a subscript it would get moved to the left!). If 𐡀-ω is too cheesy, my try would be 0xf090a880e2828900, which is 𐡀 subscript 9.
- tromp 3y agoCan you explain what these A₀, A₁, A₂, ... are, and how their supremum is a finite number?
- tzs 3y agoOh, I didn't realize we were only doing finite numbers. I had thought we just needed numbers that. The A's are the aleph numbers, just using A instead of 𐡀 because I don't know how to put a subscript on the right side of an 𐡀. They are the cardinalities of well-ordered infinite sets. Aleph-0 is the cardinality of the natural numbers, aleph-1 is the cardinality of the smallest infinite set that is larger than the natural numbers, and it goes on from there.
- tromp 3y agoYeah; I was doing finite numbers. Sorry if that wasn't clear.
- userbinator 3y agoYou know you've been working with computers for a while when reading the title immmediately evokes 18446... in your mind. I was expecting the article to at least mention Kolmogorov complexity, or perhaps the demoscene (there are, surprisingly enough, 8-byte entries there.)
- tromp 3y agoI mention Kolmogorov complexity in the form of "shortest description lengths" at > This property mirrors a notion of optimality for shortest description lengths, where it’s known as the Invariance theorem: with the latter linking to https://en.wikipedia.org/wiki/Kolmogorov_complexity#Invariance_theorem https://en.wikipedia.org/wiki/Kolmogorov_complexity#Invarian...
- lifthrasiir 3y agoI know the purpose of this article, but let me be "that person"---how would you do arithmetic? Or compare them? ;-) The proposed scheme is essentially a very compact version of constructive real number, which has a well-known caveat of not always being comparable to other numbers (because two real numbers can be made arbitrarily close to each other without being equal). It would be interesting to design a constructive real number format that can avoid those pedantries.
- tromp 3y agoThe standard way of comparing these unfathomably huge numbers is by placing them in the Fast Growing Hierarchy. In fact, the article does this with both wCubed and Graham's number to show that the former is much larger.
- lifthrasiir 3y agoI mean, as others pointed out, a number format typically needs much more than just a representation. If there is a bit-size limitation any operation has to round any excess back into the limit. A computational representation based on Turing machines or lambda calculus---again, which is not very different from a constructive real number in usage---do not provide an easy way to do that. That wouldn't have been an issue if there was no bit-size limitation. Okay, let's ignore arithmetics and just allow comparison. As you've said, a common practice is to normalize it into some standard notation with a well-founded ordering. But there is no mechanical way to convert (or even bound) a computational representation to such notation---the general approach is therefore to compute a difference and check its sign. Not really good when it can continue even after the heat death of universe... Frankly speaking, I rather expected to see some improvement over Level-Index number systems [1], but it turns out that this post is completely unrelated to number formats. Otherwise it is good, hence my mild frustration here :S [1] https://www.mrob.com/pub/math/altnum.html#li_sli https://www.mrob.com/pub/math/altnum.html#li_sli
- umvi 3y agoWell if you can redefine what the bits mean you can make any number. "let the value of the 8 bytes be tree(n), where n is the unsigned integer value of the bytes". There, I just blew the article's big number out of the water.
- tromp 3y agoSee my reply to the top comment. Cheating makes it uninteresting.
- kloch 3y ago"18 Billion Trillion" is the approximation I use when referring to the absurdly large "standard" subnet size of /64 in IPv6
- fanf2 3y agoOnly off by a factor of 1000
- vlmutolo 3y agoSo maybe "18 thousand million billion"
- tromp 3y agoNote that 'billion' and 'trillion' themselves have multiple meanings [1] [2], even though most people use only the short scale. [1] https://en.wikipedia.org/wiki/Billion https://en.wikipedia.org/wiki/Billion [2] https://en.wikipedia.org/wiki/Trillion https://en.wikipedia.org/wiki/Trillion
- addaon 3y agoThe 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 3y ago> 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 https://oeis.org/A114852
- IshKebab 3y agoMeaningless question. If you allow arbitrary number formats you can just define 1 to be an arbitrarily large number.
- happytoexplain 3y agoThis is pedantic. Even mathematicians - famous pedants - embrace the subjective concept of "non-trivial" answers.
- robocat 3y agoTo 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 3y ago> 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!
- deleted 3y ago[deleted]
- tromp 3y agoBut the lambda calculus is far from an arbitrary format. It's about the oldest and least arbitrary formalism for computation.
- matja 3y agoIEEE754 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...
- summerlight 3y agoThat doesn't qualify the explicitly stated condition "a largest (finite) representable value".
- loxias 3y ago> But you could use a representation where 0 is 0, and 1 is infinity, saving 63 bits... Reminds me of the hilarious and brilliant: http://tom7.org/nand/ http://tom7.org/nand/
- 1letterunixname 3y agoFloating format 1:1:0:1's 8 possible values: 000: +0 001: +1 ( denormal: (-1)^0 * 0.5 * 2^(-0+1) ) 010: +inf 011: +qnan 100: -0 101: -1 ( denormal: (-1)^1 * 0.5 * 2^(-0+1) ) 110: -inf 111: -qnan === Floating point crib sheet === --- Format --- Sign:exponent:stored explicit mantissa leading bit:mantissa fraction: binary16 = 1:5:0:10 bfloat16 = 1:8:0:7 TensorFloat = 1:8:0:10 fp24 = 1:7:0:16 binary32 = 1:8:0:23 binary64 = 1:11:0:52 8087 = 1:11:1:67 binary128 = 1:15:0:112 --- Interpretation --- leading bit = (exponent != 0) ? 1 : 0 when implicit (not stored) bias = 2^(exponent bits - 1) - 1 value = (-1)^sign * 0 when zero value = (-1)^sign * {{leading bit}}.{{mantissa fraction}}b * 2^(exponent - bias) when normal value = (-1)^sign * 0.{{mantissa fraction}}b * 2^(-bias+1) when denormal --- Classification --- zero = exponent == 0 && mantissa fraction == 0 denormal = exponent == 0 && mantissa fraction != 0 normal = exponent != 0 && exponent != ~0 inf = exponent == ~0 && mantissa fraction == 0 nan = exponent == ~0 && mantissa fraction != 0 snan = nan && msb(mantissa fraction) == 0 qnan = nan && msb(mantissa fraction) == 1 PS: It often takes fewer gates to implement a simpler microcoded microarchitecture than to implement a single hardwired macroarchitecture. Microcoded architectures are theoretically slower than hardwired but this is often not the case in reality because of the costs of gate fanout and extra gates for clock distribution that ameliorate gains of fully specified and decoded in hardware.
- Sharlin 3y agoWell, you can certainly count on HN commenters to deliver the most pedantic, point-missing "ackshually" comments to articles like this!
- feoren 3y agoThe article feels like an excuse to talk about six different tangentially related topics at the same time. That's not a criticism of the article -- it's like listening to someone's wandering train of thought out loud, which is equally as interesting as the thoughts themselves. The article even ends with an ellipsis. I think it's a fine article, but the mental wandering could have gone any other way too. So I'm confused about what point you think people here are missing. There basically wasn't a point to the article, so people are either adding their own thought-wandering musings (totally appropriate, given the style of the post), or they're responding to the title, which is the only time the author really attempts to actually make a clear point. But the title of the article is flawed, and the author's musings do not adequately address the title. That's fine to point out. Nobody is missing any points.
- tromp 3y agoThe point of the article is that lambda calculus makes for a nicer Busy Beaver function that shows its particular strength (of surpassing the most famous huge number) at the standard 64 bit boundary for representing numbers.