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

Быстрое возведение в степень - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
Ghoster
0 / 0 / 0
Регистрация: 02.12.2012
Сообщений: 35
31.03.2013, 15:33     Быстрое возведение в степень #1
Написать функцию быстрого возведения в степень. Функция принимает в
качестве параметров y,x и n и возвращает y^x mod y как результат программы.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.03.2013, 15:33     Быстрое возведение в степень
Посмотрите здесь:

Возведение в степень C++
возведение в степень C++
C++ Возведение степень
Возведение в степень C++
Возведение в степень C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
31.03.2013, 15:36     Быстрое возведение в степень #2
А медленное возведение в степень - это как?
Sor
35 / 35 / 0
Регистрация: 24.11.2011
Сообщений: 309
31.03.2013, 15:38     Быстрое возведение в степень #3
криптографией отдает
Catstail
Модератор
 Аватар для Catstail
21501 / 10254 / 1670
Регистрация: 12.02.2012
Сообщений: 17,139
31.03.2013, 15:38     Быстрое возведение в степень #4
Цитата Сообщение от BRcr Посмотреть сообщение
А медленное возведение в степень - это как?
- мне кажется, что суть в том, чтобы возвести в нужную степень с использованием минимума умножений
coloc
погромист
 Аватар для coloc
409 / 245 / 15
Регистрация: 27.08.2012
Сообщений: 550
Завершенные тесты: 1
31.03.2013, 15:43     Быстрое возведение в степень #5
C++
1
2
3
inline int powInd( int a,int n ) {
  return (!n)?1:((n&1)?a:1)*powInd(a*a,n/2);
}
Так что ли? Хотя не знаю быстрой ли этот вариант
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
31.03.2013, 15:51     Быстрое возведение в степень #6
Цитата Сообщение от coloc Посмотреть сообщение
2
3
4
inline int powInd( int a,int n ) {
* return (!n)?1(n&1)?a:1)*powInd(a*a,n/2);
}
Так что ли? Хотя не знаю быстрой ли этот вариант
это вообще бессмысленно усложнённый вариант, а не просто медленный. Цикл использовать намного быстрее рекурсии. Есть ещё вариант
x в степени y=exp( y*log(x))
не знаю, быстрее ли он цикла?
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
31.03.2013, 15:58     Быстрое возведение в степень #7
Рекурсия действительно не оправдана.
C++
1
2
3
4
5
6
double _pow_( double x, double y ) 
{
  double res( x );
  while( --y ) res *= x;
  return res;
}
Sor
35 / 35 / 0
Регистрация: 24.11.2011
Сообщений: 309
31.03.2013, 16:02     Быстрое возведение в степень #8
C++
1
2
3
4
long long cr(long x, long y, long z)
    {
        return pow(x,y) % z;
    }
Вальдемар
 Аватар для Вальдемар
-5 / 0 / 0
Регистрация: 29.07.2012
Сообщений: 61
31.03.2013, 16:03     Быстрое возведение в степень #9
C++
1
2
3
4
int SQRT(int x, const int n){
    for(int temp = x, i=1; i<n; i++) x = x*temp;
    return x;
}
Sor
35 / 35 / 0
Регистрация: 24.11.2011
Сообщений: 309
31.03.2013, 16:10     Быстрое возведение в степень #10
C++
1
2
3
4
long long cr(long x, long y, long z)
    {
        return fmod(pow(x,y),z);
    }
Добавлено через 2 минуты
работать, то придется с большими числами, иначе толку то нет.
я думаю, можно куски исходников найти. если не ошибаюсь AES система на этой формуле базируется
Praktolock
 Аватар для Praktolock
58 / 58 / 0
Регистрация: 29.11.2011
Сообщений: 272
31.03.2013, 16:12     Быстрое возведение в степень #11
гугли "алгоритм быстрого возведения в степень", всё давно придумано уже
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
31.03.2013, 18:55     Быстрое возведение в степень #12
http://www.facebook.com/groups/31178...1638885225321/

Добавлено через 53 секунды
единственный вариант, известный мне, - бинарное возведение в степень. логарифмическая асимптотика.
BRcr
 Аватар для BRcr
4003 / 2292 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
02.04.2013, 14:03     Быстрое возведение в степень #13
Любопытства ради провел тест на скорость. По убыванию скорости:
  1. библиотечный pow;
  2. через логарифм;
  3. через цикл;
  4. рекурсия.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long double _pow_( double x, double y )
{
    long double res( x );
    while ( --y )
    {
        res *= x;
    }
    return res;
}
long double log_pow( double x, double y )
{
    return exp( y * log( x ) );
}
long double rec_pow( double x, double y )
{
    return y > 0 ? x * rec_pow( x, --y ) : 1;
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    t_time_counter tc;
    long double x = 2, y = 100, res;
    size_t lim = 1000000;
    char y_n;
 
    while ( cin >> y_n, y_n == 'y' )
    {
        tc.start( );
        for ( size_t i = 0; i < lim; ++i )
        {
            res = pow( x, y );
        }
        tc.stop( );
        cout << "pow = \t\t" << res << "\t\t" << tc.get_time_string( ).get( ) << endl;
 
        tc.start( );
        for ( size_t i = 0; i < lim; ++i )
        {
            res = _pow_( x, y );
        }
        tc.stop( );
        cout << "_pow_ = \t" << res << "\t\t" << tc.get_time_string( ).get( ) << endl;
 
        tc.start( );
        for ( size_t i = 0; i < lim; ++i )
        {
            res = log_pow( x, y );
        }
        tc.stop( );
        cout << "log_pow = \t" << res << "\t\t" << tc.get_time_string( ).get( ) << endl;
 
        tc.start( );
        for ( size_t i = 0; i < lim; ++i )
        {
            res = rec_pow( x, y );
        }
        tc.stop( );
        cout << "rec_pow = \t" << res << "\t\t" << tc.get_time_string( ).get( ) << endl;
    }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class t_time_counter
{
public:
    DWORD full_time;
    unsigned int hours, mins, secs, msecs;
    void __fastcall start( ) {
        full_time = GetTickCount( );
    }
    void __fastcall stop( )
    {
        full_time = GetTickCount( ) - full_time;
        hours = ( mins = ( secs = full_time / 1000 ) / 60 ) / 60;
        mins %= 60;
        secs %= 60;
        msecs = full_time % 1000;
    }
    typedef std::auto_ptr <TCHAR> auto_ptr_tchar;
    auto_ptr_tchar __fastcall get_time_string( )
    {
        auto_ptr_tchar ptr( new TCHAR[255] );
        if ( SUCCEEDED(
                StringCchPrintf( ptr.get( ), 255, _T( "h: %u, m: %u, s: %u, ms: %u" ), hours, mins, secs, msecs )
            ) )
        {
            return ptr;
        }
        return auto_ptr_tchar( );
    }
};
Миниатюры
Быстрое возведение в степень  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2014, 07:52     Быстрое возведение в степень
Еще ссылки по теме:

C++ Возведение в степень
C++ Возведение в степень
Возведение в степень C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Fill Filiski
Сообщений: n/a
28.05.2014, 07:52     Быстрое возведение в степень #14
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int vozved (int a, int chislo, int p)
{
    int b;
    int y = 1;
    int t = log2 (chislo);
    for (int i = 0; i < t+1; i++)
    {
        b = chislo % 2;
        chislo = chislo / 2;
        if(b == 1)
        y = y * a;
 
        a = (a * a) % p;
    }
    return y % p;
}
Yandex
Объявления
28.05.2014, 07:52     Быстрое возведение в степень
Ответ Создать тему

Метки
возведение в степень
Опции темы

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