bitarray icon indicating copy to clipboard operation
bitarray copied to clipboard

Polynomial evaluation related functions added

Open ph4r05 opened this issue 6 years ago • 0 comments

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 are x_0, ..., x_{block_size} terms. I.e., it is a projection of the input, of i-th bit each block_size bits. 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]
  • 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.

ph4r05 avatar Jan 14 '20 20:01 ph4r05