## Three Binary Algorithms

### January 15, 2010

We begin with the operations that are built-in to most hardware. R5RS Scheme does not provide bit operations, but most implementations provide an *arithmetic-shift* function, sometimes called *ash* as in Lisp. R6RS standardizes the *arithmetic-shift* function. Simple versions that will work anywhere are given below; for speed, they should be replaced by native operations, and in-lined.

`(define (lshift x) (* x 2))`

(define (rshift x) (quotient x 2))

(define (add1 x) (+ x 1))

For multiplication, we find it easier to accumulate the product as we go rather than to build the tableau of the ancient Egyptian algorithm:

`(define (multiply left right)`

(let loop ((left left) (right right) (prod 0))

(if (zero? left) prod

(loop (rshift left) (lshift right)

(if (odd? left) (+ prod right) prod)))))

For division, the outer loop accumulates *d* · 2^{k} in a temporary variable *t*, then the inner loop performs the division, stopping when *t* has been reduced beyond the original denominator, returning both quotient and remainder:

`(define (divide n d)`

(let loop ((t d))

(if (<= t n) (loop (lshift t))

(let loop ((t (rshift t)) (q 0) (r n))

(cond ((< t d) (values q r))

((<= t r) (loop (rshift t) (add1 (lshift q)) (- r t)))

(else (loop (rshift t) (lshift q) r)))))))

The greatest common divisor function is a literal translation of Stein’s algorithm:

`(define (stein-gcd n m)`

(let loop ((n n) (m m))

(if (zero? n) m (if (zero? m) n

(if (even? n)

(if (even? m)

(lshift (loop (rshift n) (rshift m)))

(loop (rshift n) m))

(if (even? m)

(loop n (rshift m))

(if (< n m)

(loop n (- m n))

(loop (- n m) m))))))))

Here are some samples:

`> (multiply 14 12)`

168

> (divide 837 43)

19

20

> (stein-gcd 2322 654)

6

You can run the code at http://programmingpraxis.codepad.org/P9bxsjXo.

[…] Praxis – Three Binary Algorithms By Remco Niemeijer In today’s Programming Praxis we have to implement binary algorithms for multiplying, dividing, and finding […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/01/15/programming-praxis-three-binary-algorithms/ for a version with comments):

I’ll break this down in three replies, C is just too verbose. I’m fascinated by how compact your Scheme and Haskell solutions always are… I really wanted to have a serious look at Python as a next step at learning to program, but this could make me change my mind.

Anyway, multiplication:

…sorry about the bit in french in the previous one. Division:

And the GCD:

I managed to get this one spectacularly wrong initially, by underestimating the difference between preprocessor macros and functions: I’d initially left out the brackets around the expression of the MAX and MIN macros, and obviously the operators precedence was playing a nasty trick on me in the gcd(MAX(m,n) – MIN(m,n), MIN(m,n)). I’d like to think it’s a lesson I won’t forget…

Python:

Working my way through old exercises; here’s my Python solution (note: the previously posted solution doesn’t look like it quite conquered division):

[…] rozruszania szarych komórek i nabrania praktyki w programowaniu. Na początek jedno z zadań z Programming Praxis, czyli prosta implementacja algorytmu mnożenia dwóch liczb całkowitych przy pomocy przesuwania o […]

My solution in Forth:

[…] suggested it would make a good exercise. Indeed it would; in fact, we have already done it twice ([1] […]