Goncharov's algorithm

Goncharov's algorithm — a method that allows you to count the number of runs in a bit sequence, where the word "run" means a continuous subsequence of identical bits. A sequence of length k bits consists of k absolutely identical bits, starts and ends with a bit containing the opposite value.^[1]

Algorithm

n = p o p (x \oplus (x > > 1)) + 1

where:

x — input value
n — number of runs
pop — a function that counts the number of bits equal to one^[2]

Implementation

  // Counts the number of runs in the first element.
  // The prevHi parameter returns the state of the high bit for the subsequent concatenation of runs across the boundary between elements.
  template <class T>
  static unsigned int getNumberOfRowsFirst(T x, int &prevHi)
  {
    prevHi = 1 - (x & 1);
    return getNumberOfRowsNext(x, prevHi);
  }

  // Counts the number of runs in the next element.
  // The prevHi parameter is used to concatenate runs across the boundary between elements.
  template <class T>
  static unsigned int getNumberOfRowsNext(T x, int &prevHi)
  {
    unsigned int uiRes = pop(static_cast<T>(x ^ ((x << 1) | prevHi)));
    prevHi = x >> ((sizeof(T) * 8) - 1);

    return uiRes;
  }

Testing

For testing, we used a nettop based on the N3160ND3V motherboard with an Intel (R) Celeron (R) CPU N3160 @ 1.60GHz.

OS: Ubuntu 20.04.4 LTS (Focal Fossa)

Execution speed testing was carried out for versions of the algorithm with and without lookup tables, for elements ranging in size from 8 to 128 bits.

A 1 megabyte data block was used. The execution speed was averaged over 100 epochs.

It turned out that with and without tables, the execution speed is almost the same. Deviations varied from run to run within ±1%.

On the specified hardware, the algorithm works fastest with 64-bit elements. (uint64_t):

>>>> Testing for elements of size 64 bits <<<<
...
Test without tables:
number of bit runs: 2097152
avg execution time: 1.49 uS
Test with tables:
number of bit runs: 2097152
avg execution time: 1.49 uS

Notes

Henry S. Warren Jr. Algorithmic Tricks for Programmers, 2nd Edition. Search this book on

References

↑ Randomness tests included in the Cryptographic Toolkit from NIST
↑ Hamming weight

External links

This article "Goncharov's algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Goncharov's algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

[1] Randomness tests included in the Cryptographic Toolkit from NIST

[2] Hamming weight

[1]

[2]