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

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

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

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.

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

Does it actually matter for hash uniformity, though?

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

I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.

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?)

I must be missing something. Aren’t ~50% of 64-bit integers the product of the number 2 and another 32-bit integer?

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.

[0]: https://en.wikipedia.org/wiki/Benford%27s_law

Well, that is entirely not surprising. Pretty sure people writing not terrible hash functions figured it decades ago

So you're better of using a 8x8->16 widening multiplication SIMD instruction or even just a multi register TBL/TBX instruction?

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.

[dead]