Egyptian division

Table of Contents

1  Egyptian division

1.1  Algorithm:

1.2  Example: 580 / 34

1.2.1  Table creation:

1.2.2  Initialization of sums:

1.2.3  Considering table rows, bottom-up:

1.2.4  Finally

2  Rosetta Code

3  Task

4  Python Solution

5  Extra

Egyptian division

Egyptian division is a method of dividing integers using addition and doubling that is similar to the algorithm of Ethiopian multiplicaion

Algorithm:

Given two numbers where the dividend is to be divided by the divisor:

1. Start the construction of a table of two columns: powers_of_2, and doublings; by a first row of a 1 (i.e. 2^0) in the first column and 1 times the divisor in the first row second column.
2. Create the second row with columns of 2 (i.e 2^1), and 2 * divisor in order.
3. Continue with successive i'th rows of 2^i and 2^i * divisor.
4. Stop adding rows, and keep only those rows, where 2^i * divisor is less than or equal to the dividend.
5. We now assemble two separate sums that both start as zero, called here answer and accumulator
6. Consider each row of the table, in the reverse order of its construction.
7. If the current value of the accumulator added to the doublings cell would be less than or equal to the dividend then add it to the accumulator, as well as adding the powers_of_2 cell value to the answer.
8. When the first row has been considered as above, then the integer division of dividend by divisor is given by answer.
   (And the remainder is given by the absolute value of accumulator - dividend).

Example: 580 / 34

Table creation:

powers_of_2	doublings
1	34
2	68
4	136
8	272
16	544

Initialization of sums:

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136
8	272
16	544
		0	0

Considering table rows, bottom-up:

When a row is considered it is shown crossed out if it is not accumulated, or bold if the row causes summations.

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136
8	272
16	544	16	544

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136
8	272	16	544
16	544

powers_of_2	doublings	answer	accumulator
1	34
2	68
4	136	16	544
8	272
16	544

powers_of_2	doublings	answer	accumulator
1	34
2	68	16	544
4	136
8	272
16	544

powers_of_2	doublings	answer	accumulator
1	34	17	578
2	68
4	136
8	272
16	544

Finally

So 580 divided by 34 using the Egyptian method is 17 remainder (578 - 580) or 2.

Rosetta Code

This blog post should be a Rosetta Code task, but at the time of writing the site has been down for maintenance for a week. I will still writethe task description and its first Python solution though.

Task

The task is to create a function that does Egyptian division. The function should closely follow the description above in using a list/array of powers of two, and another of doublings.

• Functions should be clear interpretations of the algorithm.
• Use the function to divide 580 by 34 and show the answer here, on this page.

Python Solution

In [2]:

def egyptian_divmod(dividend, divisor):
    assert divisor != 0
    pwrs, dbls = [1], [divisor]
    while dbls[-1] <= dividend:
        pwrs.append(pwrs[-1] * 2)
        dbls.append(pwrs[-1] * divisor)
    ans, accum = 0, 0
    for pwr, dbl in zip(pwrs[-2::-1], dbls[-2::-1]):
        if accum + dbl <= dividend:
            accum += dbl
            ans += pwr
    return ans, abs(accum - dividend)

# Test it gives the same results as the divmod built-in
from itertools import product
for i, j in product(range(13), range(1, 13)):
        assert egyptian_divmod(i, j) == divmod(i, j)

# Mandated result
i, j = 580, 34
print(f'{i} divided by {j} using the Egyption method is %i remainder %i'
      % egyptian_divmod(i, j))

580 divided by 34 using the Egyption method is 17 remainder 2

Extra

A quick note on hardware applications.

The astute may note that the doublings column entries are easily computed as successive shifts of the binary representation of the divisor; and that the result in binary can be read off by marking 1 if a table row is summed or 0 if it is not.

Python investigation of the Shoelace Formula for polygonal area

Table of Contents

1  Shoelace formula for polygonal area

1.1  Sawtooth generator

1.2  Calculate area by shoelace formula

2  Why Shoelace?

2.1  Get the coordinates, in order.

2.2  First "lacing":

2.3  Second "lacing"

2.4  Complete formula

Shoelace formula for polygonal area

Sawtooth generator

In [33]:

def sawtooth_wave(teeth, base=2, height=3):
    xy = [(0, 0)] # start
    for n in range(teeth):
        xy += [(base * (n + 1), height), (base * (n + 1), 0)]
    xy.append((0, 0))  # return to start
    return zip(*xy)   # x then y

In [34]:

from pprint import pprint as pp
from bokeh.plotting import figure, output_notebook, show
from bokeh.models import ColumnDataSource
from bokeh.charts import Scatter
output_notebook()

 BokehJS 0.12.5 successfully loaded.

In [35]:

teeth = 3
sawx, sawy = sawtooth_wave(teeth)
sawx, sawy = zip(*saw)
pl = figure(plot_width=400, plot_height=400, title=f'Sawtooth polygon with {teeth} right-angled triangle teeth')
#help(pl.line)
pl.line(sawx, sawy, line_width = 1, line_color="navy")
show(pl)

Calculate area by shoelace formula

In [36]:

def area_by_shoelace(x, y):
    "Assumes x,y points go around the polygon in one direction"
    return abs( sum(i * j for i, j in zip(x, y[1:])) + x[-1] * y[0]
               -sum(i * j for i, j in zip(x[1:], y)) - x[0] * y[-1]) / 2 

In [37]:

print(" Area is:", area_by_shoelace(sawx, sawy))

 Area is: 9.0

We know that the area of a right angled tringle is half base times height.

So each tooth of the saw has area 1/2 * 2 * 3 = 3 units and we have three teeth for a total area of 9.

Why Shoelace?

It's called the shoelace formula because of a visualization of the calculation.

Get the coordinates, in order.

list the x,y coordinates of each point of the polygon, going around the polygon in one direction, and going back to the starting point. (For more complex polygons, no line segments should cross).

Split the ordered points into two identically ordered lists of the x coordinates and the y coordinates.

Visualize the x coords as numbers beside one side of a row of eyelets of a shoe, and the y coords adjacent to the eyelets on the other side.

First "lacing":

lacing1 = sum(x[0]*y[1] + ... x[n]*y[n+1]) + x[N]*y[0]

Second "lacing"

lacing2 = sum(x[1]*y[0] + ... x[n+1]*y[n) + x[0]*y[N]

Complete formula

area = abs(lacing1 - lacing2) / 2

All tied up!