

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

Euclidean Division

The function $\texttt{div_mod}(a, n)$ takes two natural numbers $a, n \in \mathbb{N}$ such that $n > 0$ and returns a pair $(q, r)$ where $q$ is the quotient of dividing $a$ by $n$, while $r$ is the remainder. Mathematically, $q$ and $r$ are defined as those number that satisfy the following:

$a = q \cdot n + r$
$0 \leq r < n$



In [ ]:

    
def div_mod(a, n):
    q = 0
    while a >= n:
        a -= n
        q += 1
    return q, a



In [ ]:

    
div_mod(12, 3)



In [ ]:

    
div_mod(14, 5)



In [ ]:

    
def test_div_mod(m, n):
    q, r = div_mod(m, n)
    assert m == q * n + r, f'm = {m}, n = {n}, q = {q}, r = {r}'
    assert 0 <= r < n,     f'm = {m}, n = {n}, q = {q}, r = {r}'



In [ ]:

    
import random



In [ ]:

    
for n in range(100):
    print(random.randrange(7), end='')



In [ ]:

    
%%time
for k in range(10000):
    m = random.randrange(1000000)
    n = random.randrange(1000) + 1
    test_div_mod(m, n)



In [ ]: