Привет.

Вот сижу меня плющит. Никак не могу придумать как максимально быстро посчитать сколько в числе знаков.
Помогите пожалуйста. Может кто какую формулу знает?

Заранее всем спасибо.

Сначала определись в каком виде считать (восьмерично число, десятичное, шеснадцатеричное и т.д.)
а потом в цикле дели на эту базу, как ноль получишь - количество пройденных итереций и будет разрядность.

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

а еще попробуй тут задать вопрос, может
напишут иной алгоритм ? (он есть?)

http://algolist.manual.ru/forum/

NetImperia
Пришёл в голову такой вариант (результат в EAX):

    mov ecx,число
    xor eax,eax
    cdq
    inc edx
@@: lea edx,[edx + edx * 4]
    sal edx,1
    jc @F
    inc eax
    cmp ecx,edx
    jnc @B
@@:

Целая часть десятичного логарифма + 1.
Или часть логарифма по основанию x +1 в х-овой системе если целое число

плюс 1

Ага я так-же и с делал :)

Всем огромное спасибо.

The Svin

А что быстрее? Загнать результат в FPU, посчитать логарифм и взять целое или сделать то, что предложил Quantum? Я предполагаю, что вариант Кванта быстрее, несмотря на то, что там цикл.

Мне вообще непонятна до конца задача.
В какой системе?
Какого размера?
Потом просили формулу а не код.
Задача на скорость или разрмер если код.
Вобщем как всегда какой вопрос такие и ответы.
Если говорить что число это 32 битное бинарное значение,
и задача на скорость
то можно сделать быстрее чем у Quantum.
Если размер - меньше чем у него же.
Он сам может сделать быстрее. Поскольку, как мне кажется
он тоже толком неуверен чего нужно человеку - и наугад предложил вариант "скорее всего поставленной задачи" с комромиссом между размером и скоростью.
По поводу FPU - я не предлогал FPU, то что делает Quantum и есть рассчёт целой части десятичного логарифма.
Но для данного случая можно чуть быстрее -
1.найди индекс старшего бита.
2.раздели на 10 (AAM) умножь на три (сдвиг, сложение).
3.Проверь остаток на делимость на три. Поставь флаг.
4.Модуль остаток - 1 раздели на три прибавь к 2 увеличь на 1
5.Если флаг (3и случая из 10и) - проверь сравни по таблице
со степенью десятки. Больше - увеличь на 1.

Другой вариант, тоже что и он делает но без цикла - самый быстрый.

 xor ecx,ecx
 cmp eax,10
 inc ecx
 jc done
 cmp eax,100
 inc ecx
 jc done
и т.д...
 

The Svin
Потом просили формулу а не код
Точно, а я как-то не заметил...

Другой вариант, тоже что и он делает но без цикла - самый быстрый.
Был у меня такой вариант года полтора назад в универе на экзамене. Преподаватель грозился убить меня за такой код: "хоть бы в цикл это что ли запихнул, лентяй" :-)

Если размер - меньше чем у него же.
После того инцидента меня до сих пор мучает этот вопрос. Можно пример или ссылку? Заранее спасибо!

В смысле написать размером меньше что ли?
Ты и сам можешь написать.
Повторюсь (и честно говоря забодало повторятся - вопрос поставили невнятно) - если скажут что главное РАЗМЕР.
Вот преподователь такой же. Видимо сам ЦУ внятно не дал,
имея в голове "как надо". Мы же математики-кибернетики-прикладники, нельзя так невнятно ставить задачи.

Ты преподователей то чего боишься здесь?
Если тебе сказали - любой ценой сделать быстрее то какой нафиг тут преподователь имеет голос то, с его комплексами и личной ограниченностью. Здесь только математика судит.

И кстати, если по математике приняв равномерное распределение вероятностно нужно проверять со старших (это к моей самокритике)

 т.е.
 mov ecx,10
 cmp eax,милльярд
 jnc done
 cmp eax,сто милльёнов
 dec ecx
 jnc done
и т.д. 

Должно быть линейное ускорение в 4-5 раз.

Кстати твой вариант нерабочий.
Ты же вычитаешь 10+100+1000..
т.е. у тебя по разному сработает скажем 101 и 120.
В первом случае у тебя будет после первой итерации 91
и на второй итерации 91 - 100 и выход
а во втором случае на второй итерации 110 - 100. и на новую :)
А знаков то у них одинаково :)
Если по размеру то не задумываясь

 xor ecx,ecx
 lea ebx,[ecx][10]
@@:
 xor edx,edx
 inc ecx
 div ebx
 test eax,eax
 jne @B

На три байта короче. И будет работать. Но это будет медленее, но короче, можно ещё короче. Вопрос открытый - чего нужно то.
Как самый быстрый я сказал уже, компромисный - написал формулу по ней можно делать алгоритм.

Вот такой грязновой вариант. Не проверял пока.
Грубо объясняет то что я словами написал.
табличка 10 двойных слов. 9 первых степени 10 от 1 до 9 -1, т.е. 9,99,999 и т.д.
10ый dword=-1.

tbl dd 10-1,100-1,...10^9-1,0FFFFFFFh
...
;edx - число, ecx - out число знаков
	bsr eax,edx
	aam
	movxz ecx,ah
	dec al
	lea ecx,[ecx*2][ecx]
	sets al
      xor ah,ah
      aam 3
	add cl,ah
	cmp tbl[ecx*4],edx
	adc ecx,1

The Svin
Ты же вычитаешь 10+100+1000..
Это я намудрил. Вместо sbb надо было cmp. Уже исправил.

И кстати, если по математике приняв равномерное распределение вероятностно нужно проверять со старших (это к моей самокритике)
Ясно. К сожалению, делить на 10 труднее чем умножать, но надо будет подумать и над этой возможностью (мысли вслух).

На три байта короче. И будет работать. Но это будет медленее, но короче, можно ещё короче.
Div не очень смотрится на фоне такой оптимизации. Для беззнаковых чисел можно сократить на один байт, а мой вариант - на два.

Вопрос открытый - чего нужно то.
Меня интересует всё! Размер и скорость. Хотя я думал, что существует какой-то линейный способ...

Линейный способ существует для части работы.
При чём с относительно большими величинами до 2^97.
Часть эта заключается в том, что довольно просто определить сколько знаков будет в десятичном представлении 2^x. При этом из десяти случаев только в 3х существует угроза что в x+1 бинарном разрядном числе число десятичных знаков не совпадёт с колличеством десятичных знаков в 2^x.
И известно у каких x это может быть.
Это особенно эффективно можно применять когда речь идёт о 64 - 96 разрядных числах.