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

Тема в разделе "WASM.A&O", создана пользователем locki, 4 апр 2007.

  1. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    функа обязана проверять любое число, но наверняка она сначала тестит на чет, а затем остальную часть теста гонит, коли нумбер нечет - таким образом усе ок:)
     
  2. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    CreatorCray
    Думаю, для простоты и удобства. Иначе пришлось бы во-первых определять четное ли t, и во-вторых: делящиеся на 3 числа тоже не могут быть простыми, чем они хуже делящихся на 2? И на 5, и на 7.. :) То есть непонятно, где остановиться, поэтому наверное решили не проверять совсем. Может еще и изменят..
     
  3. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    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 очень просто позволяет пропускать все четные.

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    CreatorCray
    Угу, только надо еще случай t=1 проверять. Можешь им написать, посмотрим на ответ..
     
  5. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    Stiver
    >> надо еще случай t=1 проверять
    зачем? при t == 1 следующим числом для проверки станет 3. По мне так все верно...

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    CreatorCray
    В описании функции mpz_nextprime(p,t) сказано "compute the next prime > t and store that in p". Следующим простым числом после 1 будет 2, а не 3.
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    вопрос не стоит выеденного яйца:)) - ты волен сам устанавливать будут у тебя в цикле чёты или нет - так учём проблема. вот коли ты выщемишь составной нумбер, который она обзавет праймом вот ето интересно:))
     
  8. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    Stiver
    точно. Тут я ступил...

    UbIvItS
    кто здесь!?
     
  9. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    ты про что??
     
  10. tar4

    tar4 New Member

    Публикаций:
    0
    Регистрация:
    28 сен 2006
    Сообщения:
    43
    На одном из подфорумов BugTraq.Ru было отмечено...
    "Возведение в квадрат в бинарном поле это "раздвигание" бит по четным позициям".
    Может кто-нибудь покомментировать это утверждение.
    Я чего-то его не понимаю.
     
  11. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    tar4
    Видимо это какая-то фигня ;) В двоичном виде произведение X*X представляет собой сумму чисел Х, сдвинутых влево в соответствии с позициями единичных бит числа X. В общем случае найти какую-то закономерность преобразования бит при сдвигах и сложениях видимо невозможно, разве только для частных тривиальных случаев типа: квадрат нечетного числа будет также нечетным, или квадрат числа состоящего из всех единиц - младшая единица остается на месте, а старшие сдвигаются влево на число единиц в X. Возьми виндовый калькулятор и посмотри на примерах - если найдешь закономерность, получишь орден "Знак почета" ;)

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

    tar4 New Member

    Публикаций:
    0
    Регистрация:
    28 сен 2006
    Сообщения:
    43
    Я и взял, посмотрел и ... ничего не нашел. Поэтому и задал вопрос.
     
  13. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    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
     
  14. S_Alex

    S_Alex Alex

    Публикаций:
    0
    Регистрация:
    27 авг 2004
    Сообщения:
    561
    Адрес:
    Ukraine
    Смотрим как советуют в книге.

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


    Код (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. }
     
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    Код (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))
    при небольшой доработки будет считать и плавающую точку.
     
  16. maxdiver

    maxdiver Max

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    308
    Адрес:
    Саратов
    S_Alex
    Это обычное сокращение повторяющихся операций с помощью бинарного метода. Так можно разложить любую ассоциативную операцию (если термин не перепутал ;) ).
    И вообще-то, этот код уже неоднократно приводился в этой теме - см. посты выше.
     
  17. tar4

    tar4 New Member

    Публикаций:
    0
    Регистрация:
    28 сен 2006
    Сообщения:
    43
    Хотелось бы услышать рекомендации по улучшению алгоритма вычисления квадратного корня (потом предполагается использовать для работы с большими числами).
    Для начала код:
    Код (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
    Код, конечно, не оптимален. Другой вариант, указанный
    выше, переведу на асм позднее.
     
  18. UbIvItS

    UbIvItS Well-Known Member

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.077
    ну, и ещё: p взаимно простое с X.