Comment

Comment by nly

This post misses one of the most fundamental and important optimisations for 'digits10' that his compiler is likely doing for him: turning the divide by 10 in to a multiply by using a multiplicative inverse mod 2^64

    $ cat div10.cpp 
    #include <cstdint>

    uint64_t div10(uint64_t y) {
        return y / 10;
    }

    $ g++ -std=c++11 -march=native -Ofast -c div10.cpp
    $ objdump -C -d --no-show-raw-insn div10.o

    0000000000000000 <div10 (unsigned long)>:
    0:   movabs $0xcccccccccccccccd,%rdx
    a:   mov    %rdi,%rax
    d:   mul    %rdx
    10:   mov    %rdx,%rax
    13:   shr    $0x3,%rax
    17:   retq
His basic implementation likely isn't using division at all.
parent nly 12 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton