当前位置:网站首页>How to carry out modular power operation efficiently

How to carry out modular power operation efficiently

2020-11-09 19:33:00 labuladong,

After reading this article , You can go and get the following questions :

372. Super power

-----------

Today, let's talk about a topic related to mathematical operations ,LeetCode 372 topic Super Pow, Let you do a huge power operation , Then find the remainder .

int superPow(int a, vector<int>& b);

Ask your algorithm to return power operations a^b The calculation results of 1337 modulus (mod, That's the remainder ) After the results of the . You have to calculate the power first a^b, But this b It will be very big. , therefore b In the form of an array .

This algorithm is actually a modular power algorithm widely used in discrete mathematics , As for why we should be right 1337 We don't care , There are three difficulties in this problem alone :

One is how to deal with indexes represented by arrays , Now? b Is an array , in other words b It can be very large , There's no way to go straight to integer , Otherwise, it may overflow . How do you use this array as an index , Do the calculation ?

The second is how to get the result after module ? According to the truth , At least we should calculate the result of power operation first , Then I do % 1337 This operation . But the problem is , Exponentiation you know , The real results are bound to be terrifying , in other words , There is no way to show the true result , It's a long time ago .

Third, how to perform power operation efficiently , There are also algorithmic skills in power operation , If you don't understand the algorithm , I'll explain later .

So for these questions , Let's think separately , Break one by one .

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

How to deal with array index

First of all, clarify the problem : Now? b Is an array , It can't be expressed as an integer , And the characteristic of array is random access , Deleting the last element is more efficient .

Don't consider the requirement of module , With b = [1,5,6,4] For example , The law of exponentiation , We can find such a law :

See this , Our old readers must have been acutely aware of , This is the sign of recursion ! Because the scale of the problem has shrunk :

    superPow(a, [1,5,6,4])
=>  superPow(a, [1,5,6])

that , Found this Law , We can simply translate the code framework first :

//  Calculation  a  Of  k  Result of the power 
//  We will implement it manually later 
int mypow(int a, int k);

int superPow(int a, vector<int>& b) {
    //  Recursive  base case
    if (b.empty()) return 1;
    //  Take out the last number 
    int last = b.back();
    b.pop_back();
    //  Simplify the original problem , Reduce the scale recursively solve 
    int part1 = mypow(a, last);
    int part2 = mypow(superPow(a, b), 10);
    //  Merge the results 
    return part1 * part2;
}

Come here , It's not hard to understand ! We have solved b It's an array problem , Now let's see how to deal with mod, Avoid integer overflow caused by too large result .

How to deal with it mod operation

First of all, clarify the problem : Because of the way computers code , Form like (a * b) % base Operations like this , The result of multiplication can lead to overflow , We hope to find a skill , Can simplify this expression , Avoid spillovers and get results .

For example, in binary search , Let's use (l+r)/2 Turn it into l+(r-l)/2, Avoid spillovers and get the right results .

that , Let's talk about the technique of modular operation , After all, modular operations are more common in algorithms :

(a * b) % k = (a % k)(b % k) % k

The proof is simple , hypothesis :

a = Ak +B;b = Ck + D

among A,B,C,D It's an arbitrary constant , that :

ab = ACk^2 + ADk + BCk +BD

ab % k = BD % k

Again because :

a % k = B;b % k = D

therefore :

(a % k)(b % k) % k = BD % k

Sum up , Then we can get the equation that we simplify the module .

let me put it another way , Module the result of multiplication , It's equivalent to first modulus every factor , And then we can get the modulus of the result of factor multiplication .

So extend to this question , To find the power of a number is not to multiply the number ? So just expand the ideas just now , You can modulo a power operation :

int base = 1337;
//  Calculation  a  Of  k  Then the power and  base  The result of module 
int mypow(int a, int k) {
    //  To model a factor 
    a %= base;
    int res = 1;
    for (int _ = 0; _ < k; _++) {
        //  There's multiplication , It's a potential spillover point 
        res *= a;
        //  Module the result of multiplication 
        res %= base;
    }
    return res;
}

int superPow(int a, vector<int>& b) {
    if (b.empty()) return 1;
    int last = b.back();
    b.pop_back();
    
    int part1 = mypow(a, last);
    int part2 = mypow(superPow(a, b), 10);
    //  Modules are required for every multiplication 
    return (part1 * part2) % base;
}

You see , First pair factor a modulus , And then every time I do the multiplication res modulus , This ensures res *= a When the code is executed, both factors are less than base Of , It will not cause overflow , At the same time, the result is correct .

thus , This problem has been completely solved , You can pass LeetCode The question system of .

But some readers may ask , Is this algorithm for power so simple , Direct one for Cycle and multiply ? Will it be more complicated , Is there a more efficient algorithm ?

There are more efficient algorithms , But in this case alone , That's enough .

Because you think about , call mypow Function passed in k How big... At most ?k But is b A number in an array , That is to say 0 To 9 Between , So it can be said that every call here mypow The complexity of time is O(1). The time complexity of the whole algorithm is O(N),N by b The length of .

But when it comes to power operations , Let's say by the way how to calculate power operation efficiently .

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

How to find power efficiently

There is more than one algorithm for fast exponentiation , Let's talk about a basic idea we should master . Using the properties of power operation , We can write such a recursion :

This idea is definitely better than using it directly for It's efficient to find the power of a cycle , Because there is an opportunity to directly scale the problem (b Size ) Cut it in half , The complexity of the algorithm must be log The magnitude of .

Then you can modify the previous mypow function , Translate this recursive formula , Plus the modular operation :

int base = 1337;

int mypow(int a, int k) {
    if (k == 0) return 1;
    a %= base;

    if (k % 2 == 1) {
        // k  Is odd 
        return (a * mypow(a, k - 1)) % base;
    } else {
        // k  It's even 
        int sub = mypow(a, k / 2);
        return (sub * sub) % base;
    }
}

Although for the subject , There is no obvious efficiency improvement in this optimization , But the power algorithm has been upgraded , In the future, if someone asks you to write a power algorithm , At least write the algorithm .

thus ,Super Pow Even if it's completely solved , Including the idea of recursion and the processing of modular operations 、 The skill of power operation , It can be said that this topic is quite interesting , What interesting topic do you have , May as well leave a message to share .

_____________

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ! Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢