Benchmark for trailing zero removal

This repo is for benchmarking various trailing zero removal algorithms for their uses in Dragonbox. Discussions of the algorithms listed here can be found here.

Here is the benchmark result I got (on 04/20/2024, on Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz, Windows 10 Laptop):

• 32-bit benchmark for numbers with at most 8 digits.

• 64-bit benchmark for numbers with at most 16 digits.

Notes.

• Samples were generated randomly using the following procedure:
  • Uniformly randomly generate the total number of digits, ranging from 1 to the specified maximum number of digits.
  • Given the total number of digits, uniformly randomly generate the number of trailing zeros, ranging from 0 to the total number of digits minus 1.
  • Uniformly randomly generate an unsigned integer with given total number of digits and the number of trailing zeros.
• Algorithms without any suffix iteratively remove trailing zeros one by one.
• Algorithms suffixed with "2-1" initially attempt to iteratively remove two consecutive trailing zeros at once (by running the loop with $q=100$), and then remove one more zero if necessary.
• Algorithms suffixed with "8-2-1" first check if the input contains at least eight trailing zeros (using the corresponding divisibility check algorithm with $q=10^{8}$), and if that is the case, then remove eight zeros and invoke the 32-bit "2-1" variants of themselves. If there are fewer than eight trailing zeros, then they proceed like their "2-1" variants.
• Algorithms suffixed with "branchless" do branchless binary search, as suggested by reddit users r/pigeon768 and r/TheoreticalDumbass. (See this reddit post.)

Building and installing

See the BUILDING document.

Contributing

See the CONTRIBUTING document.

Licensing

All code is licensed under Boost Software License Version 1.0 (LICENSE-Boost or https://www.boost.org/LICENSE_1_0.txt).