saxbophone / arby

Arbitrary precision arithmetic in C++, even at compile-time
https://saxbophone.com/arby/
Mozilla Public License 2.0
8 stars 1 forks source link

Math support ilog() optimisation: count digits when base is a power of 2 #124

Closed saxbophone closed 1 year ago

saxbophone commented 2 years ago

Note: For the first two versions, $+1$ is only added to the ceiling part of the calculation if any bits to the right of the most significant set bit are set. Otherwise, $floor() = ceil()$ (because $x$ is an integer power of the base: $x = b^n$).

Logarithms are very useful for underpinning other mathematical operations so this optimisation may be very useful.

saxbophone commented 2 years ago

Found useful optimisations to be applied here when checking if a single digit is a power of 2 and for log2(): http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

This optimisation should also probably be applied to Nat.bit_length()

saxbophone commented 1 year ago

Extension task: