> 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.
svat 53 minutes ago [-]
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:
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.
ot 10 hours ago [-]
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.
jetsamflotsam 5 hours ago [-]
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.
kens 4 hours ago [-]
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.
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.
adgjlsfhk1 50 minutes ago [-]
> For example, the different NaN values could hold debugging information to track down errors.
Unfortunately IEEE didn't bother specifying NaN propagation semantics so it ended up pretty useless.
danbruc 11 hours ago [-]
All the primes above 2^32 are out, but that accounts for only two point something percent.
topaz0 9 hours ago [-]
But also all of their multiples. I suspect that those account for the vast majority.
danbruc 6 hours ago [-]
Each x is prime with probability 1/ln(x), each x has M/x multiples less than M, as a fraction of M that is just 1/x. Together that makes 1/(x ln(x)) with the indefinite integral ln(ln(x)). If we plug in 2^32 and 2^64 [1], we get ln(2). So about 69.3 % of all 64 bit integers should have a prime factor larger than 2^32 and therefore not be the product of two 32 bit integers. That leaves about 13 % unaccounted. Three prime factors all larger than 2^32/2, five prime factors all larger than 2^32/3, and so on cannot be packed into two 32 bit integers. Not sure to how much this will add up.
[1] The bounds are important because they guarantee that there is at most one prime factor from that range and this ensures that we are not double counting anything. If the upper bound was larger than the square of the lower bound, then we would have to worry about double counting numbers with more than one large prime factor.
topaz0 6 hours ago [-]
Nice work. I guess "vast majority" is overstating the case, but majority anyway.
6 hours ago [-]
thehappypm 6 hours ago [-]
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
danbruc 5 hours ago [-]
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.
FabHK 10 hours ago [-]
> 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.
sdenton4 10 hours ago [-]
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.
FabHK 9 hours ago [-]
Ah, fair enough, thanks everyone. So basically the argument is if that we have a deterministic function taking a pair (x_1, x_2) with x_i in X with |X| = M, then the function can produce at most M^2 outputs. And knowing that the function is symmetric cuts it down to M(M+1)/2. (Which is still far bigger than the 2M in my addition analogy.) Cheers.
Dylan16807 9 hours ago [-]
Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.
thesz 6 hours ago [-]
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.
mkl 1 hours ago [-]
Decoding this so it's readable: 6^2 = (2*2*3)*3 = 2*(2*3*3).
(You can escape * with \: \*)
sdenton4 8 hours ago [-]
Ha, fair!
topaz0 9 hours ago [-]
The 2^64 in gps argument comes from the number of pairs of 32 bit numbers, not from the upper bound of multiplying two 32 bit numbers. So for the addition case the symmetry argument is still only good enough to get you down to about 2^63, which doesn't help you at all because you have much stronger information from the upper bound.
klodolph 10 hours ago [-]
Addition in this case is cutting from 2^64 to 2^33-1.
The 2^64 number is the number of inputs. For an operation which is commutative, you expect the outputs to be 2^63+2^32 or smaller, since you’ve introduced symmetry.
9 hours ago [-]
HarHarVeryFunny 9 hours ago [-]
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.
orlp 8 hours ago [-]
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.
HarHarVeryFunny 7 hours ago [-]
OK - thanks. I must have misunderstood what the other poster was saying, since I thought they were objecting to the "most" characterization.
Dylan16807 3 hours ago [-]
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.
gweinberg 6 hours ago [-]
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.
adgjlsfhk1 11 hours ago [-]
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).
PaulHoule 11 hours ago [-]
... 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.
topaz0 10 hours ago [-]
It's a bit more subtle than that -- most n>2^32 are not prime in which case 2 x n has more factorizations you would have to check.
(Just by way of example, for n=2^33, 2n=2^34 but also =2^17*2^17)
thaumasiotes 10 hours ago [-]
> 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.
Dylan16807 3 hours ago [-]
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.
henry2023 11 hours ago [-]
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
HWR_14 11 hours ago [-]
There are about 18.446 quintillion more 64-bit integers than 32-bit integers.
adrian_b 10 hours ago [-]
True, but there are as many 64-bit integers as pairs of 32-bit integers.
Therefore the fact that relatively few 64-bit numbers are products of 32-bit integers means that a lot of pairs of 32-bit integers give by multiplication the same product.
aidenn0 7 hours ago [-]
That seems intuitively true given that most 32-bit numbers are composite, so if you have
X = ab and aY < 2^32 and bY < 2^32:
X × Y = X/a × aY = X/b × bY = Y × X = aY × X/a = bY × X/b
Which is 6 pairs resulting in the same product. This will be reduced if e.g. aY = X, but still...
moefh 10 hours ago [-]
I think they meant to write "There are about 4 billion TIMES more 64 bit integers than 32 bit integers".
henry2023 10 hours ago [-]
Indeed, edited the mistake
10 hours ago [-]
bo1024 8 hours ago [-]
There are about 2^64 more 64-bit integers than 32-bit integers.
layer8 10 hours ago [-]
The chance of a random 64-bit integer matching some pair of 32-bit integers is a 100%, though.
brookst 10 hours ago [-]
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.
rao-v 10 hours ago [-]
Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?
thaumasiotes 10 hours ago [-]
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.
9 hours ago [-]
9 hours ago [-]
nyeah 9 hours ago [-]
What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.
shiandow 3 hours ago [-]
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).
9 hours ago [-]
tobz1000 9 hours ago [-]
> 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?
Timwi 3 hours ago [-]
It looks like that has been fixed in the article. Good catch!
tgv 9 hours ago [-]
Perhaps it's binary.
pants2 11 hours ago [-]
I dream of a future where all 64-bit integers are products of 32-bit integers. Together, we can change math for the better.
jerf 10 hours ago [-]
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.
order-matters 10 hours ago [-]
Enough of this divided binary world, we are all one
jihadjihad 11 hours ago [-]
Why stop there? We can dream of a future where math is bent to our will [0] for the betterment of all mankind!
It helps if you take the limit of 1 going towards 1.5.
Most 1s won't go towards 1.5, but sometimes you're lucky.
Taek 8 hours ago [-]
I thought you were making a joke but if we're assuming that the 1's are being rounded or truncated before the final value cake is produced I guess you are right.
aidenn0 7 hours ago [-]
That would require multiplication to be non-commutative, right?
basilikum 6 hours ago [-]
Cryptographers hate this trick
AlienRobot 6 hours ago [-]
Maybe we can reach there by using integers as fixed point decimals?
kleiba2 11 hours ago [-]
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.
zamadatix 11 hours ago [-]
"Ignore" is one of those things that sounds like it's a neutral choice but really isn't in practice - it's still just saying "can only ever be positively pressured". IMO people shouldn't go as far as flag though, at the very least, and if it's already at the bottom of the sort there is no sense dumping on it further.
My current comment itself, for instance, also doesn't really add anything to the discussion about the article and I'd have no expectation people leave it from going negative. Maybe the will, maybe they won't, but there is no reason to expect they should in principle of me loving tangents :D.
brookst 10 hours ago [-]
There should be a law!
AnotherGoodName 5 hours ago [-]
The mathematical term for this is the probability of a number being b-smooth. Here ‘b’ is 2^32
svat 50 minutes ago [-]
It's related, but not the same thing. For example, for b=10, the number 70=2x5x7 is b-smooth, but it cannot be written as the product of two numbers less than b. Here are the other b-smooth (counter)examples for b=10:
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.
_alternator_ 8 hours ago [-]
> 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.
bonzini 7 hours ago [-]
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.
_alternator_ 5 hours ago [-]
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!
_alternator_ 4 hours ago [-]
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.
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.
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.
intuitionist 8 hours ago [-]
Having a prime factor greater than 2^32 accounts for about 80% of the 64-bit integers that can’t be expressed as a product of 32-bit integers. But it’s not the only way; you can also have three prime factors in the range (2^16, 2^32), for instance.
bonzini 7 hours ago [-]
More precisely one in the range (a,2^32) and two in the range (2^32/a, 2^32). But if the latter have many duplicate prime factors it's worse.
Taek 8 hours ago [-]
Well, technically yes, but 'stopping the factors at 32 bits' is a plenty interesting constraint because it excludes all 64 bit composite numbers that have at least one factor above 2^32.
You have to redo the math to make the constraint work.
kingstnap 9 hours ago [-]
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.
(Should I host the image on GitHub Gists so it doesn't vanish?)
kurlberg 7 hours ago [-]
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.
tucnak 7 hours ago [-]
They address this argument in the blog.
8 hours ago [-]
furyofantares 6 hours ago [-]
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).
11 hours ago [-]
saghm 4 hours ago [-]
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.
andrewflnr 4 hours ago [-]
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.
saghm 2 hours ago [-]
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.
9 hours ago [-]
cobbzilla 9 hours ago [-]
I must be missing something. Aren’t ~50% of 64-bit integers the product of the number 2 and another 32-bit integer?
slazaro 8 hours ago [-]
Going from 32 bits to 64 bits doesn't double the range (that would be adding 1 bit), it squares the range.
mplanchard 8 hours ago [-]
I don’t think so, because that only gets you up to 2x2^32, which is nowhere near halfway to 2^64
jlarocco 8 hours ago [-]
No. 50% of them are the product of 2 and a 63-bit integer.
fogleman 8 hours ago [-]
Does it actually matter for hash uniformity, though?
themafia 3 hours ago [-]
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.
PunchyHamster 9 hours ago [-]
Well, that is entirely not surprising. Pretty sure people writing not terrible hash functions figured it decades ago
crest 10 hours ago [-]
So you're better of using a 8x8->16 widening multiplication SIMD instruction or even just a multi register TBL/TBX instruction?
Automator666 3 minutes ago [-]
[flagged]
MarkusQ 11 hours ago [-]
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.
childintime 10 hours ago [-]
where is the graph and the theorem for integers of n bits, with n going to infinity?
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.
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:
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.Information quantities are more meaningfully expressed in number of bits.
Having ~a quadrillion redundant bitstrings all mapping to NaN sounds pretty bad, but logarithmic/information utilization-wise, this is actually not too bad.
See "8087 Numeric Data Processor" page S-74: https://ethw.org/w/images/2/2f/Intel_8086_family_users_numer...
Unfortunately IEEE didn't bother specifying NaN propagation semantics so it ended up pretty useless.
[1] The bounds are important because they guarantee that there is at most one prime factor from that range and this ensures that we are not double counting anything. If the upper bound was larger than the square of the lower bound, then we would have to worry about double counting numbers with more than one large prime factor.
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
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.
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.
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.
(You can escape * with \: \*)
The 2^64 number is the number of inputs. For an operation which is commutative, you expect the outputs to be 2^63+2^32 or smaller, since you’ve introduced symmetry.
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.
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.
(Just by way of example, for n=2^33, 2n=2^34 but also =2^17*2^17)
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.
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.
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
Therefore the fact that relatively few 64-bit numbers are products of 32-bit integers means that a lot of pairs of 32-bit integers give by multiplication the same product.
X = ab and aY < 2^32 and bY < 2^32:
X × Y = X/a × aY = X/b × bY = Y × X = aY × X/a = bY × X/b
Which is 6 pairs resulting in the same product. This will be reduced if e.g. aY = X, but still...
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.
That should be "relatively few 20000000-bit integers", right?
0: https://en.wikipedia.org/wiki/Indiana_pi_bill
Most 1s won't go towards 1.5, but sometimes you're lucky.
My current comment itself, for instance, also doesn't really add anything to the discussion about the article and I'd have no expectation people leave it from going negative. Maybe the will, maybe they won't, but there is no reason to expect they should in principle of me loving tangents :D.
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.
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!
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
[0]: https://en.wikipedia.org/wiki/Benford%27s_law
You have to redo the math to make the constraint work.
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?)
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.
Extremely strange way to deliver the headline (right before delivering the headline).
> 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.
https://arxiv.org/pdf/1908.04251