Задачка о длине числа

В eax содержится число без знака [0..2³²). Необходимо подсчитать количество разрядов этого числа в десятичном представлении. Например для числа 100110b=38d длина равна 2. Код без условных переходов, оптимизируем по скорости.

 

количество разрядов числа X в десятичном представлении = 0.43429448190325182765*ln(X)+1
И нет никаких условий и переходов. Для расчетов юзай FPU. Может по скорости и не очень оптимально, но должно работать.

 

S_Alex
Это совсем не оптимально

 

murder
наиболее быстрое будет что-то типа bsr/log₂(10), а потом по таблице сравнить исходное число со степенью десятки и при необходимости скорректировать результат на 1

 

С высокой точностью Длина_в_битах*3/10

Для деления на 10 вроде можно юзать команды двоично-десятичной перепаковки...

Ну вопщем до ума сам доведешь... Скорректируешь если что...

 

Black_mirror
Я тоже так подумал

Код (Text):

1. function numlen(x: dword): dword;register;assembler;
2. const
3.   declen: array[0..31] of byte =(1,1,1,1,1,2, 2, 2, 3,  3,  3,  4,   4,   4,   4,   5,    5,    5,    6,     6,     6,     7,      7,      7,      7,      8,       8,       8,       9,        9,        10,        10        );
4.   decnum: array[0..31] of dword=(9,9,9,9,9,99,99,99,999,999,999,9999,9999,9999,9999,99999,99999,99999,999999,999999,999999,9999999,9999999,9999999,9999999,99999999,99999999,99999999,999999999,999999999,4294967295,4294967295);
5.                                //0,1,2,3,4,5, 6, 7, 8,  9,  10, 11,  12,  13,  14,  15,   16,   17,   18,    19,    20,    21,     22,     23,     24,     25,      26,      27,      28,       29,       30,        31
6. asm
7.   cdq
8.   bsr   edx,eax
9.   cmp   dword[decnum+edx*4],eax
10.   adc   edx,0
11.   movzx eax,byte[declen+edx]
12. end;

Можно ещё попробовать lzcnt вместо bsr - будет немного быстрее.

А можно без таблицы?

 

Код (Text):

1.  finit
2.  push eax
3.  fld1                                ; загрузка 1
4.  fild [x]                            ; загрузка x
5. ; настройка режима округления на отбрасывание дробной части
6.  fstcw [esp]
7.  or byte [esp+1], 12
8.  fldcw [esp]
9. ; первое действие 1*log(2,x)
10.  fyl2x
11. ; второе действие 1*log(2,x)/log(10,2)
12.  fldl2t                            ; загрузка log(2,10)
13.  fdivp
14. ; третье действие round(1*log(2,x)/log(2,10))+1
15.  fistp dword [esp]
16.  pop eax
17.  inc eax

если убрать настройку режима округления будет красивее, но вот скажи те: чего тут не оптимального? без переходов, 3 действия, 3 загрузки и одна выгрузка + настройка режима округления

 

murder
Если двоичный логарифм сразу преобразовать в десятичный, то табличка потребуется всего одна на 10 элементов. Ну а без таблички можно попробовать 10 возвести в полученую степень и сравнить для коррекции, хотя бинарный поиск наверно будет быстрее в таком случае.

 

PowerASM
Ну вот приблизительная таблица

Код (Text):

1. инструкция такты
2. finit      ~100
3. fldcw      ~10
4. fyl2x      ~100
5. fdivp      ~20

В Optimization Guide for AMD family 10h пишут, что латентность fyl2x равна 13, а fyl2xp1 - 114. Проверил на своём Athlon II 250 и оказалось, что fyl2x в 4 раза быстрее чем fyl2xp1. Это конечно не 13 тактов но всё же. Интересно как обстоят дела у интел.

 

persicum
Результат получается приближённый.

Black_mirror

Код в студию

 

что значит приближенный, плюс минус один или хуже?
ИМХО точный результат не даст ни один быстрый алгоритм, пока явно не выпишишь число в виде десятичного стринга и не посчитаешь цифры. Так ли уж сильно будут различатся двоичная запись у 99999 и 100000 например.

 

persicum
Ну да - там плюс минус 1.

http://www.wasm.ru/forum/viewtopic.php?pid=372436#p372436

 

murder
у Уорена в конце 11й главы:

Код (Text):

1. int ilog10(unsigned x)
2. {
3.   int y;
4.   static unsigned table2[11]={0,9,99,...,999999999,0xFFFFFFFF};
5.   y=(19*(31-nlz(x)))>>6;
6.   y=y+((table2[y+1]-x)>>31);
7.   return y;
8. }

31-nlz(x) - это номер старшего единичного бита.

А вот моя безобразная версия:

Код (Text):

1. mov eax,10
2. cmp ecx,10^9
3. sbb eax,0
4. cmp ecx,10^8
5. sbb eax,0
6. ....
7. cmp ecx,10^2
8. sbb eax,0
9. cmp ecx,10^1
10. sbb eax,0

 

Можно, но быстрее и элегантнее способа не состряпать, чем твой вариант с таблицей.

Суть в чем: с помощью fbstp можно перевести число в BCD. Т.е. имея 013d получим 013h, далее с помощью bsr найдем самый старший бит, установленный в единицу. Ну и зная, что в BCD один разряд соответствует четырем битам, легко найдем кол-во разрядов. Есть, правда, один подводный камень - BCD-вариант числа 0xFFFFFFFF не залезет в один DWORD, это надо учесть.

В общем, вполне рабочий метод, правда ни по размеру кода, ни по скорости он не подойдет

 

murder
вам что мало ~10`000`000 вычислений в секунду для 3,0 ГГц процессора. (Хотя я бы не стал считать такты - это бесполезно. У современного проца это число может варьироваться.) К тому же для циклических алгоритмов инициализацию (finit) и настройку округления можно из цикла вынести, что почти в двое ускорит выполнение (судя по вашей таблице)

 

Black_mirror
На данный момент твой код лучший из не табличных.

Вот моя реализация Уоренновского алгоса

Код (Text):

1. function numlen(x: dword): dword;register;assembler;
2. const
3. table: array[0..10] of dword=(0,9,99,999,9999,99999,999999,9999999,99999999,999999999,$FFFFFFFF);
4. asm
5.   cdq
6.   bsr  edx,eax
7.   imul edx,edx,19
8.   shr  edx,6
9.   cmp  dword[table+edx*4+4],eax
10.   adc  edx,1
11.   mov  eax,edx
12. end;

Похоже идея аналогична той, что предложил persicum, только множитель и делитель другие. Я пока не в силах понять как именно работают умножение+деление.

 

PowerASM
Но ведь в этом и заключается дзен.

 

и в чем же. сидеть неделю ради задачки, которую в быстром случае можно сделать таблицей, в коротком случае на сопроцессоре.

 

Ну в общем-то эта тема из разряда "Мелкие задачки для крупных мозгов" и изначально не предполагает какой-либо практической ценности.

 

еще один вариант без таблицы, двоичный поиск(может быть с багами):

Код (Text):

1. mov eax,1;число цифр
2. mov ebx,1
3. mov ecx,5
4. mov edx,10000
5. cmp esi,edx;сравниваем число с серединой диапазона
6. cmovae eax,ecx
7. cmovae ebx,edx
8. lea ecx,[eax+2]
9. imul edx,ebx,100
10. cmp esi,edx
11. cmovae eax,ecx
12. cmovae ebx,edx
13. lea ecx,[eax+2]
14. imul edx,ebx,100
15. cmp esi,edx
16. cmovae eax,ecx
17. cmovae ebx,edx
18. imul edx,ebx,10
19. cmp esi,edx
20. sbb eax,-1