▲ 226 points
back
103 comments
> 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.
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.
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
All the primes above 2^32 are out, but that accounts for only two point something percent.
> 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.
> 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).
Ok so I think I understand your insight: the number of 64 bit numbers you can get from multiplying two 32 bit numbers is the number of distinct results. I guess it follows that, of those 64 bit integers that can be written as the product of 2 32 bit ints, on average they can be factored into 32 bit ints 6 different ways. The only ones that could possibly be written as such a product exactly one way are the prefect squares.
... 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.
There are about 4 billion 64 bit integers for each 32 bit integer.
The chance of a random 64 bit integer being a 32 bit integer is 0.0000000233 %
The chance of a random 64 bit integer being a product of two 32 bit integers is 17%
Nice
There are about 18.446 quintillion more 64-bit integers than 32-bit integers.
The chance of a random 64-bit integer matching some pair of 32-bit integers is a 100%, though.
Or, the odds of a random 64-bit integer being a 32-bit integer are the same as you or me guessing a random 32 bit integer.
Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?
> 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!
Perhaps it's binary.
I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.
Indeed, but justice requires that we recursively continue all the way to the base case, until all 32-bit integers are products of 16-bit integers, all 16-bit integers are products of 8-bit integers, all 8-bit integers are products of 4-bit integers, all 4-bit integers are products of 2-bit integers, and all 2-bit integers are products of 1-bit integers. Only when we have reach all the way down that list to the very, very smallest of the numbers around us and brought justice to them will the future be able to arrive. I literally can not wait for that day.
Why stop there? We can dream of a future where math is bent to our will [0] for the betterment of all mankind!
1 + 1 = 3 (for sufficiently large values of 1)
Maybe we can reach there by using integers as fixed point decimals?
That would require multiplication to be non-commutative, right?
Cryptographers hate this trick
I upvoted you, not because I think your joke is particularly great, but I hate that HN has this tendency to downvote comments that are clearly meant as a humorous contribution. And I get it, no-one wants HN to turn into Reddit. I also understand that not every joke lands. But I just think it's unnecessary to downvote, you could simply ignore.
There should be a law!
This feels like a underlying property that contributes to of Benford's Law[0]. That is, most numbers we measure and record are the results of various independent (addition) and dependent (multiplication) factors stacking together, and we observe this property in the distribution of them.
> 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 classes: Y (has 32 but factors), N (does not have 32 bit factors), U (unknown).
Check if prime using probabilistic miller rabin. (Error prob goes to zero exponentially fast). If prime, return N. If it's not a prime, then run T steps of pollard rho to determine whether the number has 32 but factors; return Y,N, or U depending of the factors found up to step T.
The key observation is that T can be chosen to make the UNKNOWN class very small (with high probability), and so our estimate should rapidly converge to 17%Y, 83%N, ~0.001%U
For fixed error tolerance, this would run in roughly a constant number of iterations, independent of N.
There is a cute argument (I think it is due to Erdos) that, asymptotically, 0% of the integers in [0,n^2] appears in the "n by n multiplication table":
By Erdos-Kac, almost all integers of size about n^2 have about log(log(n^2)) ~ log(log(n)) prime factors. However, almost all integers in the multiplication table have about 2*log(log(n)) prime factors.
Kevin Ford gets much more precise asymptotic estimates.
The mathematical term for this is the probability of a number being b-smooth. Here ‘b’ is 2^32
This is something I had thought about some time back where I was thinking about the feasibility of somehow using the upper and lower registers inside a multiplier as general purpose storage for fun / seeing if you could make them more compact.
Anyway here is a fun pattern you get when you multiply 8 bit unsigned integers. Not all pairs of (upper bits, lower bits) are reachable, and it has a lot of distinct patterns.
https://i.imgur.com/Gb3HDR0.png
(Should I host the image on GitHub Gists so it doesn't vanish?)
This just seems like an expansion of prime numbers to includes factors in the 2^33+ range. Basically you're calculating if a number is prime but stopping the check when the factors go above 2^32.
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.
I don't think I needed an AI-generated infographic of the headline. It looks like a product sales pitch.
Extremely strange way to deliver the headline (right before delivering the headline).
So you're better of using a 8x8->16 widening multiplication SIMD instruction or even just a multi register TBL/TBX instruction?
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.
Well, that is entirely not surprising. Pretty sure people writing not terrible hash functions figured it decades ago
I must be missing something. Aren’t ~50% of 64-bit integers the product of the number 2 and another 32-bit integer?
Only 20% of 2 digit numbers are product of one digit numbers:
10 (1+9), 11, 12, 13 … 18 (9+9)
I wonder what kind of result you'd get with floats
Does it actually matter for hash uniformity, though?
Honestly, this is a larger portion than I would have expected.
If this seems counterintuitive, consider that only about a third of the two-digit numbers ({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81}) can be written as the product of two one-digit numbers.