4 ms·
You can actually extend the XOR trick for missing elements to any fixed number! The standard (non-XOR) low-memory solution calculates the sum of x, x^2, x^3, .
by Straw 6y ago
You can actually extend the XOR trick for missing elements to any fixed number!
The standard (non-XOR) low-memory solution calculates the sum of x, x^2, x^3, ..., x^n, which gives enough information to find the missing elements as the roots of an n degree polynomial.
We can just do the same thing in the finite field F_{2^k}, where k is the bitwidth of the integers. Addition in this field corresponds to a bitwise XOR, so the first term gives exactly the 1-missing case!
I don't remember how to actually solve the resulting polynomial over the finite field though.
- dandanua 6y agoAddition in F_{2^k} is not the same as XORing. But that summation idea is correct. To solve polynomial you can use this algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algo...
- Straw 6y agoOh, neat, what's the runtime? https://math.stackexchange.com/questions/1479745/relations-of-galois-field-to-bitoperators-in-c https://math.stackexchange.com/questions/1479745/relations-o... What have we missed?
- dandanua 6y agoAh, XORing is indeed addition in F_{2^k}. It's not addition in Z_{2^k}, though. I was thinking about summation modulo prime number, in this case Z_p = F_p.