Top
Best
New

Posted by tromp 3 hours ago

The largest number representable in 64 bits(tromp.github.io)
51 points | 39 comments
cortesoft 2 hours ago|
This feels like the computer science version of this article: https://www.scottaaronson.com/writings/bignumbers.html
its-summertime 1 hour ago||
It 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?
kstrauser 2 hours ago||
What's the biggest up-arrow notation number you can spell with 64 bits?

https://mathworld.wolfram.com/KnuthUp-ArrowNotation.html

shhsshs 1 hour 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 45 minutes ago||
I 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.
tromp 49 minutes ago||
Please 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.
petalmind 50 seconds ago||
Question: but how many different numbers can you fit in 64 bits using your encoding (sorry I understand the general approach but I have no idea how that fast hierarchy works). I guess it's still 2^64 different numbers?

So basically you have a very low density of representable numbers (2^64 / w218), I wonder how quickly it grows as you use more and more 1-bits, and is there even a correlation between the bit pattern and the corresponding number value?

orlp 55 seconds ago|||
An interesting follow-up question is, what is the smallest number unable to be encoded in 64 bits of binary lambda calculus?
hcs 27 minutes ago|||
Surely 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").
alecco 21 minutes ago||
I think "representable" is misleading. Nice post, though.
heyitsdaad 2 hours ago||
bits == entropy.

Everything else is word play.

bmacho 1 hour ago||
Can you give a formulation of the problem you are trying to answer?
tromp 1 hour ago|
To 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.
bmacho 1 hour ago|||
Do you have a mathematical formulation, or?

Ultimately you seem to pick a random definition of computing and size and then work with that?

dooglius 1 hour ago||
I'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 1 hour ago||
As 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.
geoffschmidt 31 minutes ago|||
It's not "the largest representable number" because you're not representing numbers in any rigorous sense. If I give you 64 bits, you can't tell me what number those bits represent (first, because the rules of the game are ambiguous - what if I give you 8 bytes that are a valid program in two different languages; and second, because even if you made the rules precise, you don't know which bitstrings correspond to programs that halt). And if I give you a number, you can't tell me which 64 bits represent that number or even if the number is representable, and that's true even for small numbers and even if I give you unbounded time.

It seems far more natural to say that you're representing programs rather than numbers. And you're asking, what is the largest finite output you can get from a program in today's programming languages that is 8 bytes or less. Which is also fun and interesting!

tromp 6 minutes ago||
> And you're asking, what is the largest finite output you can get from a program in today's programming languages that is 8 bytes or less.

That's what the post ends up saying, after first discussing conventional representations, and then explicitly widening the representations to programs in (non-cheating) languages.

dooglius 1 hour ago|||
I 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 25 minutes ago||
Turing 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.

firebot 43 minutes ago||
In the spirit of floating points, I'd say posits offer an excellent insight into the trade-offs between precision and accuracy, while being meaningfully representative of a number system rather than some arbitrary functions.
gegtik 1 hour ago||
I can do you one better. I can represent the largest number with a single binary bit.
aimor 1 hour ago|
I can do it in half a bit
crazygringo 1 hour ago||
Slow down there mr zip file
dmitrygr 1 hour ago|
Given 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
jerf 1 hour ago||
That 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

lazide 43 minutes ago||
It 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 37 minutes ago||
This 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.

More comments...