Prime power/perfect power

Господа, перед тем как лезть в алгоритм, объясните мне, пожалуйста, как понимать фразу:



"Suppose n is a k-bit number, that is 2^k-1 <= n < 2^k"



Положим, на примере числа 343. Сколько в нем k-bit? Это единички считать надо? Или просто 8*8?

 

Пардон, уже дошло. 343 - 9 бит. Только как это подсчитать? Наиболее экономным способом?

 

n хранится в 32-битном регистре? Если да, то можно сдвигать через carry в сторону MSB до нахождения первой единички.

 

Да. Пусть n будет unsigned.

Мой алгоритм таков:

Код (Text):

1.  
2. unsigned bitcount( unsigned n)
3. {
4.     unsigned b;
5.  
6.     for(b = 0; n; n >>= 1)
7.         b++;
8.  
9.     return b;
10.  
11. }
12.  

Как это сделать еще быстрее?

 

Так?

Код (Text):

1. ecx - n
2. eax - output value - number of bits
3.  
4. @@:
5.     shr ecx, 1
6.     inc eax
7.     test    ecx, ecx
8.     jne SHORT @b

 

volodya



У тя ошипка - нужно eax обнулять перед циклом.





А можно так:

Код (Text):

1.  
2. ; in:  eax - n,
3. ; out: eax - output value - number of bits
4.  
5.     test eax,eax
6.     jz   @F
7.     bsr eax, eax
8. @@: inc eax

BSR r32,r/m32

 

У тя ошипка - нужно eax обнулять перед циклом.



Ну, ты меня уже совсем за идиота держишь. Я считал, что это очевидно.

А за алгоритм - спасибо. Как всегда, что-то оригинальное придумал

 

Нет конечно, я не держу

Просто кто-нить сделает copy-paste и будет удивляться, почему не работает.

 

Теперь, собственно, к алгоритму. Великолепнейшие объяснения лежат тут:

http://shoup.net/ntb/ - 10.5 - "Perfect Power Testing and Prime Power Factoring".

Громадное спасибо Relf, который дотолкал мне одну слабоочевидную вещь (по крайней мере для меня). Сам алгоритм проиллюстрирован ниже.

Код:

Код (Text):

1.  
2. #include <iostream>
3. #include <math.h>
4.  
5. using namespace std;
6.  
7. /* n must be > 0 */
8. inline static unsigned bitcount(unsigned n)
9. {
10.     unsigned b;
11.  
12.     __asm
13.     {
14.         mov eax, n
15.         bsr eax,eax
16.         inc eax
17.         mov b, eax
18.     }
19.  
20.     return b;
21. }
22.  
23. void perfect_power(unsigned n)
24. {
25.     unsigned k = bitcount(n);
26.     unsigned e = 2;
27.     unsigned e_limit = (unsigned)floor(log((double)n)/log(2.0));
28.     for(;e < e_limit; e++)
29.     {
30.         double u = pow(2.0, floor((double)(k-1)/e));
31.         double v = pow(2.0, ceil((double)k/e));
32.  
33.         do
34.         {  
35.             double w = floor((u+v)/2);
36.             unsigned z = pow(w, (double)e);
37.             if(z == n)
38.             {
39.                 cout << "n = d^e: " << n << " = " << w << "^" << e << endl;
40.                 return;
41.             }
42.             else if (z < n)
43.                 u = w + 1;
44.             else
45.                 v = w;
46.         }while(u < v);
47.     }
48. }
49.  
50. void main()
51. {
52.     perfect_power(45435424);
53. }
54.  

 

volodya

Лучше уж так

Код (Text):

1. @@:
2.  inc eax
3.  shr ecx, 1
4.  jne @B

 

Нет. Лучше всего как предлагает S.T.A.S. - вообще без цикла

 

Команды тестирования битов медленные так что ещё неизвестно

чей вариант лучше.

 

Мых-мых, несущественно в данном случае.

Ладно, из уважения к вам, сэр, скажу - мне все равно