Repository: keon/algorithms
Pull request #361 (2018-06-20 20:34:15)

added exponential and some refactors to maths/
- [x] **If creating a new file :**
  - [x] added links to it in the README files ?
  - [x] included tests with it ?
  - [x] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [x] **if done some changes :**
  - [x] wrote short description in the PR explaining what the changes do ?

- removed requirements for testing from `requirements.txt` since tests are no longer included in package. There is no dependencies for this repo as of now (apart from tests).
- removed `prime_check2`. Too similar to `prime_check`
- other refactoring.

coveralls: ## Pull Request Test Coverage Report for [Build 650](https://coveralls.io/builds/17619219)

* **57** of **72**   **(79.17%)**  changed or added relevant lines in **8** files are covered.
* **2** unchanged lines in **2** files lost coverage.
* Overall coverage increased (+**0.1%**) to **71.327%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/maths/nth_digit.py](https://coveralls.io/builds/17619219/source?filename=algorithms%2Fmaths%2Fnth_digit.py#L7) | 0 | 5 | 0.0%
| [algorithms/maths/rsa.py](https://coveralls.io/builds/17619219/source?filename=algorithms%2Fmaths%2Frsa.py#L33) | 0 | 5 | 0.0%
| [algorithms/maths/sqrt_precision_factor.py](https://coveralls.io/builds/17619219/source?filename=algorithms%2Fmaths%2Fsqrt_precision_factor.py#L12) | 0 | 5 | 0.0%
<!-- | **Total:** | **57** | **72** | **79.17%** | -->

|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/maths/nth_digit.py](https://coveralls.io/builds/17619219/source?filename=algorithms%2Fmaths%2Fnth_digit.py#L1) | 1 | 0.0% |
| [algorithms/maths/rsa.py](https://coveralls.io/builds/17619219/source?filename=algorithms%2Fmaths%2Frsa.py#L41) | 1 | 15.38% |
<!-- | **Total:** | **2** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/17619219/badge)](https://coveralls.io/builds/17619219) |
| :-- | --: |
| Change from base [Build 648](https://coveralls.io/builds/17597770): |  0.1% |
| Covered Lines: | 3704 |
| Relevant Lines: | 5193 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/.travis.yml b/.travis.yml
index 1146884..e9a4450 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -12,7 +12,7 @@ matrix:
         - python: 3.6
           env: TOX_ENV=py36
 install:
-    - pip install -r requirements.txt
+    - pip install -r test_requirements.txt
 before_script:
     # stop the build if there are Python syntax errors or undefined names
     - flake8 . --count --select=E901,E999,F821,F822,F823 --show-source --statistics
diff --git a/README.md b/README.md
index 3ba28d0..8228698 100644
--- a/README.md
+++ b/README.md
@@ -187,6 +187,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
+    - [modular_exponential](algorithms/maths/modular_exponential.py)
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
diff --git a/README_CN.md b/README_CN.md
index 42f7b36..99fac2a 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -183,6 +183,7 @@ pip3 uninstall -y algorithms
     - [primes_sieve_of_eratosthenes：埃拉托色尼的质数筛](algorithms/maths/primes_sieve_of_eratosthenes.py)
     - [generate_strobogrammtic：生成对称数](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic：判断对称数](algorithms/maths/is_strobogrammatic.py)
+    - [modular_exponential](algorithms/maths/modular_exponential.py)
     - [nth_digit：第n位](algorithms/maths/nth_digit.py)
     - [rabin_miller：米勒-拉宾素性检验](algorithms/maths/rabin_miller.py)
     - [rsa：rsa加密](algorithms/maths/rsa.py)
diff --git a/README_GE.md b/README_GE.md
index 2760b2c..a8f16ad 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -193,6 +193,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
+    - [modular_exponential](algorithms/maths/modular_exponential.py)
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
diff --git a/README_JP.md b/README_JP.md
index 900f8ee..86453b7 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -187,6 +187,7 @@ if __name__ == "__main__":
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
+    - [modular_exponential](algorithms/maths/modular_exponential.py)
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
diff --git a/README_KR.md b/README_KR.md
index daf7368..ccb7fad 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -184,6 +184,7 @@ if __name__ == "__main__":
     - [gcd/lcm](algorithms/maths/gcd.py)
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
+    - [modular_exponential](algorithms/maths/modular_exponential.py)
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 543d8d3..177fed3 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -5,6 +5,7 @@ from .factorial import *
 from .gcd import *
 from .generate_strobogrammtic import *
 from .is_strobogrammatic import *
+from .modular_exponential import *
 from .next_perfect_square import *
 from .prime_check import *
 from .primes_sieve_of_eratosthenes import *
diff --git a/algorithms/maths/extended_gcd.py b/algorithms/maths/extended_gcd.py
index 96c31ac..83b6578 100644
--- a/algorithms/maths/extended_gcd.py
+++ b/algorithms/maths/extended_gcd.py
@@ -1,11 +1,10 @@
-"""
-extended GCD algorithm
-return s,t,g
-such that a s + b t = GCD(a, b)
-and s and t are coprime
-"""
+def extended_gcd(a, b):
+    """Extended GCD algorithm.
+    Return s, t, g
+    such that a * s + b * t = GCD(a, b)
+    and s and t are co-prime.
+    """
 
-def extended_gcd(a,b):
     old_s, s = 1, 0
     old_t, t = 0, 1
     old_r, r = a, b
diff --git a/algorithms/maths/factorial.py b/algorithms/maths/factorial.py
index 2cd1a34..23e1f53 100644
--- a/algorithms/maths/factorial.py
+++ b/algorithms/maths/factorial.py
@@ -1,20 +1,32 @@
-#
-# This function calculates n!
-# Factorial function not works in less than 0
-#
-
-def factorial(n):
-
+def factorial(n, mod=None):
+    """Calculates factorial iteratively.
+    If mod is not None, then return (n! % mod)
+    Time Complexity - O(n)"""
+    if not (isinstance(n, int) and n >= 0):
+        raise ValueError("'n' must be a non-negative integer.")
+    if mod is not None and not (isinstance(mod, int) and mod > 0):
+        raise ValueError("'mod' must be a positive integer")
     result = 1
+    if n == 0:
+        return 1
     for i in range(2, n+1):
         result *= i
-
+        if mod:
+            result %= mod
     return result
 
 
-def factorial_recur(n):
+def factorial_recur(n, mod=None):
+    """Calculates factorial recursively.
+    If mod is not None, then return (n! % mod)
+    Time Complexity - O(n)"""
+    if not (isinstance(n, int) and n >= 0):
+        raise ValueError("'n' must be a non-negative integer.")
+    if mod is not None and not (isinstance(mod, int) and mod > 0):
+        raise ValueError("'mod' must be a positive integer")
     if n == 0:
         return 1
-    
-    return n * factorial(n-1)
-    
+    result = n * factorial(n - 1, mod)
+    if mod:
+        result %= mod
+    return result
diff --git a/algorithms/maths/modular_exponential.py b/algorithms/maths/modular_exponential.py
new file mode 100644
index 0000000..f0e58de
--- /dev/null
+++ b/algorithms/maths/modular_exponential.py
@@ -0,0 +1,18 @@
+def modular_exponential(base, exponent, mod):
+    """Computes (base ^ exponent) % mod.
+    Time complexity - O(log n)
+    Use similar to Python in-built function pow."""
+    if exponent < 0:
+        raise ValueError("Exponent must be positive.")
+    base %= mod
+    result = 1
+
+    while exponent > 0:
+        # If the last bit is 1, add 2^k.
+        if exponent & 1:
+            result = (result * base) % mod
+        exponent = exponent >> 1
+        # Utilize modular multiplication properties to combine the computed mod C values.
+        base = (base * base) % mod
+
+    return result
diff --git a/algorithms/maths/nth_digit.py b/algorithms/maths/nth_digit.py
index ea2d681..381926f 100644
--- a/algorithms/maths/nth_digit.py
+++ b/algorithms/maths/nth_digit.py
@@ -1,20 +1,17 @@
-"""
-find nth digit
-1. find the length of the number where the nth digit is from.
-2. find the actual number where the nth digit is from
-3. find the nth digit and return
-"""
-
-
 def find_nth_digit(n):
-    len = 1
+    """find the nth digit of given number.
+    1. find the length of the number where the nth digit is from.
+    2. find the actual number where the nth digit is from
+    3. find the nth digit and return
+    """
+    length = 1
     count = 9
     start = 1
-    while n > len * count:
-        n -= len * count
-        len += 1
+    while n > length * count:
+        n -= length * count
+        length += 1
         count *= 10
         start *= 10
-    start += (n-1) / len
+    start += (n-1) / length
     s = str(start)
-    return int(s[(n-1) % len])
\ No newline at end of file
+    return int(s[(n-1) % length])
\ No newline at end of file
diff --git a/algorithms/maths/prime_check.py b/algorithms/maths/prime_check.py
index 1821d25..60e4427 100644
--- a/algorithms/maths/prime_check.py
+++ b/algorithms/maths/prime_check.py
@@ -1,8 +1,8 @@
-"""
-prime_test(n) returns a True if n is a prime number else it returns False
-"""
-
 def prime_check(n):
+    """Return True if n is a prime number
+    Else return False.
+    """
+
     if n <= 1:
         return False
     if n == 2 or n == 3:
@@ -15,22 +15,3 @@ def prime_check(n):
             return False
         j += 6
     return True
-
-
-def prime_check2(n):
-    # prime numbers are greater than 1
-    if n > 1:
-        # check for factors
-        for i in range(2, int(n ** 0.5) + 1):
-            if (n % i) == 0:
-                # print(num, "is not a prime number")
-                # print(i, "times", num//i, "is", num)
-                return False
-
-        # print(num, "is a prime number")
-        return True
-
-    # if input number is less than
-    # or equal to 1, it is not prime
-    else:
-        return False
diff --git a/algorithms/maths/primes_sieve_of_eratosthenes.py b/algorithms/maths/primes_sieve_of_eratosthenes.py
index 1677b25..7c21c6d 100644
--- a/algorithms/maths/primes_sieve_of_eratosthenes.py
+++ b/algorithms/maths/primes_sieve_of_eratosthenes.py
@@ -1,11 +1,12 @@
-'''
-Using sieve of Eratosthenes, primes(x) returns list of all primes less than x
+"""
+Return list of all primes less than n,
+Using sieve of Eratosthenes.
 
 Modification:
 We don't need to check all even numbers, we can make the sieve excluding even
 numbers and adding 2 to the primes list by default.
 
-We are going to make an array of: x / 2 - 1 if number is even, else x / 2 
+We are going to make an array of: x / 2 - 1 if number is even, else x / 2
 (The -1 with even number it's to exclude the number itself)
 Because we just need numbers [from 3..x if x is odd]
 
@@ -21,20 +22,25 @@ For x = 11:
 
 With this, we have reduced the array size to a half,
 and complexity it's also a half now.
-'''
+"""
 
-def primes(x):
-    assert(x >= 0)
+
+def get_primes(n):
+    """Return list of all primes less than n,
+    Using sieve of Eratosthenes.
+    """
+    if n <= 0:
+        raise ValueError("'n' must be a positive integer.")
     # If x is even, exclude x from list (-1):
-    sieve_size = (x//2 - 1) if x % 2 == 0 else (x//2)
-    sieve = [1 for v in range(sieve_size)]   # Sieve
-    primes = []                              # List of Primes
-    if x >= 2:
-        primes.append(2)                     # Add 2 by default
+    sieve_size = (n // 2 - 1) if n % 2 == 0 else (n // 2)
+    sieve = [True for _ in range(sieve_size)]   # Sieve
+    primes = []      # List of Primes
+    if n >= 2:
+        primes.append(2)      # 2 is prime by default
     for i in range(sieve_size):
-        if sieve[i] == 1:
+        if sieve[i]:
             value_at_i = i*2 + 3
             primes.append(value_at_i)
             for j in range(i, sieve_size, value_at_i):
-                sieve[j] = 0
+                sieve[j] = False
     return primes
diff --git a/algorithms/maths/rsa.py b/algorithms/maths/rsa.py
index e3f2995..70b7bc5 100644
--- a/algorithms/maths/rsa.py
+++ b/algorithms/maths/rsa.py
@@ -24,21 +24,20 @@ a number very quickly:
 import random
 
 
-def modinv(a, m):
-    """calculate the inverse of a mod m
-    that is, find b such that (a * b) % m == 1"""
-    b = 1
-    while not (a * b) % m == 1:
-        b += 1
-    return b
-
-
 def generate_key(k, seed=None):
     """
     the RSA key generating algorithm
     k is the number of bits in n
     """
 
+    def modinv(a, m):
+        """calculate the inverse of a mod m
+        that is, find b such that (a * b) % m == 1"""
+        b = 1
+        while not (a * b) % m == 1:
+            b += 1
+        return b
+
     def gen_prime(k, seed=None):
         """generate a prime with k bits"""
 
diff --git a/algorithms/maths/sqrt_precision_factor.py b/algorithms/maths/sqrt_precision_factor.py
index ce4f0cf..bb47c09 100644
--- a/algorithms/maths/sqrt_precision_factor.py
+++ b/algorithms/maths/sqrt_precision_factor.py
@@ -1,17 +1,19 @@
 """
 Given a positive integer N and a precision factor P,
-write a square root function that produce an output
+it produces an output
 with a maximum error P from the actual square root of N.
 
 Example:
-Given N = 5 and P = 0.001, can produce output O such that
-2.235 < O > 2.237. Actual square root of 5 being 2.236.
+Given N = 5 and P = 0.001, can produce output x such that
+2.235 < x < 2.237. Actual square root of 5 being 2.236.
 """
 
-def square_root(n,p):
-	guess = float(n) / 2
 
-	while abs(guess * guess - n) > p:
-		guess = (guess + (n / guess)) / 2
+def square_root(n, epsilon=0.001):
+    """Return square root of n, with maximum absolute error epsilon"""
+    guess = n / 2
 
-	return guess
+    while abs(guess * guess - n) > epsilon:
+        guess = (guess + (n / guess)) / 2
+
+    return guess
diff --git a/requirements.txt b/requirements.txt
index 7a3e47c..e69de29 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -1,6 +0,0 @@
-flake8
-python-coveralls
-coverage
-nose
-pytest
-tox


Test patch:
diff --git a/test_requirements.txt b/test_requirements.txt
new file mode 100644
index 0000000..7a3e47c
--- /dev/null
+++ b/test_requirements.txt
@@ -0,0 +1,6 @@
+flake8
+python-coveralls
+coverage
+nose
+pytest
+tox
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 9270c28..2499a4f 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -6,12 +6,13 @@ from algorithms.maths import (
     gcd, lcm,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
+    modular_exponential,
     find_next_square, find_next_square2,
-    prime_check, prime_check2,
-    primes,
+    prime_check,
+    get_primes,
     pythagoras,
     is_prime,
-    encrypt, decrypt, generate_key,
+    encrypt, decrypt,
     combination, combination_memo
 )
 
@@ -46,9 +47,12 @@ class TestDecimalToBinaryIP(unittest.TestCase):
     """
 
     def test_decimal_to_binary_ip(self):
-        self.assertEqual("00000000.00000000.00000000.00000000", decimal_to_binary_ip("0.0.0.0"))
-        self.assertEqual("11111111.11111111.11111111.11111111", decimal_to_binary_ip("255.255.255.255"))
-        self.assertEqual("11000000.10101000.00000000.00000001", decimal_to_binary_ip("192.168.0.1"))
+        self.assertEqual("00000000.00000000.00000000.00000000",
+                         decimal_to_binary_ip("0.0.0.0"))
+        self.assertEqual("11111111.11111111.11111111.11111111",
+                         decimal_to_binary_ip("255.255.255.255"))
+        self.assertEqual("11000000.10101000.00000000.00000001",
+                         decimal_to_binary_ip("192.168.0.1"))
 
 
 class TestExtendedGcd(unittest.TestCase):
@@ -112,6 +116,22 @@ class TestIsStrobogrammatic(unittest.TestCase):
         self.assertFalse(is_strobogrammatic2("14"))
 
 
+class TestModularExponential(unittest.TestCase):
+    """[summary]
+    Test for the file modular_Exponential.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_modular_exponential(self):
+        self.assertEqual(1, modular_exponential(5, 117, 19))
+        self.assertEqual(pow(1243, 65321, 10**9 + 7),
+                         modular_exponential(1243, 65321, 10**9 + 7))
+        self.assertEqual(1, modular_exponential(12, 0, 78))
+        self.assertRaises(ValueError, modular_exponential, 12, -2, 455)
+
+
 class TestNextPerfectSquare(unittest.TestCase):
     """[summary]
     Test for the file next_perfect_square.py
@@ -138,7 +158,8 @@ class TestPrimesSieveOfEratosthenes(unittest.TestCase):
     """
 
     def test_primes(self):
-        self.assertEqual([2, 3, 5, 7], primes(7))
+        self.assertListEqual([2, 3, 5, 7], get_primes(7))
+        self.assertRaises(ValueError, get_primes, -42)
 
 
 class TestPrimeTest(unittest.TestCase):
@@ -160,17 +181,6 @@ class TestPrimeTest(unittest.TestCase):
                 counter += 1
         self.assertEqual(25, counter)
 
-    def test_prime_test2(self):
-        """
-            checks all prime numbers between 2 up to 100.
-            Between 2 up to 100 exists 25 prime numbers!
-        """
-        counter = 0
-        for i in range(2, 101):
-            if prime_check2(i):
-                counter += 1
-        self.assertEqual(25, counter)
-
 
 class TestPythagoras(unittest.TestCase):
     """[summary]
@@ -219,6 +229,7 @@ class TestRSA(unittest.TestCase):
     #         dec = decrypt(en, d, n)
     #         self.assertEqual(data,dec)
 
+
 class TestCombination(unittest.TestCase):
     """[summary]
     Test for the file combination.py
@@ -230,9 +241,12 @@ class TestCombination(unittest.TestCase):
     def test_combination(self):
         self.assertEqual(10, combination(5, 2))
         self.assertEqual(252, combination(10, 5))
+
     def test_combination_memo(self):
         self.assertEqual(10272278170, combination_memo(50, 10))
         self.assertEqual(847660528, combination_memo(40, 10))
+
+
 class TestFactorial(unittest.TestCase):
     """[summary]
     Test for the file factorial.py
@@ -245,13 +259,19 @@ class TestFactorial(unittest.TestCase):
         self.assertEqual(1, factorial(0))
         self.assertEqual(120, factorial(5))
         self.assertEqual(3628800, factorial(10))
-        
+        self.assertEqual(637816310, factorial(34521, 10**9 + 7))
+        self.assertRaises(ValueError, factorial, -42)
+        self.assertRaises(ValueError, factorial, 42, -1)
+
     def test_factorial_recur(self):
         self.assertEqual(1, factorial_recur(0))
         self.assertEqual(120, factorial_recur(5))
         self.assertEqual(3628800, factorial_recur(10))
-        
+        self.assertEqual(637816310, factorial_recur(34521, 10**9 + 7))
+        self.assertRaises(ValueError, factorial_recur, -42)
+        self.assertRaises(ValueError, factorial_recur, 42, -1)
+
+
 if __name__ == "__main__":
     unittest.main()
-    
-    
+