7 ms·
The largest number representable in 64 bits
- masfuerte 8mo ago> The largest number (currently known to be) representable in 64 bits is w218 In my representation the bit pattern 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 stands for the number w218+1. I win!
- tromp 8mo ago> Precisely because the Turing machine model is so ancient and fixed, whatever emergent behavior we find in the Busy Beaver game, there can be no suspicion that we “cheated” by changing the model until we got the results we wanted. Sorry; no winning for cheaters:-(
- cortesoft 8mo agoThis feels like the computer science version of this article: https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
- deleted 8mo ago[deleted]
- pinkmuffinere 8mo ago> You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number—not an infinity—on a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature. Lol, we used to do this with my (extremely nerdy) friends group in college when we 'inducted' new members! I never knew that it was from something, I just thought it was tradition. We had some great entries -- a circle of nines with no beginning and ending, a very good drawing of a wolf, many protest entries, somebody accidentally wrote 1^1^1^1^1^... before realizing their folly, etc. Great times.
- cwillu 8mo agoI get what you're trying to say, but the computer science version of that article is very clearly https://www.scottaaronson.com/papers/bb.pdf https://www.scottaaronson.com/papers/bb.pdf
- Sharlin 8mo ago(Edit: oops, incorrect numbers)
- tromp 8mo agoFollowing BLC8's bytewise encoding convention of [1], w218's binary encoding 0100 0101 1010 1000 0110 0110 0000 0001 0101 1011 1011 0000 0011 1001 1101 0 gets padded with 3 arbitrary least significant bits, say 000, and becomes 45A8_6601_5BB0_39C0 in hexadecimal. [1] https://www.ioccc.org/2012/tromp/ https://www.ioccc.org/2012/tromp/
- dorianmariecom 8mo agowow that entry to the international obfuscated c code contest
- heyitsdaad 8mo agobits == entropy. Everything else is word play.
- IshKebab 8mo agoOnce you allow any format the question is completely meaningless. You can just define 0 to mean any number you want.
- tromp 8mo agoThe post addresses this very issue: > Precisely because the Turing machine model is so ancient and fixed, whatever emergent behavior we find in the Busy Beaver game, there can be no suspicion that we “cheated” by changing the model until we got the results we wanted.”
- IshKebab 8mo agoIt's not really "cheating" - and they did "change the model" by picking the busy beaver game.
- kstrauser 8mo agoWhat's the biggest up-arrow notation number you can spell with 64 bits? https://mathworld.wolfram.com/KnuthUp-ArrowNotation.html https://mathworld.wolfram.com/KnuthUp-ArrowNotation.html
- shhsshs 8mo ago`9↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑9` seems like a reasonable guess (barring encoding cheats/trickery like @masfuerte commented!) Edit: I've misread the above comment and my number is is 64 bytes (significantly more than 64 bits. The largest 64 bit number through my approach would be `9↑↑↑↑↑↑9`, which is significantly smaller.
- lisper 8mo agoI can do you one better and specify that the normal base-2 integer represented by the bits is the number of up-arrows. But as /u/tromp has already pointed out, that is not very interesting.
- tuhgdetzhh 8mo agoIs there any intuition on how big this number is?
- odo1242 8mo agoIf every atom in the universe had a universe inside each proton, there still wouldn’t be enough atoms within all the universes in the protons. In fact you might not make it to four arrows with the above lol
- tromp 8mo agoIn terms of the Fast Growing Hierarchy, it's about f_62(9) or what the article would denote as [62] 9. It's way smaller than Graham's Number, which involves 64 iterations of mapping n to 3 ↑↑↑... {n uparrows) 3, whereas this expression has between 1 and 2 iterations.
- gegtik 8mo agoI can do you one better. I can represent the largest number with a single binary bit.
- aimor 8mo agoI can do it in half a bit
- crazygringo 8mo agoSlow down there mr zip file
- bmacho 8mo agoCan you give a formulation of the problem you are trying to answer?
- tromp 8mo agoTo find the largest number that is computable by a program of at most 64 bits in a non-cheating language; i.e. one that's not geared toward producing large numbers.
- deleted 8mo ago[deleted]
- bmacho 8mo agoDo you have a mathematical formulation, or? Ultimately you seem to pick a random definition of computing and size and then work with that?
- SAI_Peregrinus 8mo ago"Computable" has a well-known standard definition in this context, meaning a computable function[1]. In a given model of computation, a computable function is one for which an algorithm exists which computes the value of the function for every value of its argument. For example, the successor function adds 1 to an input number, and is computable. The halting problem (determine whether a program given in the argument halts) is not computable. [1] https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function
- deleted 8mo ago[deleted]
- deleted 8mo ago[deleted]
- ted_dunning 8mo agoThe article described why the choices were neither random nor particularly arbitrary.
- dmitrygr 8mo agoGiven time, this will output a bigger number, and it is only 48 bits: B0 39 mov al,'9' //load character '9' to AL CD 29 int 29h //print to screen EB FA jmp short -6 //go again
- deleted 8mo ago[deleted]
- jerf 8mo agoThat is not a number, that is infinity. The (implicit) rules of the game require the number to be finite. The reason for this is not that infinity is not obviously "the largest" but that the game of "write infinity in the smallest number of {resource}" is trivial and uninteresting. (At least for any even remotely sensible encoding scheme. Malbolge[1] experts may chime up as to how easy it is to write infinity in that language.) So if you like, pretend we played that game already and we've moved on to this one. "Write infinity" is at best a warmup for this game. (I'm not going to put up another reply for this, but the several people posting "ah, I will cleverly just declare 'the biggest number someone else encodes + 1'" are just posting infinity too. The argument is somewhat longer, but not that difficult.) [1]: https://esolangs.org/wiki/Malbolge https://esolangs.org/wiki/Malbolge
- lazide 8mo agoIt isn’t actually infinite since it can only do a finite number of iterations per second (though it would be large!), and there are only a finite number of seconds in the universe (near as we can tell).
- jerf 8mo agoThis game assumes the computations run to completion on systems that will never run out of resources. No one in this universe will ever compute Ackerman's Number, BB(6), or the final answer given in the post. Computations that never complete are infinite. If you are playing this game and can't produce a number that doesn't fit in this universe you are probably better suited playing something else. That's just table stakes. If it even qualifies as that. "Inscribe every subatomic particle in the universe with a 9 every planck instant of the universe until the heat death of the universe" doesn't even get off the starting line in games like this. Another general comment: It feels like a lot of people are really flailing around here, and need to understand this is a game. It has rules. If you change the rules, you are playing a different game. There is nothing wrong with playing a different game. It is just a different game. The game is not immutably written in the structure of the universe, or a mathematical truth, it is a human choice. And there isn't necessarily a "why" to the rules any more than there's a "why" to why the bishop moves as it does in chess. You can, in fact, change that rule. There are thousands of such variants. It's just that you're playing a different game than chess at that point. If you don't want to play the author's game, then that's fine, but it doesn't change the game itself. And proposing different solutions is equivalent to saying that you can win a chess game by just flipping over the board and yelling "I win". You can do that. Perhaps you've even won some game. But whatever game you just won, it isn't chess.
- dooglius 8mo agoI'm going to agree with the downvoted people and say that this sort of approach is largely meaningless if you allow arbitrary mappings. IMO the most reasonable mathematical formulation given the structure of the integers (in the sense of e.g. Peano) is that to truly represent an integer you have to represent zero and each other representable number has a representable predecessor, i.e. to say you can represent 5 you need 0,1,2,3,4, and 5 to be representable. By a straightforward counting argument, 2^64-1 is then the largest representable number, in other words the obvious thing is right.
- tromp 8mo agoAs I've replies several times before, we don't allow arbitrary mappings. We allow computable mappings but consider only obviously non-cheating languages like Turing machines or lambda calculus or Linux's bc or any existing programming language, that are not geared toward outputting insanely large numbers.
- dooglius 8mo agoI would say that all of those seem both arbitrary and geared toward outputting insanely large numbers (in the sense that the output of any Turing-complete language is). Now if you can make these claims in a mathematical rigorous way (i.e. without relying on a particular mapping like Turing Machines / Lambda Calculus, and without silly "up to a constant factor" cheats) then that would be more interesting.
- tromp 8mo agoTuring Machines and Lambda Calculus can only output insanely large numbers by building those numbers from scratch using their Turing completeness. So while lambda calculus can output something exceeding Loader's Number, it needs well over a thousand bits to do so. What I mean by "geared toward outputting insanely large numbers" is saying: I define a language in which the 1-bit program "0" outputs Loader's Number. That is obviously cheating. There is unfortunately no mathematically rigorous way to define what is cheating, so it seems unreasonable to ask me for that.
- its-summertime 8mo agoIt all goes over my head, but, what does the distribution of values look like? e.g. for unsigned integers its completely flat, for floating point its far too many zeros, and most of the numbers are centered around 0, what do these systems end up looking like?
- tromp 8mo agoLet me go ahead and compute that for all halting lambda terms of length at most 33 bits. The output I got from a modified BB.lhs is (giving the normal form size and the number of terms with that normal form size): 4x208506 6x203638 7x93072 8x202741 9x62039 10x189422 11x101450 12x183896 13x96804 14x167842 15x103631 16x131387 17x100319 18x161560 19x148361 20x180227 21x117866 22x82568 23x90577 24x136315 25x158660 26x207930 27x181334 28x33308 29x33331 30x52430 31x80559 32x140753 33x231169 34x3643 35x1356 36x2817 37x1162 38x2067 39x707 40x1820 41x414 42x1316 43x226 44x1026 45x230 46x663 47x142 48x189 49x150 50x189 51x63 52x102 53x169 54x161 55x24 56x71 57x88 58x48 59x6 60x63 61x11 62x19 63x3 64x18 65x11 66x20 67x10 68x13 69x4 70x6 71x11 72x8 73x12 74x10 75x7 76x9 77x5 78x6 79x5 80x4 81x3 82x9 84x6 85x2 86x3 87x3 88x13 89x3 90x6 92x5 94x3 95x2 96x9 101x1 102x3 103x1 106x2 108x2 109x1 111x3 112x1 113x3 115x1 117x1 118x1 120x2 121x1 122x1 124x1 127x3 128x1 130x2 132x1 133x1 134x3 141x1 142x3 143x2 144x1 146x1 148x1 149x2 158x1 159x1 160x3 161x1 162x7 164x3 166x1 179x1 180x1 187x2 199x1 202x2 203x1 217x1 223x1 225x1 227x4 242x1 247x2 267x1 268x1 269x1 280x1 296x1 298x1 331x1 363x1 394x1 432x1 475x1 484x1 544x1 673x1 708x1 820x1 1364x1 1812x1
- tromp 8mo agoAnother comment asked for the smallest unrepresented number with 64 bit programs. While I cannot give a definite answer there, and one may never be found, here we see that the first unrepresented normal form size for programs up to 33 bits is 83, a number with only 7 bits. Curiously, there are 7 unrepresented numbers even before the first uniquely represented number, 101.
- deleted 8mo ago[deleted]
- o_nate 8mo agoWhatever largest number you can express in your system, I can represent a larger one in only one bit, using the following specification. 0=your largest number 1=your largest number + 1
- deleted 8mo ago[deleted]
- Veserv 8mo agoTo be pedantic, that is a instance of the Berry paradox [1] and no you can not [2] as that would be a violation of Godel's incompleteness theorems. edit: To clarify further, you could create a new formal language L+ that axiomatically defines 0 as "largest number according to L", but that would no longer be L, it would be L+. For any given language with rules at this level of power you could not make that statement without creating a new language with even more powerful rules i.e. each specific set of rules is capped, you need to add more rules to increase that cap, but that is a different language. [1] https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox [2] https://terrytao.wordpress.com/2010/11/02/the-no-self-defeating-object-argument-and-the-vagueness-paradox/ https://terrytao.wordpress.com/2010/11/02/the-no-self-defeat...
- deleted 8mo ago[deleted]
- o_nate 8mo agoIt's not a paradox, because there is nothing logically inconsistent in my definition, unlike the Berry paradox.
- thewakalix 8mo agoTo be more pedantic, yes you can, but only with a meta-language.
- deleted 8mo ago[deleted]
- tromp 8mo agoPlease no more comments to the extent of "i can define a much larger number in only 1 bit". What makes my blog post (hopefully) interesting is that I consider tiny programs for computing huge numbers in non-cheating languages, that are not specifically equipped for doing so.
- hcs 8mo agoSurely you've been on HN long enough to know people just read the headline. Not that it would stop all sniping, but that headline doesn't even include "program" (or "compute").
- tromp 8mo ago> that headline doesn't even include "program" (or "compute"). Neither does Scott's article titled "Who Can Name the Bigger Number?" [1] The title is just a way to invite the reader to find out why the answer isn't simply 2^64-1. [1] https://news.ycombinator.com/item?id=9058986 https://news.ycombinator.com/item?id=9058986
- alecco 8mo agoI think "representable" is misleading. Nice post, though.
- orlp 8mo agoAn interesting follow-up question is, what is the smallest number unable to be encoded in 64 bits of binary lambda calculus?
- tromp 8mo agoBLC can output any literal 60 bit string x as the 64-bit (delimited) program 0010 x, so in that sense it would be some 61 bit number. But if ask about just lambda calculus terms without the binary input, then I think it would be some small number of at most 10 bits. BBλ looks at the normal form size so it cannot even reach numbers 0,1,2,3, and 5.
- petalmind 8mo ago
- dang 8mo agoRelated. Others? The largest number representable in 64 bits - https://news.ycombinator.com/item?id=38414303 https://news.ycombinator.com/item?id=38414303 - Nov 2023 (105 comments) The largest number representable in 64 bits - https://news.ycombinator.com/item?id=35677148 https://news.ycombinator.com/item?id=35677148 - April 2023 (42 comments) (I haven't put 2023 in the current title since the article says it's been significantly expanded since then.)
- abcde666777 8mo agoHi guys, I've come up with a new 64 bit number representation where 0xFFFFFFFF is infinity. Hell you know what every value is just infinity.
- deleted 8mo ago[deleted]
- LoganDark 8mo agoWhich infinity?
- deathanatos 8mo agoAssuming your representation's infinity is size of ℵ₀, I set my representation's 0xFFFF_FFFF to the size of ℵ₁. Similarly, if you choose ℵ_(n), I'm choosing ℵ_(n+1).
- adrian_b 8mo agoUnfortunately, someone else had this idea before you. Arithmetic operations with saturation for integers, either unsigned saturation or signed saturation, have been introduced in personal computers since Intel Pentium MMX (launched in January 1997). A few other CPUs and DSPs had such operations much earlier. "Saturation" means that the highest representable number, e.g. 0xFFFFFFFF, is interpreted as positive infinity and all operations where it appears as an operand are defined accordingly. While whatever CPU you have in your computer or smartphone certainly supports arithmetic with integer infinities, such operations are not available in the high-level programming languages. So in order to use them, you have to use assembly language, inline assembly language in a high-level language or compiler intrinsics that give access to the corresponding machine instructions.
- anthk 8mo agoYou can do that Ackermann number with zenlisp with no internal numbers at all, just lists.
- leodavi 8mo agoTo the author: this work you've published rests on some background knowledge that I'm familiar with but also a lot of background knowledge that's foreign to me. For the parts I was able to follow, I thought the mental gear-turning was enjoyable and interesting! But pursuing these intersections between algebra and computer science is often not so interesting, at least, when I research it myself. Is this something you've learned in university? I ask because I fear that without a formal learning environment, I may never pick up on the more advanced logic halfway through the article. Anyway, cheers to the good work.
- tromp 8mo agoYes, I studied theoretical computer science in University, but I believe the article should be accessible to anyone with a willingness to learn some of the background material. E.g. there are many good introductory texts on the lambda calculus. For a great introduction to the fast growing hierarchy I can recommend David Metzler's Ridiculously Huge Numbers [1] series on youtube. [1] https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3 https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3
- drob518 8mo agoIn a sense, this is just an exercise in (possibly lossy) compression. 64-bit unsigned into are not lossy. 64-bit floating point is lossy but has larger range; it’s only able to encode a small fraction of the numbers in its range (in the limit, the fraction that can be represented is zero since there are infinite real numbers in the range and FP only captures a few).
- xelxebar 8mo agoBusy Beaver gets a lot of love, but the fast growing hierarchy is both constructive and can go way, way, waaaaay beyond current known BB bounds. This makes their size much more viscerally apparent than gesturing vaguely at BB(BB(BB(100))) or whatever, IMHO. David Metzler has this really cool playlist "Ridiculously Huge Numbers" that digs into the details in an accessible way: https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3 https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3 By the end, you're thinking about functions that grow so fast TREE is utterly insignificant. Surprisingly, getting there just needs a small bit of machinery beyond Peano Arithmetic [0]. Then you can ponder doing all that but making a tiny tweak by replacing succesorship with BB. Holy cow... [0]:https://en.wikipedia.org/wiki/Theories_of_iterated_inductive_definitions https://en.wikipedia.org/wiki/Theories_of_iterated_inductive...
- tromp 8mo ago> the fast growing hierarchy is both constructive Only the part for which we have well-defined fundamental sequences is constructive. As far as I know, there is no such system of FS defined up to PTO(Z_2), the Proof Theoretic Ordinal of second order arithmetic, while growth rate at that ordinal can be programmed in under 42 bytes. > waaaaay beyond current known BB bounds I have to disagree here. The Proof Theoretic Ordinal of ZFC + infinitely many inaccessibles can be reached with a program under one kilobyte in size, and that is already extremely high up into the FGH.
- librecell 8mo agoi take so much for granted. every time i’m hacking around with no idea what the program might be, i really should be working on a “thank you, world!” program, to cultivate gratitude and humility all those whose work has made it such that i can say “hellos commonlisp what is the most positive fixnum or word or whatever!” or totally not even think about that let alone complex allocations that seem to happen automatically relative to me they’re cool as f**! i should do well not to forget this. thank you for sharing
- rurban 8mo agoI win: 0x7FF0000000000000 Proof: There is no larger number than +∞. Is +∞ a number? Yes, it is. It is not a real number, it is not a representative number, it's a hyperreal number. (Kreisler 1986)
- nivertech 8mo agoThe correct answer is: the largest number representable in 1 bit is any number (including +infinity and beyond). This article describing various Rube Goldberg machines, there is no need to agree on different ways of representing numbers when one can set a single bit to 1 to represent any desired pre-defined number, or 0 to represent its absence (or the number 0).
- pseudohadamard 8mo agoCame here to say the same thing. In my encoding there are close to 2^64 standard numbers and a few values just below the top end reserved for encoding of hyperoperations. That should cover most requirements, including silly ones.
- nivertech 8mo agoThat's similar to how kdb+/q represent nulls and infinities This is certainly pragmatic, although it breaks the math q type size q literal forms underlying integer value (encoding) ---------------------------------------------------------------------------------------------------------- short (h) 16-bit 0Nh / -0Wh / 0Wh null = -32768; -inf = -32767; +inf = 32767 int (i) 32-bit 0Ni / -0Wi / 0Wi null = -2147483648; -inf = -2147483647; +inf = 2147483647 long (j) 64-bit 0N (or 0Nj) / -0W (or -0Wj) / 0W (or 0Wj) null = -9223372036854775808; -inf = -9223372036854775807; +inf = 9223372036854775807 -- https://code.kx.com/q/basics/datatypes/ https://code.kx.com/q/basics/datatypes/ https://code.kx.com/q/basics/datatypes/#infinities https://code.kx.com/q/basics/datatypes/#infinities
- tromp 8mo agoA Rube Goldberg machine is one intentionally designed to perform a simple task in a comically overcomplicated way, usually consisting of a series of simple unrelated devices. Programs like Melo and w128 are the opposite, performing a hard task with the simplest means, using only a few highly inter-related parts. Your proposed representation is exactly the kind of cheating, to get the results you want, that the article purposely avoids.
- jrm4 8mo agothis 0x6269676773657403 I win :)
- countWSS 8mo agothe article misses log-math and log-log-math which would use 64-bit (d)oubles are exponents in 10^d and 10^(10^d) respectively, which allows far higher range of possible values but somewhat more awkward math operations(addition/subtraction), though much more practical & faster to compute.