4 ms·
> 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
by FabHK 4mo 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.
- klodolph 4mo agoAddition 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.
- sdenton4 4mo agoConcatenating 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 4mo agoAh, 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 4mo agoExcept the perfect squares don't reduce by half, so it's not quite 50% but it's very close.
- sdenton4 4mo agoHa, fair!
- thesz 4mo agoSome 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 4mo agoDecoding this so it's readable: 6^2 = (2*2*3)*3 = 2*(2*3*3). (You can escape * with \: \*)
- deleted 4mo ago[deleted]
- topaz0 4mo agoThe 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.