Возведение числа в степень... (возможные варианты и их улучшение)

функа обязана проверять любое число, но наверняка она сначала тестит на чет, а затем остальную часть теста гонит, коли нумбер нечет - таким образом усе ок

 

CreatorCray

Думаю, для простоты и удобства. Иначе пришлось бы во-первых определять четное ли t, и во-вторых: делящиеся на 3 числа тоже не могут быть простыми, чем они хуже делящихся на 2? И на 5, и на 7.. То есть непонятно, где остановиться, поэтому наверное решили не проверять совсем. Может еще и изменят..

 

UbIvItS
Ты ж ее почитай: сперва p = t+1; а потом while (p не простое) p++;
так что ничего она не проверяет. Сразу переход на следующее число и тест с шагом +1 в цикле.

Stiver
ну, про мне так это непростительная халатность.
функция могла бы выглядеть примерно так:

Код (Text):

1. if (t & 1) // если на входе нечетное число
2.    p = t + 2; // переходим к следующему нечетному
3. else p = t + 1; // переходим к следующему нечетному
4. while (!p.isPrime())
5.   p+=2; //переходим к следующему нечетному
6. return p;

проверка на четность делается очень просто: надо проверить чему равен самый младший бит числа.
А в теле цикла += 2 очень просто позволяет пропускать все четные.

Так что ни простоты ни удобства я не вижу

 

CreatorCray

Угу, только надо еще случай t=1 проверять. Можешь им написать, посмотрим на ответ..

 

Stiver
>> надо еще случай t=1 проверять
зачем? при t == 1 следующим числом для проверки станет 3. По мне так все верно...

>> Можешь им написать
Ради интереса наверное можно.

 

CreatorCray

В описании функции mpz_nextprime(p,t) сказано "compute the next prime > t and store that in p". Следующим простым числом после 1 будет 2, а не 3.

 

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

 

Stiver
точно. Тут я ступил...

UbIvItS
кто здесь!?

 

ты про что??

 

На одном из подфорумов BugTraq.Ru было отмечено...
"Возведение в квадрат в бинарном поле это "раздвигание" бит по четным позициям".
Может кто-нибудь покомментировать это утверждение.
Я чего-то его не понимаю.

 

tar4
Видимо это какая-то фигня В двоичном виде произведение X*X представляет собой сумму чисел Х, сдвинутых влево в соответствии с позициями единичных бит числа X. В общем случае найти какую-то закономерность преобразования бит при сдвигах и сложениях видимо невозможно, разве только для частных тривиальных случаев типа: квадрат нечетного числа будет также нечетным, или квадрат числа состоящего из всех единиц - младшая единица остается на месте, а старшие сдвигаются влево на число единиц в X. Возьми виндовый калькулятор и посмотри на примерах - если найдешь закономерность, получишь орден "Знак почета"

PS: С большим опозданием обнаружил в личке твой вопросик и еще кучку всякой всячины. В связи с этим, довожу до сведения, что в личку я заглядываю крайне редко, поэтому общие вопросы не приватного характера лучше задавать в форуме - и ответ быстрее получишь, и может еще кому интересно будет уточнить, дополнить и т.д.
А по сути - если речь идет об умножении не сверхдлинных, а обычных чисел, то я уже не раз отмечал, что mul\imul на современных процессорах достаточно быстрые операции и ускорение возможно только в частных случаях умножения на константу. Для длинных чисел при умножении на константу с малым числом единичных бит возможно сдвиги\сложения тоже дадут ускорение, при умножении длинного на короткое можно сократить число операций и т.п. Т.е. в частных случаях можно поэкспериментировать, но общих рекомендаций по "раздвижке бит" ИМХО не существует или я о них не знаю

 

Я и взял, посмотрел и ... ничего не нашел. Поэтому и задал вопрос.

 

tar4
"Возведение в квадрат в бинарном поле это "раздвигание" бит по четным позициям".

Если под "бинарным полем" подразумевается обыкновенное алгебраическое поле характеристики 2, то в принципе верно. Так как в нем (x^{m}+x^{m+1}+...+x^{n})^2 = x^{2*m}+x^{2*(m+1)}+...+x^{2*n} В качестве интересной иллюстрации можно посмотреть тему http://www.wasm.ru/forum/viewtopic.php?id=16208

 

Смотрим как советуют в книге.

Генри Уоррен
"Алгоритмические трюки для программистов"

Код (Text):

1. Вычисление х^^n бинарным разложением n
2. int iexp (int x, unsigned n)
3. {
4.   int  p, y;
5.   у = l; // Инициализация результата
6.   p = x; //и переменной р
7.   while(l) {
8.     if (n & 1)
9.     у = p*у;    // Если n нечетно, множим на p
10.     n = n >> 1;     // Позиция очередного бита n
11.    if (n == 0)
12.    return у;   // Если больше нет битов n
13.    p = p*p;        // Степень для очередного бита n
14.    }
15. }

 

Код (Text):

1.  // бинарный поиск корня числа
2.  p=0;
3.  start_iter=2^((bsr(N)>>1)+1)-1;
4. for(;start_iter > 0;)
5.  {
6.    if( p==0 || p < N/p)
7.    {
8.      p+=start_iter;
9.     goto lbl;
10.    }
11.    else if(p > N/p)
12.     {
13.      p-=start_iter;
14.    }
15.    else break; //обрываем цикл - корень найден
16. lbl:   if(start_iter>0 && (start_iter & 1))
17.    {
18.      start_ier>>=1;
19.      start_iter++;
20.     }
21.     else start_ier>>=1;
22.  }

эта реализация способна раскладывать целочисл. квадраты за время O((1/2)*lg2(N))
при небольшой доработки будет считать и плавающую точку.

 

S_Alex
Это обычное сокращение повторяющихся операций с помощью бинарного метода. Так можно разложить любую ассоциативную операцию (если термин не перепутал ).
И вообще-то, этот код уже неоднократно приводился в этой теме - см. посты выше.

 

Хотелось бы услышать рекомендации по улучшению алгоритма вычисления квадратного корня (потом предполагается использовать для работы с большими числами).
Для начала код:

Код (Text):

1. proc Sqrt32 uses ecx edx esi, nx:dword
2.     xor     ecx,ecx
3.     mov     eax,[nx]
4. @@:                        
5.     xor     edx,edx
6.     inc     ecx
7.     mov     esi,10
8.     div     esi
9.     test    eax,eax
10.     jne     @b
11.     bt          ecx,0
12.     jnc     @F
13.     inc     ecx        
14. @@:
15.     clc
16.     shr     ecx,1       ; число цифр
17.     mov     eax,1
18. @@:
19.     xor     edx,edx    
20.     mov     esi,10
21.     mul     esi
22.     dec     ecx
23.     jne     @b
24.     mov     esi,eax
25. @@:    
26.     xor     edx,edx
27.     mul     esi
28.     cmp     eax,[nx]
29.     jbe     @f
30.     dec     esi
31.     mov     eax,esi
32.     jmp     @b
33. @@:
34.     mov     eax,esi                
35. ret
36. endp

Код, конечно, не оптимален. Другой вариант, указанный
выше, переведу на асм позднее.

 

кстати, для быстрого теста является ли число квадратом можно применить след. подход: X^2 mod p==y^2 (p - простое число), но, надо заметить, p должно быть <X, короче, для быстрого теста берем первые в ряду простые числа: 3, 5, 7, 11..... и смотрим по ним модули нашего претендента, если все квадрат. вычеты значит наш претендент с некоторой долей вероятности тоже квадрат - в случае хотя бы одного прокола =====> не квадрат.

 

ну, и ещё: p взаимно простое с X.