3 ms·
An optimizing compiler will turn div-by-constant and mod-by-constant into multiplications and bitshifts. For example, the Rust compiler: https://play.rust-lang.
by adwn 5y ago
An optimizing compiler will turn div-by-constant and mod-by-constant into multiplications and bitshifts. For example, the Rust compiler: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=6ff274d702aec5de7078dba9300c9ac4 https://play.rust-lang.org/?version=stable&mode=release&edit... (select "Show assembly" on the top-left button).
pub fn divmod10(x: u32) -> (u32, u32) {
(x / 10, x % 10)
}
generates
mov ecx, edi
mov eax, 3435973837
imul rax, rcx
shr rax, 35
lea ecx, [rax + rax]
lea ecx, [rcx + 4\*rcx]
sub edi, ecx
mov edx, edi
ret
- kongin 5y agoIt's still not as efficient since you're breaking on base 10 digit boundaries, not base 2, the most efficient encoding will be base 3, but alas we don't have ternary computers.
- adwn 5y agoBut it's a much more compact than that glibc monstrosity is. Sure, the glibc version will win in a micro-benchmark, but micro-benchmarks don't capture the effect on the instruction cache.
- kongin 5y agohttps://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Radix_economy Using a decimal expansion adds 25% overhead from pure maths. Your cache will be larger if you're working in base ten regardless of what optimizations your compiler does.