_Posted on June 04, 2025_
##### Introduction
In a field $K$ (such as the real numbers $\mathbb{R}$), every non-zero element has a unique multiplicative inverse. Therefore, for non-zero elements $a,b \in K$, $a \div b = a \cdot b^{-1}$, which is itself an element of $K$. This property makes division itself a binary operation on $K$.
Over a ring $R$, however, not every non-zero element has a multiplicative inverse, so that division is not a binary operation on $R$. There is, however, a subclass of rings called **Euclidean domains** where there is a **division algorithm**. A division algorithm exists when there is a function $f$ satisfying the division with remainder property:
> [!theorem] If $a,b \in R$ such that $b \neq 0$, then there exists $q,r \in R$ such that $a = b\cdot q + r$ and either $r = 0$ or $f(r) < f(b)$
By [[Euclid's Division Lemma]], the set of integers is a Euclidean domain (where $f(n) = \left|n\right|$).
A division algorithm is supposed to compute the **quotient** $q$ and **remainder** $r$. The following are two such algorithms on the integers.
##### Algorithm 1
The first algorithm is a naive solution based on repeated subtraction. Let $a,b \in \mathbb{Z}$ where $b \neq 0$. Simply observe that $a = b \cdot q + r = \underbrace{b + b + \cdots + b}_{q \text{ times}} + r,$and hence$a - \underbrace{b + b + \cdots + b}_{q \text{ times}} = r$with $0 \leq r < \left| b \right|$. To find $q$, we can therefore subtract $b$ from $a$ until the result is less than $\left| b \right|$, counting the number of iterations. This algorithm is implemented below.
```scheme
(define (division-by-repeated-subtraction a b)
(define (division-by-repeated-subtraction-iter a b q)
(if (>= (- a b) 0)
(division-by-repeated-subtraction-iter
(- a b)
d
(+ q 1))
(list q a)))
(division-by-repeated-subtraction-iter a b 0))
```
##### Algorithm 2
The second algorithm is akin to the long division algorithm typically learned in elementary school, but implemented in binary.
```scheme
(define (set-bit n bit-position value)
(logior n (ash value bit-position)))
(define (get-bit n bit-position)
(logand 1 (ash n (- bit-position))))
(define (long-division a b)
(define (long-division-iter a b q r i)
(cond
((< i 0) (list q (ash r -1)))
((>= r b) (long-division-iter a b
(set-bit q i 1)
(set-bit (ash (- r b) 1)
0
(get-bit a (- i 1)))
(- i 1)))
(else (long-division-iter a b q
(set-bit (ash r 1)
0
(get-bit a (- i 1)))
(- i 1)))))
(long-division-iter a b 0
(set-bit 0 0 (get-bit a (- (integer-length a) 1)))
(- (integer-length a) 1)))
```