Goncharov's algorithm
Script error: No such module "Draft topics". Script error: No such module "AfC topic".
Goncharov's algorithm — a method that allows you to count the number of rows in a bit sequence, where the word "row" 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[edit]
where:
- x — input value
- n — number of rows
- pop — a function that counts the number of bits equal to one[2]
Implementation[edit]
// Counts the number of rows in the first element.
// The prevHi parameter returns the state of the high bit for the subsequent concatenation of rows 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 rows in the next element.
// The prevHi parameter is used to concatenate rows 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[edit]
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[edit]
Henry S. Warren Jr. Algorithmic Tricks for Programmers, 2nd Edition. Search this book on 
References[edit]
- ↑ Randomness tests included in the Cryptographic Toolkit from NIST
- ↑ Hamming weight
External links[edit]
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.
