bitarray
bitarray copied to clipboard
Polynomial evaluation related functions added
We implemented few other functions related to the GF(2) polynomial evaluation:
- count(1) is more effective - HW on 64 bits.
- using WP3 from http://bisqwit.iki.fi/source/misc/bitcounting/#Wp3NiftyRevised
- fast copy of the vector contents
- evaluate monic polynomial multiple times on input data
- e.g.,
x_i, where there arex_0, ..., x_{block_size}terms. I.e., it is a projection of the input, of i-th bit eachblock_sizebits. This can later serve as basis to construct more complex polynomials evaluated on the whole input data repeatedly. - e.g. assume
base[i] = base[i].eval_monic(input, i, block_size) for i in range(block_size)] - then
x_2 * x_8 + x_14 = base[2] * base[8] + base[14]
- e.g.,
- fast operations: (A op B).count(1), where op is AND, OR, XOR
- fast polynomial evaluation when only the number of 1 is required
-
HW(x_2 * x_8 + x_14) = (base[2] * base[8]).fast_hw_xor(base[14])- the last XOR is performed in-memory, which is faster
- eval all top-k terms, according to the z-score. Top-k is performed via heap.
We also used vector operations from #20.
Check if there is something usable, I can make a PR using just some parts of this code.