Понимание алгоритма быстрого возведения в степень и теоремы по модулю

алгоритм

Я сегодня выучил еще один алгоритм.У меня ушло два часа, чтобы понять его с перерывами.Я должен вздохнуть.Алгоритм действительно слишком силен,и он упрощает слишком много шагов.Слишком силен,слишком силен,слишком силен?

Прежде всего, давайте поговорим о том, какую проблему решает быстрое питание. Основная проблема состоит в том, чтобы решить проблему «невыносимых чисел» для компьютеров. Представьте себе сценарий. Если вас просят рассчитать21202^{120}из后三位的值, что бы вы сделали? Может быть, вы скажете так просто, независимо от того, является ли ваше решение сложным расчетом, умным расчетом или разумным расчетом. Пожалуйста, выслушайте меня подробно:

1. Жесткий расчет степенной функции

Жесткий код расчета с использованием функции pow выглядит следующим образом:

#include<cmath>
int main(){
    long long int x;
    x = pow(2,120);
    cout<<x<<endl;
  	cout<<x%1000<<endl;
    return 1;
}

// 打印
// -9223372036854775808
// -808

Ха, почему такой результат? Затем поговорим о размере типа данных int, подробнее см. в этой статье. В 64-разрядных компиляторах тип int обычно занимает 4 байта, а тип long long int — 8. За исключением первого бита символа, максимальный допустимый размер составляет28*8−1−1=92233720368547758072^{8*8-1}-1=9223372036854775807,и21202^{120}Это намного больше, чем это число, поэтому измученный компьютер не может его сосчитать, не говоря уже о том, как сосчитать его последние три цифры.

Давайте улучшим его, используя волну теоремы по модулю для оптимизации оптимизации

2. Теорема по модулю

Проблема в том, что результат умножения нескольких больших чисел, решаемый операцией по модулю, слишком велик (компьютер его не поддерживает) и не может принять последние несколько цифр. Это также первый раз, когда я услышал теорему по модулю. Прочитав ее, Я обнаружил, что это настоящая корова — это математическая теорема. Я не буду здесь вдаваться в подробности, подробнее см. в моей ==другой статье==, конкретное содержание теоремы по модулю:

(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p ) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）

Просто посмотрите на (3) здесь,(a * b) % p = (a%p * b%p) % p, это здорово, по модулю произведение равно произведению по модулю каждого множителя, а дальше берется по модулю, что равносильно контролю числа до p-1 бит, количество вычислений супер мало, есть лес~

Код с использованием операции по модулю:

int main(){
    long long int result=1;
//    x = pow(2,120);
    clock_t start_time = clock();
    for(int i=0;i<120;++i){
        result = result*2%1000;
    }
  	result = result % 1000;
  
    clock_t end_time = clock();
    cout<<result<<endl;
    cout<<"计算花费时间："<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl;
  	// start_time和end_time的差值计算的是 CPU 运行程序所花费的时钟单元数量，然后在除以CLOCK_PER_SEC（是：CPU 每秒有多少时钟单元数。）
    return 1;
}

// 打印
// 576
// 计算花费时间3e-06

Эта скорость слишком 6, а результат все равно вычисляется. Математическая теорема действительно слишком сильна. Я всегда любил ее ?, хотя самый главный тест в жизни - это тест по математике.

Почувствуйте силу математических теорем, но достаточно ли этого? Теорема по модулю только контролирует данные в пределах определенного количества цифр, так что число можно вычислить, но это не упрощает количество вычислений (все равно в 120 раз) Лучше бы был алгоритм, упрощающий вычисление шаги. Как говорится, нет самого быстрого, есть только быстрее?, если есть сегодняшний герой, пожалуйста, сократите количество вычисленийалгоритм быстрого возведения в степеньПоявляется:

3. Интеллектуальный расчет алгоритма Fast Power

Когда я увидел объяснение этого алгоритма, я встал, как будто увидел новый мир, манящий меня, то есть алгоритм. Алгоритм действительно силен, он может упростить сложную проблему до маленьких задач и решать их в цикле, а скорость очень высока.

Ну, хватит ерунды, пиши по делу. Прежде всего, я пишу статьи, чтобы упражнять свои писательские способности и углублять свое понимание знаний.Может быть, мое объяснение неясно. Если вы не понимаете, вы можете прочитать справочную статью внизу статьи, написанную большим парнем.алгоритм быстрого возведения в степеньДля получения более подробной информации вы можете перейти, чтобы увидеть, если вам это нужно.

3.1 Что такое алгоритм быстрого возведения в степень?

Алгоритм быстрого возведения в степень, также известный как двоичное возведение в степень, может значительно сократить этапы вычислений и повысить скорость работы.lognlog_nмаленькие хитрости, чтобы вычислить вовремя, в то время как расчеты грубой силы требуютnnвремя.

3.2 Описание алгоритма

Например, мы вычисляем:ana^n, что эквивалентноan1*an2……*ansа^{n1}*а^{n2}……*а^{ns},вn=n1+n2+......+nsn = n1 + n2 +......+ ns. Но когда n очень велико, объем вычислений очень велик, так называемый «экспоненциальный взрыв». Здесь мы можем упростить,a2b=(ab)2a^{2b}=({a^b})^2, объем вычислений мал в одно мгновение, например:2400=4200=16100=……2^{400}=4^{200}=16^{100}=…, расчет на 200 шагов меньше, 300 шагов..., эффективности нет.

Зная, что взятие квадрата может сократить количество вычислений, мы можем следоватьбинарныйпредставлять власть. Тогда давайте посмотрим на взаимосвязь между мощностью и двоичным числом или приведем пример для объяснения: Например:313=3(1101)2=38*34*313^{13}=3^{(1101)_2}=3^8*3^4*3^1.

Вы обнаружили, что есть толькодвоичный битЕсли он равен 1, он будет умножен на него, а если равен 0, то будет пропущен. Таким образом, нам нужно только использовать метод преобразования из десятичного числа в двоичное (непрерывно делить остаток от 2 до тех пор, пока частное не станет равным 0), чтобы получить двоичное число, соответствующее степени. Если двоичная цифра равна 1, умножьте соответствующее число на результат и удвойте основание; если это 0, удвойте основание. Вы можете посмотреть на процесс деривации ниже, Это место немного запутанно, и вы поймете это, пройдя по нему.

# 1、指数(power)13 对一个二进制，底数(base)为3
13/2 = 6 余1	# base变成3*3=9   result=result*3,base=base*base
6/2 = 3 余0	# base变成9*9=81	base=base*base
3/2 = 1 余1	# base变成81*81=6561	result=result*3,base=base*base
1/2 = 0 余1	# base变成6561*6561	result=result*3,base=base*base
# 所以对应的二进制是 1101

# 2、对应计算代码 Python
def quick(base, power):
    result = 1
    b = power
    while(b>0):
        if b&1:   # 相当于是if b%2 == 1:  为奇数
            result = result * base
        base = base * base
        b >>= 1      # 相当于是 b = b/2    b取一半
    print(result)

quick(3, 13)

# 打印
# 1594323

Вы думали, что это конец? Есть еще один шаг, быстрая мощность только сокращает количество вычислений, но не решает проблему вычисления последних трех цифр высокой мощности (таких как:21202^{120}). Вы можете подумать, что если вы добавите предыдущую операцию по модулю, это уменьшит число, и вы сможете вычислить результат.

Правильно, вот и все, алгоритм быстрого возведения в степень + теорема по модулю - идеальное совпадение cp, вот волна кода на С++:

#include<iostream>
#include<ctime>
using namespace std;

int main(){
    long long int result=1;
    int base = 2,power=120;
    clock_t start_time = clock();
    while(power>0){
        if(power & 1){
            result = result*base%1000;
        }
        base = (base*base)%1000;
        power >>= 1;
    }
  	result = result%1000;
  	
    clock_t end_time = clock();
    cout<<result<<endl;
    cout<<"计算花费时间："<<double(end_time - start_time)/CLOCKS_PER_SEC<<endl;
    cout<<"CPU每秒时钟数："<<CLOCKS_PER_SEC<<endl;
    return 1;
}

// 打印
// 576
// 计算花费时间：1e-06
// CPU每秒时钟数：1000000

Вау, я наконец закончила писать, у меня голова болит ?~

Суммировать:

Алгоритм действительно сильный, а эффективность очень высокая, мне он нравится, и я усердно работаю над его изучением~

Справочная статья:

blog.CSDN.net/QQ_19782019…

ОИ-wiki.org/math/quick-…

Категории