Какой самый быстрый метод вычисления целых чисел Log10 для 64-разрядных целых чисел на современном x86-64? - PullRequest
Новая
       80

Какой самый быстрый метод вычисления целых чисел Log10 для 64-разрядных целых чисел на современном x86-64?

2 голосов
/ 07 марта 2019

Название; Я нашел много 32-битных примеров, но нет полных 64-битных. Используя этот пост в качестве руководства, я придумал следующую реализацию Log10, но я не совсем уверен, точен ли перевод или эффективен ...

Редактировать: Предположительно, этот пример Clang обрабатывает случай MAX_VALUE без последних двух инструкций, но, если удалить его, я получаю результат 20 вместо ожидаемых 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

1 Ответ

5 голосов
/ 07 марта 2019

Самым быстрым методом вычисления log10 для произвольных входных данных будет поиск в таблице на основе начального нуля (приближение log2) с последующей возможной корректировкой на единицу в зависимости от второй таблицы, в которой записано значение 10, которое попадает вдиапазон приближения log2.

Это именно то, что вы нашли здесь , так что я думаю, что вы готовы пойти.Расширение до 64-битной системы является простым, если вы понимаете 32-битную версию, просто удвойте все размеры таблиц и заполните их правильными значениями и измените несколько инструкций для использования 64-битных регистров и 64-битной загрузки.

...