TheAlgorithms · dhruvmanila · Nov 29, 2020 · Nov 29, 2020 · Nov 29, 2020 · Nov 29, 2020
diff --git a/blockchain/chinese_remainder_theorem.py b/blockchain/chinese_remainder_theorem.py
@@ -1,18 +1,21 @@
-# Chinese Remainder Theorem:
-# GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )
+"""
+Chinese Remainder Theorem:
+GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )
 
-# If GCD(a,b) = 1, then for any remainder ra modulo a and any remainder rb modulo b
-# there exists integer n, such that n = ra (mod a) and n = ra(mod b).  If n1 and n2 are
-# two such integers, then n1=n2(mod ab)
+If GCD(a,b) = 1, then for any remainder ra modulo a and any remainder rb modulo b
+there exists integer n, such that n = ra (mod a) and n = ra(mod b).  If n1 and n2 are
+two such integers, then n1=n2(mod ab)
 
-# Algorithm :
+Algorithm :
 
-# 1. Use extended euclid algorithm to find x,y such that a*x + b*y = 1
-# 2. Take n = ra*by + rb*ax
+1. Use extended euclid algorithm to find x,y such that a*x + b*y = 1
+2. Take n = ra*by + rb*ax
+"""
+from typing import Tuple
 
 
 # Extended Euclid
-def extended_euclid(a: int, b: int) -> (int, int):
+def extended_euclid(a: int, b: int) -> Tuple[int, int]:
     """
     >>> extended_euclid(10, 6)
     (-1, 2)

diff --git a/blockchain/diophantine_equation.py b/blockchain/diophantine_equation.py
@@ -1,12 +1,14 @@
-# Diophantine Equation : Given integers a,b,c ( at least one of a and b != 0), the
-# diophantine equation a*x + b*y = c has a solution (where x and y are integers)
-# iff gcd(a,b) divides c.
+from typing import Tuple
 
-# GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )
 
-
-def diophantine(a: int, b: int, c: int) -> (int, int):
+def diophantine(a: int, b: int, c: int) -> Tuple[float, float]:
     """
+    Diophantine Equation : Given integers a,b,c ( at least one of a and b != 0), the
+    diophantine equation a*x + b*y = c has a solution (where x and y are integers)
+    iff gcd(a,b) divides c.
+
+    GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )
+
     >>> diophantine(10,6,14)
     (-7.0, 14.0)
 
@@ -26,19 +28,19 @@ def diophantine(a: int, b: int, c: int) -> (int, int):
     return (r * x, r * y)
 
 
-# Lemma : if n|ab and gcd(a,n) = 1, then n|b.
-
-# Finding All solutions of Diophantine Equations:
+def diophantine_all_soln(a: int, b: int, c: int, n: int = 2) -> None:
+    """
+    Lemma : if n|ab and gcd(a,n) = 1, then n|b.
 
-# Theorem : Let gcd(a,b) = d, a = d*p, b = d*q. If (x0,y0) is a solution of Diophantine
-# Equation a*x + b*y = c.  a*x0 + b*y0 = c, then all the solutions have the form
-# a(x0 + t*q) + b(y0 - t*p) = c, where t is an arbitrary integer.
+    Finding All solutions of Diophantine Equations:
 
-# n is the number of solution you want, n = 2 by default
+    Theorem : Let gcd(a,b) = d, a = d*p, b = d*q. If (x0,y0) is a solution of
+    Diophantine Equation a*x + b*y = c.  a*x0 + b*y0 = c, then all the
+    solutions have the form a(x0 + t*q) + b(y0 - t*p) = c,
+    where t is an arbitrary integer.
 
+    n is the number of solution you want, n = 2 by default
 
-def diophantine_all_soln(a: int, b: int, c: int, n: int = 2) -> None:
-    """
     >>> diophantine_all_soln(10, 6, 14)
     -7.0 14.0
     -4.0 9.0
@@ -67,13 +69,12 @@ def diophantine_all_soln(a: int, b: int, c: int, n: int = 2) -> None:
         print(x, y)
 
 
-# Euclid's Lemma :  d divides a and b, if and only if d divides a-b and b
-
-# Euclid's Algorithm
-
-
 def greatest_common_divisor(a: int, b: int) -> int:
     """
+    Euclid's Lemma :  d divides a and b, if and only if d divides a-b and b
+
+    Euclid's Algorithm
+
     >>> greatest_common_divisor(7,5)
     1
 
@@ -94,12 +95,11 @@ def greatest_common_divisor(a: int, b: int) -> int:
     return b
 
 
-# Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers
-# x and y, then d = gcd(a,b)
-
-
-def extended_gcd(a: int, b: int) -> (int, int, int):
+def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
     """
+    Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers
+    x and y, then d = gcd(a,b)
+
     >>> extended_gcd(10, 6)
     (2, -1, 2)
 

diff --git a/blockchain/modular_division.py b/blockchain/modular_division.py
@@ -1,21 +1,23 @@
-# Modular Division :
-# An efficient algorithm for dividing b by a modulo n.
+from typing import Tuple
 
-# GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )
 
-# Given three integers a, b, and n, such that gcd(a,n)=1 and n>1, the algorithm should
-# return an integer x such that 0≤x≤n−1, and  b/a=x(modn) (that is, b=ax(modn)).
+def modular_division(a: int, b: int, n: int) -> int:
+    """
+    Modular Division :
+    An efficient algorithm for dividing b by a modulo n.
 
-# Theorem:
-# a has a multiplicative inverse modulo n iff gcd(a,n) = 1
+    GCD ( Greatest Common Divisor ) or HCF ( Highest Common Factor )
 
+    Given three integers a, b, and n, such that gcd(a,n)=1 and n>1, the algorithm should
+    return an integer x such that 0≤x≤n−1, and  b/a=x(modn) (that is, b=ax(modn)).
 
-# This find x = b*a^(-1) mod n
-# Uses ExtendedEuclid to find the inverse of a
+    Theorem:
+    a has a multiplicative inverse modulo n iff gcd(a,n) = 1
 
 
-def modular_division(a: int, b: int, n: int) -> int:
-    """
+    This find x = b*a^(-1) mod n
+    Uses ExtendedEuclid to find the inverse of a
+
     >>> modular_division(4,8,5)
     2
 
@@ -32,9 +34,10 @@ def modular_division(a: int, b: int, n: int) -> int:
     return x
 
 
-# This function find the inverses of a i.e., a^(-1)
 def invert_modulo(a: int, n: int) -> int:
     """
+    This function find the inverses of a i.e., a^(-1)
+
     >>> invert_modulo(2, 5)
     3
 
@@ -50,9 +53,11 @@ def invert_modulo(a: int, n: int) -> int:
 
 # ------------------ Finding Modular division using invert_modulo -------------------
 
-# This function used the above inversion of a to find x = (b*a^(-1))mod n
+
 def modular_division2(a: int, b: int, n: int) -> int:
     """
+    This function used the above inversion of a to find x = (b*a^(-1))mod n
+
     >>> modular_division2(4,8,5)
     2
 
@@ -68,17 +73,15 @@ def modular_division2(a: int, b: int, n: int) -> int:
     return x
 
 
-# Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers x
-# and y, then d = gcd(a,b)
-
-
-def extended_gcd(a: int, b: int) -> (int, int, int):
+def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
     """
-     >>> extended_gcd(10, 6)
-     (2, -1, 2)
+    Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers x
+    and y, then d = gcd(a,b)
+    >>> extended_gcd(10, 6)
+    (2, -1, 2)
 
-     >>> extended_gcd(7, 5)
-     (1, -2, 3)
+    >>> extended_gcd(7, 5)
+    (1, -2, 3)
 
     ** extended_gcd function is used when d = gcd(a,b) is required in output
 
@@ -98,9 +101,9 @@ def extended_gcd(a: int, b: int) -> (int, int, int):
     return (d, x, y)
 
 
-# Extended Euclid
-def extended_euclid(a: int, b: int) -> (int, int):
+def extended_euclid(a: int, b: int) -> Tuple[int, int]:
     """
+    Extended Euclid
     >>> extended_euclid(10, 6)
     (-1, 2)
 
@@ -115,12 +118,11 @@ def extended_euclid(a: int, b: int) -> (int, int):
     return (y, x - k * y)
 
 
-# Euclid's Lemma :  d divides a and b, if and only if d divides a-b and b
-# Euclid's Algorithm
-
-
 def greatest_common_divisor(a: int, b: int) -> int:
     """
+    Euclid's Lemma :  d divides a and b, if and only if d divides a-b and b
+    Euclid's Algorithm
+
     >>> greatest_common_divisor(7,5)
     1