Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The largest number representable in 64 bits

tromp.github.io

Post reply on HN
Print view View original

81–90 of 98 posts

Re: The largest number representable in 64 bits

#81

Post by tromp »

leodavi wrote: post #68

To 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'…

Yes, 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

Re: The largest number representable in 64 bits

#82

Post by tromp »

omoikane wrote: post #76
tromp wrote: post #32

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.

A better title might have been "fastest growing function with 64bit arguments". The main value of this article is really the various functions that take larger strides to cover a finite range that's significantly larger than 2^64-1.

If it were about coding fast growing functions, then it would have had to mention the incredible 47-bit lambda calculus term λn. n n (λe λx. x e x) (λm. m (λe. m e m)) that achieves f_ε₀ growth. But it expects its argument to be a so-called state numeral n, rather than a Church numeral, and even state numeral 2, which is \e\f\x.f e (\e.f e x) is already 32 bits long, making the application take 2+47+32=81 bits, more than the required 64.

Re: The largest number representable in 64 bits

#83

Post by tromp »

tuhgdetzhh wrote: post #52
shhsshs wrote: post #19

Earlier quoted context omitted.

`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.

Is there any intuition on how big this number is?

In 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.

Re: The largest number representable in 64 bits

#84

Post by nivertech »

The 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).

Re: The largest number representable in 64 bits

#85

Post by tromp »

xelxebar wrote: post #71

Busy 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=PL3…

> 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.

Re: The largest number representable in 64 bits

#86

Post by IshKebab »

tromp wrote: post #10
IshKebab wrote: post #6

Once you allow any format the question is completely meaningless. You can just define 0 to mean any number you want.

The 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.”

It's not really "cheating" - and they did "change the model" by picking the busy beaver game.

Re: The largest number representable in 64 bits

#87

Post by adrian_b »

abcde666777 wrote: post #59

Hi 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.

Unfortunately, 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.

Re: The largest number representable in 64 bits

#88

Post by pseudohadamard »

nivertech wrote: post #84

The 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).

Came 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.

Re: The largest number representable in 64 bits

#89

Post by nivertech »

pseudohadamard wrote: post #88
nivertech wrote: post #84

The 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).

Came 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.

That'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/#infinities

Re: The largest number representable in 64 bits

#90

Post by [deleted] »

SAI_Peregrinus wrote: post #54
bmacho wrote: post #18

Earlier quoted context omitted.

Do you have a mathematical formulation, or? Ultimately you seem to pick a random definition of computing and size and then work with that?

"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…

[deleted]
Post reply on HN