## Three Binary Algorithms

### January 15, 2010

Today’s exercise examines three binary algorithms, for basic arithmetic: multiplication, division, and greatest common divisor.

Four millenia ago, when the ancient Egyptians were building the pyramids, they invented a method for multiplying positive integers that works like this: They start by writing the two numbers to be multiplied at the head of two columns. Then they repeatedly divide the number in the left column by two (right-shift), dropping any remainder, and double the number in the right column (left-shift), writing the two new numbers immediately below their predecessors, until the number in the left column is one. Then they cross out all rows where the number in the left column is even, and add the remaining numbers in the right column, which is the desired product. For instance, the product fourteen times twelve is found like this:

`14 `

~~12~~

7 24

3 48

1 96

168

It is easy to see why this method works if you use the grade-school method of multiplication, but with binary numbers instead of decimal numbers:

` 1 1 0 0 1 2`

1 1 1 0 1 4

- - - - - -

0 0 0 0 0 x 1 2 0

1 1 0 0 2 x 1 2 2 4

1 1 0 0 4 x 1 2 4 8

1 1 0 0 8 x 1 2 9 6

- - - - - - - - - - - - - -

1 0 1 0 1 0 0 0 1 4 x 1 2 1 6 8

In binary, 14 is 1 · 2^{3} + 1 · 2^{2} + 1 · 2^{1} + 0 · 2^{0}. The odd numbers in the left column correspond to the 1 bits in the binary representation of the multiplicand.

Binary division is the inverse operation to binary multiplication, and is also done by a series of doubling and halving operations. We’ll begin with the grade-school algorithm, in binary:

` 1 0 0 1 1`

- - - - - - - - - - -

1 0 1 0 1 1 ) 1 1 0 1 0 0 0 1 0 1 8 3 7

1 0 1 0 1 1 6 8 8 / 4 3 = 1 6

- - - - - - - - -

1 0 0 1 0 1 0 1 4 9

1 0 1 0 1 1 8 6 / 4 3 = 2

- - - - - - - - - -

1 1 1 1 1 1 6 3

1 0 1 0 1 1 4 3 / 4 3 = 1

- - - - - - - -

1 0 1 0 0 2 0

The quotient has a 1 wherever the divisor is less than the current portion of the dividend, and a 0 where the next digit is “brought down” from the dividend. The algorithmic version of *n* ÷ *d* is based on a quantity *d* · 2^{k}, which we call *t*, which is initialized with the largest *k* that leaves *t* less than *n*; this can be done by repeated left shifts. Then the quotient *q* is initialized to zero, the remainder *r* is initialized to *n*, and an iteration continues halving *t* until *t* is less than the original *d*; at each stage of the iteration, the quotient is doubled (left-shift) if the current remainder is less than *t*, otherwise the quotient is doubled (left-shift), then one is added, and the current remainder is reduced by the current value of *t*. An example is shown below:

`t q r`

43

86

172

344

688

1376

688 0 837

344 1 149

172 2 149

86 4 149

43 9 63

43/2 19 20

Josef Stein described a binary algorithm for greatest common divisor in 1967 that was devised by Chinese mathematicians in the first century. The greatest common divisor of two numbers is calculated by a recursive algorithm with four rules:

- If either number is zero, their greatest common divisor is the other number.
- If both numbers are even, the two numbers share a factor of two, so their greatest common divisor is double (left-shift) the greatest common divisor of the halves (right-shift) of the two numbers.
- If one number is even and the other is odd, they have no factor of two in common, so their greatest common divisor is the greatest common divisor of the odd number and half (right-shift) the even number.
- Otherwise, both numbers are odd, and a normal Euclidean step is performed, replacing the larger of the two numbers with their difference.

Binary algorithms such as these are quite common; see for instance the `ipow`

and `expm`

functions in the Standard Prelude. They are especially useful for hardware implementations in the microcode of the processor, since bit-shifting operations are extremely fast.

Your task is to write functions that perform the three operations given above, simulating how they are performed in hardware. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

[…] 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] […]

[…] X. I describe (with code) the original Euclidean algorithm, the modern Euclidean algorithm, the binary algorithm, and the extended Euclidean algorithm at my […]