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

Тема в разделе "WASM.A&O", создана пользователем murder, 27 мар 2010.

  1. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    В eax содержится число без знака [0..232). Необходимо подсчитать количество разрядов этого числа в десятичном представлении. Например для числа 100110b=38d длина равна 2. Код без условных переходов, оптимизируем по скорости.
     
  2. S_Alex

    S_Alex Alex

    Публикаций:
    0
    Регистрация:
    27 авг 2004
    Сообщения:
    561
    Адрес:
    Ukraine
    количество разрядов числа X в десятичном представлении = 0.43429448190325182765*ln(X)+1
    И нет никаких условий и переходов. Для расчетов юзай FPU. Может по скорости и не очень оптимально, но должно работать.
     
  3. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    S_Alex
    Это совсем не оптимально
     
  4. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    murder
    наиболее быстрое будет что-то типа bsr/log2(10), а потом по таблице сравнить исходное число со степенью десятки и при необходимости скорректировать результат на 1
     
  5. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    С высокой точностью Длина_в_битах*3/10

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

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

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    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 - будет немного быстрее.

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

    PowerASM New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    59
    Код (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 загрузки и одна выгрузка + настройка режима округления
     
  8. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    murder
    Если двоичный логарифм сразу преобразовать в десятичный, то табличка потребуется всего одна на 10 элементов. Ну а без таблички можно попробовать 10 возвести в полученую степень и сравнить для коррекции, хотя бинарный поиск наверно будет быстрее в таком случае.
     
  9. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    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 тактов но всё же. Интересно как обстоят дела у интел.
     
  10. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    persicum
    Результат получается приближённый.

    Black_mirror
    Код в студию
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    что значит приближенный, плюс минус один или хуже?
    ИМХО точный результат не даст ни один быстрый алгоритм, пока явно не выпишишь число в виде десятичного стринга и не посчитаешь цифры. Так ли уж сильно будут различатся двоичная запись у 99999 и 100000 например.
     
  12. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    persicum
    Ну да - там плюс минус 1.

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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
     
  14. Twister

    Twister New Member

    Публикаций:
    0
    Регистрация:
    12 окт 2005
    Сообщения:
    720
    Адрес:
    Алматы
    Можно, но быстрее и элегантнее способа не состряпать, чем твой вариант с таблицей.

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

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

    PowerASM New Member

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

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    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, только множитель и делитель другие. Я пока не в силах понять как именно работают умножение+деление.
     
  17. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    PowerASM
    Но ведь в этом и заключается дзен.
     
  18. PowerASM

    PowerASM New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    59
    и в чем же. сидеть неделю ради задачки, которую в быстром случае можно сделать таблицей, в коротком случае на сопроцессоре.
     
  19. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
  20. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    еще один вариант без таблицы, двоичный поиск(может быть с багами):
    Код (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