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

81–90 of 115 posts

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

#81

Post by thesz »

Dylan16807 wrote: post #50
sdenton4 wrote: post #36

Earlier quoted context omitted.

Concatenating arbitrary 32 bit ints covers all possible 64 bit ints. So the space of all pairs of 32 bit ints is in bijection with 64 bit ints. Commutativity introduces a relation on pairs of 32 bit ints (a,b) ~ (b,a), which accounts for one bit of information. Thus, at most 50% of 64bit ints show up as products of 32 bit ints.

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 = (223)3 = 2(233).

One of ~22 (ln(2^32)) perfect squares will be a square of perfect prime. Most won't.

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

#82

Post by thehappypm »

danbruc wrote: post #6
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…

All the primes above 2^32 are out, but that accounts for only two point something percent.

The simple explanation is just that lot of ways that numbers can multiply to produce the same product

Like an odd number x times an even number y, x* y produces the same product as x* 2 and y/2

Same for a multiple of 3 c and and a non multiple of 3 d, c * d = c/3 * d*3

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

#83

Post by jetsamflotsam »

ot wrote: post #33
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…

Yeah the number sounds a lot less impressive if you say that you only get 2^61.44 integers out of 2^64. In other words, a 4% entropy loss. Information quantities are more meaningfully expressed in number of bits.

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.

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

#84

Post by _alternator_ »

bonzini wrote: post #69
_alternator_ wrote: post #65

> You might be able to come up with a more efficient algorithm. Challenge accepted. Suppose we want to know the answer to 3 decimal places (so we'd match the headline). And suppose I allow my algorithm to be wrong one in a thousand times ("probably approximately correct"). Then sample some constant number C of random 64 bit integers. Run the following algorithm which separates each random sample into one of three cla…

Even if you have 32-bit factors the number may not be the product of two 32-bit numbers. For example 2^62*3 cannot be split as either (2^32, 2^30*3) or (2^31, 2^31*3). In both cases one factor does not fit in 32 bits.

Ah, yes, this is true, but it's not really a counterexample, since this would show up in the N or U bucket. But I think the issue is that my sketch algorithm is, well, pretty sketchy.

Working on coding it up... it converges to 17±0.5%for N=64 bits in a javascript implementation relatively quickly, but for N=96, it really slows down as Pollard's Rho starts with large factors. This means my fast-and-loose assumption that "a constant number of iterations of Pollard Rho would work" isn't actually true!

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

#85

Post by danbruc »

thehappypm wrote: post #82
danbruc wrote: post #6

Earlier quoted context omitted.

All the primes above 2^32 are out, but that accounts for only two point something percent.

The simple explanation is just that lot of ways that numbers can multiply to produce the same product Like an odd number x times an even number y, x* y produces the same product as x* 2 and y/2 Same for a multiple of 3 c and and a non multiple of 3 d, c * d = c/3 * d*3

This is just looking at it from a different perspective. Both, one 64 bit integer and the product of two 32 bit integers represent a number up to 2^64 with 64 bits. But while all 64 bit integers are unique, there are, as you say, several representation for some numbers as the product of two 32 bit integers and therefore it is impossible to represent all 64 bit integers. Commutativity alone costs you about 50 percent of all numbers in the range as x * y and y * x represent the same 64 bit number but with two different representation as a product of two 32 bit numbers, at least if x and y are different. But this tells you nothing about the numbers that you can not represent, only that they must exist. I was looking at it from this other perspective, which numbers are not representable as a product and why.

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

#87

Post by danbruc »

AnotherGoodName wrote: post #86

The mathematical term for this is the probability of a number being b-smooth. Here ‘b’ is 2^32

Related but not strong enough. 17 x 17 x 17 = 4,913 is 2^8-smooth - no prime factors larger than 2^8 - and it is less than 2^16, but 17 x 17 = 289 does not fit into a byte. Smoothness is required but not sufficient for a product representation to exist.

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

#88

Post by saghm »

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.

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

#89

Post by _alternator_ »

_alternator_ wrote: post #84
bonzini wrote: post #69

Earlier quoted context omitted.

Even if you have 32-bit factors the number may not be the product of two 32-bit numbers. For example 2^62*3 cannot be split as either (2^32, 2^30*3) or (2^31, 2^31*3). In both cases one factor does not fit in 32 bits.

Ah, yes, this is true, but it's not really a counterexample, since this would show up in the N or U bucket. But I think the issue is that my sketch algorithm is, well, pretty sketchy. Working on coding it up... it converges to 17±0.5%for N=64 bits in a javascript implementation relatively quickly, but for N=96, it really slows down as Pollard's Rho starts with large factors. This means my fast-and-loose assumption th…

Ok, chatting with Claude and I found a way to salvage the approach! (Also, it's apparently in the paper that's referenced in the post, kinda cool that my sketchy algorithm got halfway to the published result).

Basically, replace the Pollard Rho partial factorization with a method of Kalai [1] for generating random numbers _together with their prime factors_.

I'm able to run this at about 30 samples per second at 160bits, giving an estimate of ~14.1% of 160-bit numbers factoring into two 80-bit numbers.

[1]: https://link.springer.com/article/10.1007/s00145-003-0051-5

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

#90

Post by kens »

jetsamflotsam wrote: post #83
ot wrote: post #33

Earlier quoted context omitted.

Yeah the number sounds a lot less impressive if you say that you only get 2^61.44 integers out of 2^64. In other words, a 4% entropy loss. Information quantities are more meaningfully expressed in number of bits.

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://ethw.org/w/images/2/2f/Intel_8086_family_users_numer...

Post reply on HN