> 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.
> 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.
... 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.
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.
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 whose prime factors are all larger than 2^32.
If you're only considering numbers that will fit into 64 bits, all of the ones that satisfy that requirement will themselves be prime. (Because the product of two numbers both greater than 2^32 is greater than 2^64.)
Indeed, but justice requires that we continue, 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.
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.
"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.
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.
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.
> 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.
> 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.
All the primes above 2^32 are out, but that accounts for only two point something percent.
... 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.
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).
So you're better of using a 8x8->16 widening multiplication SIMD instruction or even just a multi register TBL/TBX instruction?
There are about 4 billion more 64 bit integers than 32 bit integers.
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.
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.
I think they meant to write "There are about 4 billion TIMES 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.
Wonder what the limit is as you add more 32 bit integers to the product. Just the primes over 32 bit?
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 whose prime factors are all larger than 2^32.
If you're only considering numbers that will fit into 64 bits, all of the ones that satisfy that requirement will themselves be prime. (Because the product of two numbers both greater than 2^32 is greater than 2^64.)
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.
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 continue, 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!
0: https://en.wikipedia.org/wiki/Indiana_pi_bill
1 + 1 = 3 (for sufficiently large values of 1)
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.
There should be a law!
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.
"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.
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
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.
where is the graph and the theorem for integers of n bits, with n going to infinity?