CODEWITHSUNDEEP
mathassemblyoptimizationx86-64masm
Kittoes0124
Kittoes0124

Reputation: 5080

What is the fastest method of calculating integer Log10 for 64-bit integers on modern x86-64?

Title; I've found plenty of 32-bit examples but no complete 64-bit ones. Using this post as a guide, I came up with the following implementation of Log10 but I'm not entirely sure if the translation is accurate or efficient...

Edit: Supposedly, this Clang example handles the MAX_VALUE case without the last two instructions but, if removed, I get a result of 20 instead of the expected 19.

...
mov rcx, 0FFFFFFFFFFFFFFFFh               ; put the integer to be tested into rcx

lea r10, qword ptr powersOfTen            ; put pointer to powersOfTen array into r10
lea r9, qword ptr maxDigits               ; put pointer to maxDigits array into r9
bsr rax, rcx                              ; put log2 of rcx into rax
cmovz rax, rcx                            ; if rcx is zero, put zero into rax
mov al, byte ptr [(r9 + rax)]             ; index into maxDigits array using rax; put the result into al
cmp rcx, qword ptr [(r10 + (rax * 8))]    ; index into powersOfTen array using (rax * 8); compare rcx with the result
sbb al, 0h                                ; if the previous operation resulted in a carry, subtract 1 from al
add rcx, 1h                               ; add one to rcx
sbb al, 0h                                ; if the previous operation resulted in a carry, subtract 1 from al
...

align 2

maxDigits:
    byte 00h
    byte 00h
    byte 00h
    byte 01h
    byte 01h
    byte 01h
    byte 02h
    byte 02h
    byte 02h
    byte 03h
    byte 03h
    byte 03h
    byte 03h
    byte 04h
    byte 04h
    byte 04h
    byte 05h
    byte 05h
    byte 05h
    byte 06h
    byte 06h
    byte 06h
    byte 06h
    byte 07h
    byte 07h
    byte 07h
    byte 08h
    byte 08h
    byte 08h
    byte 09h
    byte 09h
    byte 09h
    byte 09h
    byte 0Ah
    byte 0Ah
    byte 0Ah
    byte 0Bh
    byte 0Bh
    byte 0Bh
    byte 0Ch
    byte 0Ch
    byte 0Ch
    byte 0Ch
    byte 0Dh
    byte 0Dh
    byte 0Dh
    byte 0Eh
    byte 0Eh
    byte 0Eh
    byte 0Fh
    byte 0Fh
    byte 0Fh
    byte 0Fh
    byte 11h
    byte 11h
    byte 11h
    byte 12h
    byte 12h
    byte 12h
    byte 13h
    byte 13h
    byte 13h
    byte 13h
    byte 14h

align 2

powersOfTen:
    qword 00000000000000001h
    qword 0000000000000000Ah
    qword 00000000000000064h
    qword 000000000000003E8h
    qword 00000000000002710h
    qword 000000000000186A0h
    qword 000000000000F4240h
    qword 00000000000989680h
    qword 00000000005F5E100h
    qword 0000000003B9ACA00h
    qword 000000002540BE400h
    qword 0000000174876E800h
    qword 0000000E8D4A51000h
    qword 0000009184E72A000h
    qword 000005AF3107A4000h
    qword 000038D7EA4C68000h
    qword 0002386F26FC10000h
    qword 0016345785D8A0000h
    qword 00DE0B6B3A7640000h
    qword 08AC7230489E80000h
    qword 0FFFFFFFFFFFFFFFFh

Upvotes: 2

Views: 2378

Answers (1)

BeeOnRope
BeeOnRope

Reputation: 64895

The fastest method of calculating log10 for arbitrary inputs, will be a table lookup based on leading zero count (a log2 approximation), followed by a possible adjustment by one depending on a second table which records the power of 10 which falls within the range of the log2 approximation.

That's exactly what you found over here, so I think you are good to go. The extension to 64-bits is straightforward if you understand the 32-bit version, just double all the table sizes and fill them with the right values and change a few instructions to use 64-bit registers and 64-bit loads.

Upvotes: 7

Related Questions