[deleted]
Only 17% of all 64-bit Integers are products of two 32-bit integers
41–50 of 115 posts
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#42Earlier quoted context omitted.
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 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.
[deleted]
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#43Earlier quoted context omitted.
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 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.
What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#44> 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" alr…
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.
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#45Earlier quoted context omitted.
> 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.
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.
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.
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#46This 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?)
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#47Earlier quoted context omitted.
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.
What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.
[deleted]
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#48> 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?
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#49> 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?
Perhaps it's binary.
Re: Only 17% of all 64-bit Integers are products of two 32-bit integers
#50Earlier quoted context omitted.
> 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.
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.
Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.