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 · 2k 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] […]