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

Only 17% of all 64-bit Integers are products of two 32-bit integers

lemire.me

Post reply on HN
Print view View original

91–100 of 115 posts

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#91

Post by andrewflnr »

saghm wrote: post #88

The way the headline is phrased doesn't really surprise me much. There aren't twice as many 64-bit integers than 32-bit ones; there are twice as many 33-bit integers as 32 bit ones, and there are 2^32 times as many 64-bit ones than 32-bit ones. It's like asking how many numbers between 1-64 you can get by multiplying numbers between 1-8; I think it's readily apparent that a pretty large portion are missed.

But you're using two 32-bit numbers, which have the same total bits as a 64-bit number. There are equally many 32-bit x 32-bit pairs as there are 64-bit numbers.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#92

Post by Dylan16807 »

thaumasiotes wrote: post #24
Dylan16807 wrote: post #3

> I find it interesting to consider that if you pick a value at random, it will usually fail! That is, most 64-bit integers cannot be written as the product of two 32-bit integers. While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" alr…

> While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" already It's much worse than that. It's difficult for a 64-bit product to have the high bit set if the multiplicands are both no larger than 32 bits.

I wouldn't say difficult. To set the high bit, the geometric mean of the two multiplicands has to be at least 3 billion. 32 bit numbers go up to 4.3 billion so that's quite common.

If I did the correct integral (the area inside the unit square above y=.5/x), then 15.34% of products should have the high bit set. That's much less than half but it's still happening constantly.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#93

Post by Dylan16807 »

HarHarVeryFunny wrote: post #68
orlp wrote: post #58

Earlier quoted context omitted.

The input space is 32 + 32 = 64 bits. The output space is 64 bits. So the best you can do is an 1-to-1 mapping. However, since a * b = b * a, our input space has a lot of duplicate outputs. So from this alone you can conclude roughly half of the output space must be uncovered by any input pair, simply because there aren't enough input pairs.

OK - thanks. I must have misunderstood what the other poster was saying, since I thought they were objecting to the "most" characterization.

I wasn't saying it's wrong, I was saying that "most" is so easy to reach that it's a trivial and rather boring threshold.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#94

Post by themafia »

Sure. You're just experiencing aliasing though. Are you not?

> There are 3,215,709,724,700,470,902 64-bit (unsigned) integers that can be written as a product of two 32-bit integers.

That can be written as a product of one or more pairs of 32 bit integers. So this is just not a bijective map.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#95

Post by shiandow »

nyeah wrote: post #43
thaumasiotes wrote: post #25

Earlier quoted context omitted.

If you're allowed to multiply as many 32-bit numbers as you want, the only numbers you won't be able to achieve by so doing are those with any prime factor larger than 2^32. This is more than just the prime numbers. For example, a 41-bit prime can be multiplied by 16 and it will still fit into 64 bits.

What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.

If you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#96

Post by Timwi »

tobz1000 wrote: post #48

> the proportion of all 2n-bit values that can be generated by the product of two n-bit values goes to zero as n becomes large. This means that if you have, say, 10000000-bit integers multiplying 10000000-bit integers, you’d expect relatively few 100000000000000-bit integers to be produced. That should be "relatively few 20000000-bit integers", right?

It looks like that has been fixed in the article. Good catch!

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#97

Post by TomatoCo »

kens wrote: post #90
jetsamflotsam wrote: post #83

Earlier quoted context omitted.

Exactly. Being precise about logarithmic vs linear utilizations is key here. I tried making a similar point about the inefficiency of IEEE-754 redundant NaN encodings here: https://arxiv.org/pdf/2508.05621 Having ~a quadrillion redundant bitstrings all mapping to NaN sounds pretty bad, but logarithmic/information utilization-wise, this is actually not too bad.

I've been looking at the 8087 NaN circuitry lately. Having 2^53 (or whatever) values for NaN was supposedly a feature: "the large number of NAN values that are available, provide the sophisticated programmer with a tool that can be applied to a variety of special situations." For example, the different NaN values could hold debugging information to track down errors. See "8087 Numeric Data Processor" page S-74: https…

You'll see some scripting languages (ab)use this. Where the native "number" type is a 64 bit float and only one NaN bit pattern is a real NaN. The others smuggle a pointer to an object in the lower bits. This way you don't spend any memory overhead indicating if a given variable contains a primitive or an object.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#98

Post by saghm »

andrewflnr wrote: post #91
saghm wrote: post #88

The way the headline is phrased doesn't really surprise me much. There aren't twice as many 64-bit integers than 32-bit ones; there are twice as many 33-bit integers as 32 bit ones, and there are 2^32 times as many 64-bit ones than 32-bit ones. It's like asking how many numbers between 1-64 you can get by multiplying numbers between 1-8; I think it's readily apparent that a pretty large portion are missed.

But you're using two 32-bit numbers, which have the same total bits as a 64-bit number. There are equally many 32-bit x 32-bit pairs as there are 64-bit numbers.

And there are as many pairs of numbers between 1-8 and numbers from 1-64, but it's still pretty apparent that most of them are not represented in the set of products.

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#99

Post by mkl »

thesz wrote: post #81
Dylan16807 wrote: post #50

Earlier quoted context omitted.

Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.

Some of them, with notable exception of perfect squares of primes, can be expressed by products of different combinations of factors. E.g., 6^2 = (2 2 3) 3 = 2 (2 3 3). One of ~22 (ln(2^32)) perfect squares will be a square of perfect prime. Most won't.

Decoding this so it's readable: 6^2 = (2*2*3)*3 = 2*(2*3*3).

(You can escape * with \: \*)

Re: Only 17% of all 64-bit Integers are products of two 32-bit integers

#100

Post by svat »

Dylan16807 wrote: post #3

> I find it interesting to consider that if you pick a value at random, it will usually fail! That is, most 64-bit integers cannot be written as the product of two 32-bit integers. While I find the 17% number interesting to think about, "most" is far less interesting. Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63. That's a hair's breadth away from "most" alr…

The word “most” is indeed not very surprising if taken to mean >50% (as you do), but the surprising fact (admittedly not relevant for 2^64 in the quoted sentence) is that “most” can be replaced with “almost all” in the technical sense meaning “tending to 1” i.e. “1 - o(1)”, i.e. “eventually greater than 1-epsilon for any epsilon”.

Here's the multiplication table up to 9 (so for n=10 in place of n=2^64), and it already contains only 37 distinct products among its 100 entries:

     × |  0  1  2  3  4  5  6  7  8  9
    ---+------------------------------
     0 |  0  0  0  0  0  0  0  0  0  0
     1 |  0  1  2  3  4  5  6  7  8  9
     2 |  0  2  4  6  8 10 12 14 16 18
     3 |  0  3  6  9 12 15 18 21 24 27
     4 |  0  4  8 12 16 20 24 28 32 36
     5 |  0  5 10 15 20 25 30 35 40 45
     6 |  0  6 12 18 24 30 36 42 48 54
     7 |  0  7 14 21 28 35 42 49 56 63
     8 |  0  8 16 24 32 40 48 56 64 72
     9 |  0  9 18 27 36 45 54 63 72 81
That is, in decimal, only 37% of (up to) two-digit numbers can be written as products of two one-digit numbers. This fraction, which drops to 28% at n=100, only drops to 17% at n=2^64 (per the article). So it decreases VERY slowly, and it's nontrivial that it actually goes to 0.
Post reply on HN