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

▲

ot an hour ago | parent | next [-]

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.

▲

HarHarVeryFunny 39 minutes ago | parent | prev | next [-]

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.

▲

FabHK an hour ago | parent | prev | next [-]

> 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 an hour ago | parent | next [-]

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 36 minutes ago \| parent \| next [-]
		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 16 minutes ago \| parent \| prev [-]
		Except the perfect squares don't reduce by half, so it's not quite 50% but it's very close.

▲

topaz0 an hour ago | parent | prev | next [-]

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 an hour ago | parent | prev | next [-]

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.

▲

an hour ago | parent | prev [-]

[deleted]

▲

danbruc 2 hours ago | parent | prev | next [-]

All the primes above 2^32 are out, but that accounts for only two point something percent.

	▲	topaz0 7 minutes ago \| parent [-]
		But also all of their multiples. I suspect that those account for the vast majority.

▲

PaulHoule 2 hours ago | parent | prev | next [-]

... 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 an hour ago \| parent [-]
		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)

▲

adgjlsfhk1 2 hours ago | parent | prev | next [-]

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

▲

thaumasiotes an hour ago | parent | prev [-]

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