added exponential and some refactors to maths/ (keon#361)

goswami-rahul · Hai Hoang Dang · commit 447e02d9d89b · 2018-06-21T14:51:23.000-07:00
* added maths/modular_exponential.py and tests

* cleared the requirements.txt

* refactor math/factorial

* refactor prime_check and sieve

* added test_requirements.txt for travis
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -5,6 +5,7 @@
 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
@@ -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
@@ -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
@@ -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
@@ -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])
+    return int(s[(n-1) % length])
diff --git 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
@@ -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 @@
 
 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
@@ -24,21 +24,20 @@
 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
@@ -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
@@ -1,6 +0,0 @@
-flake8
-python-coveralls
-coverage
-nose
-pytest
-tox
diff --git a/test_requirements.txt 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
