### Egyptian Multiplication Algorithm

*02 January 2020*

I have started reading the book From Mathematics to Generic Programming. In the second chapter the authors discuss an Egyptian method of multiplication that involves the use of a table. First you make the table and then you use it to perform multiplication. Below is a table for multiplying 21 by 23. Start with 1 x 23 and then double them for every following row. 1 + 1 is 2 and 23 + 23 is 46.

Multiple | Result |
---|---|

1 |
23 |

2 |
46 |

4 |
92 |

8 |
184 |

16 |
368 |

This leverages the ease of adding something to itself to create the table. The algorithm uses addition to get the final result. We add 16 + 4 + 1 in the first column to get 21. Then we add the corresponding values in the second column to get the correct answer. 23 + 92 + 368 = 483.

Having read through the chapter I will now code my own implementation. Followed by an implementation of the authors version.