Форум программистов, компьютерный форум CyberForum.ru

Перевод 10-го числа в 2-ое - C++

Восстановить пароль Регистрация
 
adds
0 / 0 / 0
Регистрация: 07.09.2011
Сообщений: 14
18.09.2011, 18:24     Перевод 10-го числа в 2-ое #1
Народ обьясните пжлста как работает эта функция(быстрое возведение числа в степень a^d mod n) :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long powmod(long a, long d, long n)
{
    long b = 1;
 
    while (d) 
    {
        if (d % 2 == 0) 
        {
             d /= 2;
             a = (a * a) % n;
        }
        else 
        {
             d--;
             b = (b * a) % n;
         }
     }
     return b;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
18.09.2011, 18:48     Перевод 10-го числа в 2-ое #2
Думается, что такое еще быстрее работать будет:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long powmod(long a, long d, long n)
{
    long rez = 1, b = a;
 
    while (d) 
    {
        if (d & 1)
        {
             rez *= b;
             rez %= n;
        }
        b *= b;
        b %= n;
        d >>= 1; 
     }
     return rez;
}
adds
0 / 0 / 0
Регистрация: 07.09.2011
Сообщений: 14
18.09.2011, 19:20  [ТС]     Перевод 10-го числа в 2-ое #3
Народ объясните этот кусок
C++
1
2
3
4
5
 else 
        {
             d--;
             b = (b * a) % n;
         }
silent_1991
18.09.2011, 19:46
  #4

Не по теме:

adds, и всё-таки вы в СибГУТИ учитесь... Зря обманули в прошлый раз, так бы может-быть помог...

fidzhi
5 / 5 / 1
Регистрация: 16.02.2011
Сообщений: 45
18.09.2011, 20:18     Перевод 10-го числа в 2-ое #5
Цитата Сообщение от adds Посмотреть сообщение
Народ объясните этот кусок
C++
1
2
3
4
5
 else 
        {
             d--;
             b = (b * a) % n;
         }
Тебе не понятен только данный кусок кода или обязательно в контексте первого поста?
Yandex
Объявления
18.09.2011, 20:18     Перевод 10-го числа в 2-ое
Ответ Создать тему
Опции темы

Текущее время: 09:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru