[FEATURE REQUEST] <Optimizing Power (base^exponent)%mod using Binary Exponentiation Algorithm>

[razat-thapar]

What would you like to Propose?

New Algorithm under https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/

File Name: PowerUsingBinaryExponentiation.java What ?
To calculate long pow(int base, int exponent, int mod) , where mod is a prime number to avoid long overflow issues. Why ?
Brute-force approach proposed in /maths/PowerUsingRecursion.java takes Time complexity : O(exponent) time. Binary Exponentiation algorithm takes Time Complexity : O(log(exponent)) time , Aux-Space Complexity: O(log(exponent))

Issue details

Link for Algorithm:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring How ? Recursive Approach: TC: O(log(exponent)) SC: O(log(exponent))

public long pow(int base, int exponent, int mod){
        //assumption : given base, exponent, mod, return base^exponent %mod. 
        if(exponent==0){
            return 1%mod;
        }
        //store power
        long p = pow(base,exponent/2,mod);
        if(exponent%2==0){
            //even exponent
            return (p*p)%C;
        }else{
            //odd exponent 
            if(base<0){
                //handle -ve remainder in java due to -ve base.
                return ( ((p*p)%mod) * (mod+ (base%mod)))%mod;
            }else{
                return (((p*p)%mod) * (base%mod))%mod;
            }
        }
    }

Additional Information

No response

[razat-thapar]

I want to work on this ! Please don't assign it to someone else!

[SkSadaf]

I've added PowerUsingBinaryExponentiation.java to my pull request titled "Introducing Binary Exponentiation Algorithm #4428. Your feedback is greatly appreciated. Please review it. Thanks!

[razat-thapar]

I've added PowerUsingBinaryExponentiation.java to my pull request titled "Introducing Binary Exponentiation Algorithm #4428. Your feedback is greatly appreciated. Please review it. Thanks!

I pointed this out and proposed my algorithm to the maintainers. I should only do it . 🙄 You can try figuring out other new issues. I am also a contributor just like you!

[SkSadaf]

I'm new to open-source contributions, and I didn't fully understand the process. Sorry about that.

[sigma390]

is it solved or not?

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

[github-actions[bot]]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!