Сколько циферок в числе?

Дано целое число 0<= n < 2^32.
Нужно узнать количество разрядов для числа n в системе с основанием p.

Понятно, что при n=2^32-1 для 2<= p <=16 можно обойтись простой таблицей:

Код (Text):

1. Основание:   Максимум разрядов:
2. 2            32
3. 3            21
4. 4            16
5. 5            14
6. 6            13
7. 7            12
8. 8            11
9. 9            11
10. 10           10
11. 11           10
12. ...
13. 16           8

Но хотелось бы узнать, а нет ли общего красивого решения для двоичной машины (без логарифмов)?
Если RTFM ткните, пожалуйста, чайника.

 

Если втупую (псевдокод):

Код (Text):

1. nDigits=0;
2. k=1;
3. while (k<=n)
4. {
5.   k*=p;
6.   ++nDigits;
7. }

Перевести на asm, думаю, и сам сможешь. Не забывай при этом про возможное переполнение. Также умножение можно заменить сдвигами и сложениями (у тебя ведь p не больше 16).

 

Atlantic, спасибо за алго.
Опять мы пришли к переводу числа в систему с новым основанием:

Код (Text):

1. mov   EAX,[n]
2. mov   EBX,[p]
3. xor   ECX,ECX
4.  
5. loopDigCount:        
6.     xor EDX,EDX
7.     div EBX
8.     inc ECX
9.     or  EAX,EAX
10.     jnz loopDigCount

Получается у нас уже три варианта: линейно-индексный, мультипликативный и соответственно через целочисленное деление.
Один другого не слаще. Но вдруг кто-нибудь найдёт решение получше...

 

В мультипликативном методе можно сократить число умножений, если не перебирать "втупую" все степени, а сначала найти максимальную степень k=2^m =(1, 2, 4, 8, 16, 32)

Код (Text):

1.   ;uses ebx,edi
2.   mov edi,[n]
3.   mov eax,[p]
4.   xor ecx,ecx
5.   inc ecx         ;k=1
6.   cmp eax,edi
7.   jge found
8. @@:
9.   mov ebx,eax     ;p^k
10.   mul eax         ;p^(2*k)
11.   add ecx,ecx     ;k=2*k
12.   cmp eax,edi
13.   sbb edx,0
14.   jc @B
15.   ;дальше можно и "втупую" ;)
16.   shr ecx,1
17.   mov eax,ebx
18.   mov ebx,[p]
19. @@:
20.   mul ebx
21.   add ecx,1
22.   cmp eax,edi
23.   sbb edx,0
24.   jc @B
25. found:
26.   mov eax,ecx

PS: Дальше уменьшать число умножений, заменяя тупой перебор во втором цикле, уже не имеет практического смысла, т.к. штрафы на условных переходах скушают весь выигрыш (в "нормальных" процах штраф за переход примерно равен 3-4-м умножениям)

 

Вот, еще пришла в голову идея: есть у x86 процев замечательная команда BSR. Зная, сколько бит в числе, по lookup-таблице можно определить, какое минимальное количество цифр в p-ичной системе счисления оно должно содержать. И стартовать тупой цикл сразу с этого числа. Теоретически, теперь этот цикл не должен выполниться больше одного раза