Merge pull request prakhar1989#44 from manishrw/master

prakhar1989 · web-flow · commit 691172d49007 · 2016-10-14T16:32:19.000-04:00
ADDED modular exponentiation in misc
diff --git a/README.md b/README.md
@@ -42,6 +42,7 @@ Completed
   - String Reverse
   - Parenthesis Matching
   - Infix to Postfix
+- Modular exponentiation
 
 
 Tests
@@ -52,3 +53,4 @@ Tests
     python -m tests.heap_test
     python -m tests.unionfind_test
     python -m tests.singly_linked_list_test
+    python -m tests.modular_exponentiation_test
diff --git a/misc/__init__.py b/misc/__init__.py
diff --git a/misc/modular_exponentiation.py b/misc/modular_exponentiation.py
@@ -0,0 +1,22 @@
+"""
+Problem: https://en.wikipedia.org/wiki/Modular_exponentiation
+"""
+
+def modular_exponentiation(base, exp, mod):
+	if exp < 1:
+		raise ValueError("Exponentiation should be ve+ int")
+	if mod == 1:
+		return 0
+	elif mod < 1:
+		raise ValueError("Modulus should be ve+ int")
+	#Initialize result to 1
+	result = 1
+	base %= mod
+	while exp > 0:
+		#multiply base to result if exp is odd
+		if exp % 2 == 1:
+			result = (result * base) % mod
+		#Double base and half exp
+		exp = exp >> 1
+		base = (base ** 2) % mod
+	return result
diff --git a/tests/modular_exponentiation_test.py b/tests/modular_exponentiation_test.py
@@ -0,0 +1,16 @@
+import os, sys
+import unittest
+sys.path.append(os.path.join(os.getcwd(), os.path.pardir))
+from misc import modular_exponentiation as me
+
+class TestLCS(unittest.TestCase):
+    def test_modular_exponentiation(self):
+    	self.assertEqual(me.modular_exponentiation(2, 10, 100), 24)
+    	self.assertEqual(me.modular_exponentiation(2, 200, 10), 6)
+    	self.assertEqual(me.modular_exponentiation(5, 20, 1), 0)
+    	#self.assertEqual(me.modular_exponentiation(8, 1, 10), 8)
+    	self.assertRaises(ValueError, me.modular_exponentiation, 12, -1, 10)
+    	self.assertRaises(ValueError, me.modular_exponentiation, 12, 5, 0)
+
+if __name__ == "__main__":
+    unittest.main()
