Repository: keon/algorithms
Pull request #687 (2020-08-14 17:35:56)

Add binary exponentiation

ericklarac: @IhebHaboubi could you add some tests, please?
ericklarac: @IhebHaboubi Also add the link on README.md to the file
ericklarac: @IhebHaboubi nice first-time contribution.

Patch:
diff --git a/README.md b/README.md
index c1b3692..f06cbf1 100644
--- a/README.md
+++ b/README.md
@@ -198,6 +198,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [is_isomorphic](algorithms/map/is_isomorphic.py)
     - [is_anagram](algorithms/map/is_anagram.py)    
 - [maths](algorithms/maths)
+    - [power](algorithms/maths/power.py)
     - [base_conversion](algorithms/maths/base_conversion.py)
     - [combination](algorithms/maths/combination.py)
     - [cosine_similarity](algorithms/maths/cosine_similarity.py)
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 7b8a7b1..678d923 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -18,3 +18,4 @@ from .cosine_similarity import *
 from .find_order_simple import *
 from .find_primitive_root_simple import *
 from .diffie_hellman_key_exchange import *
+from .power import *
diff --git a/algorithms/maths/power.py b/algorithms/maths/power.py
new file mode 100644
index 0000000..99e694f
--- /dev/null
+++ b/algorithms/maths/power.py
@@ -0,0 +1,45 @@
+def power(a: int, n: int, r: int = None):
+    """
+    Iterative version of binary exponentiation
+    
+    Calculate a ^ n
+    if r is specified, return the result modulo r
+    
+    Time Complexity :  O(log(n))
+    Space Complexity : O(1)
+    """
+    ans = 1
+    while n:
+        if n & 1:
+            ans = ans * a
+        a = a * a
+        if r:
+            ans %= r
+            a %= r
+        n >>= 1
+    return ans
+
+
+def power_recur(a: int, n: int, r: int = None):
+    """
+    Recursive version of binary exponentiation
+    
+    Calculate a ^ n
+    if r is specified, return the result modulo r
+    
+    Time Complexity :  O(log(n))
+    Space Complexity : O(log(n))
+    """
+    if n == 0:
+        ans = 1
+    elif n == 1:
+        ans = a
+    else:
+        ans = power_recur(a, n // 2, r)
+        ans = ans * ans
+        if n % 2:
+            ans = ans * a
+    if r:
+        ans %= r
+    return ans
+


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index c29a866..a79c690 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -1,4 +1,5 @@
 from algorithms.maths import (
+    power,power_recur,
     int_to_base, base_to_int,
     decimal_to_binary_ip,
     euler_totient,
@@ -25,6 +26,27 @@ from algorithms.maths import (
 import unittest
 
 
+class TestPower(unittest.TestCase):
+    """
+    Test for the file power.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_power(self):
+        self.assertEqual(8, power(2, 3))
+        self.assertEqual(1, power(5, 0))
+        self.assertEqual(0, power(10, 3, 5))
+        self.assertEqual(280380, power(2265, 1664,465465))
+
+    def test_power_recur(self):
+        self.assertEqual(8, power_recur(2, 3))
+        self.assertEqual(1, power_recur(5, 0))
+        self.assertEqual(0, power_recur(10, 3, 5))
+        self.assertEqual(280380, power_recur(2265, 1664,465465))
+
+
 class TestBaseConversion(unittest.TestCase):
     """
     Test for the file base_conversion.py