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

Improve efficiency of Nat::_stringify_for_base() #135

Open saxbophone opened 1 year ago

saxbophone commented 1 year ago

The efficiency of this method is pretty abysmal for base-10. It can be improved somewhat by finding the largest power of 10 that will fit in uintmax_t ( $n = floor(log_{10}(uintmax)$ ) and serialising it to base $10^n$ instead.

We just need to take care to pad intermediate digits with the full number of leading zeroes, and not pad the leading digit at all.

This technique can also be used for other bases, although we might find that using bit-shifting approaches for those that are binary powers is good enough.