alt Hacker News> 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" already, and considering even a tiny amount of overlapping results gets you there.
What gets interesting is actually trying to quantify the overlapping results.
Replies
All the primes above 2^32 are out, but that accounts for only two point something percent.
> Multiplication doesn't care about order so you're instantly cutting 2^64 possibilities down to about 2^63.
Not sure I understand.
Adding two 32 bit integers takes you to 33 bit integers. (1111 + 1111 = 11110).
Addition doesn't care about order, so you're instantly cutting 2^33 possibilities down to 2^32. Or so is your argument. But in reality you can reach nearly all of those 2^33 numbers.
Why does order matter?
Whether a 64-bit number can be written as the product of two 32-bit ones depends only on the prime factors of the 64-bit number - it's a property of the number itself, and apparently 17% of 64-bit numbers have this property.
A lot of the remaining is multiples of 4, which you can either get from having a 2 in both factors or a 4 in one (multiples of 9 are similar).
... or just considering the even numbers almost all of them are 2 x N where N>2^32 and that gets you to within a hair of "most" and if you add in the odd thirds for which the same is true you get a bound of 2/3 - epsilon.
> 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.
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.