Photo by Crissy Jarvis on Unsplash

Simplified Ancient Egyptian Multiplication with Elixir using Recursion — Part 1

Recursion is a very strong feature in Functional Languages.

In these 2 articles I am hoping to show you how you can write lots of recursions with mix of easy → hard using different strategies.

• Part 2

How recursion works?

When a function call itself, we call it recursion. There are different strategies in recursion. Ones that I use the most are Decrease and Conquer, Divide and Conquer.

I will try to use the mix of both in this example, and not confuse you with type.
Recursion must have an exit strategy. This is where you determine at what point script needs to finish and give you the state.

Scope of this project

Ancient Egyptian Multiplication, is a method of multiplying 2 numbers without using our modern multiplication method. (I assume you know how to multiply 2 large numbers together :)

The process is pretty straight forward,

1. Find the highest power of 2 less or equal than given number
2. each number multiple by the second number (My twist to keep things simple)
3. Sum up all the result

238 × 13= (128 + 64 + 32 + 8 + 4 + 2) × 13
= 128 × 13 + 64 × 13 + 32 × 13 + 8 × 13 + 4 × 13 + 2 × 13
= 1664 + 832 + 416 + 104 + 52 + 26
= 3094
(copied from https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication)

Now as you can see we have lots of recursions here. You can do this with Enum.reduce and maybe other Enum however what is the fun in that, aye!

One of the rules we use, No Enum

Expectation:

We want to have something like this at the very end:

iex(1)> AncientEgyptianMultiplication.multiply(238, 13)  
3094

Crude approach

The first step is decomposition of the first number.

Let’s do it a very basic decomposition of 238:

238 - :math.pow(2, 7) = 110
110 - :math.pow(2, 6) = 46
46 - :math.pow(2, 5)= 14  # Pay attention to the jump form 5
14 - :math.pow(2, 3)= 6   # to 3 in here. 2 POW 4 will be 16
6 - :math.pow(2, 2) = 2
2 - :math.pow(2, 1)= 0

Ok now you know how things work, so lets Elixirify it :)

Crude approach to decomposition

Now we can use it like:

iex(3)> AncientEgyptianMultiplication.of(238.0, [])
[128.0, 64.0, 32.0, 8.0, 4.0, 2.0]

Ok, let’s now break this recursion down a bit more, and refactor it so we can accept any number.

1. We want to get a number, state, and highest power of 2
2. Break it down from the highest power of 2 less or equal than the original number
3. put them all in a list and return it

Ok this one had a bit more to it, however still it is following the rule.

use IO.inspect to see each step.

All we are doing, we get a number, the greatest power of 2 to the supplied number and an empty state.

This script has a bug though :). See if you can pin point it!!

So now we can use it like this:

iex(6)> AncientEgyptianMultiplication.of(238, 7, [])
[128.0, 64.0, 32.0, 8.0, 4.0, 1.0]

Nice! now first question.

How do we get the highest pow of 2, where it is less / equal than our original number?

Here is a trick: — Divide the given number by 2, and ignore the reminders and decimals. Then count the number of times you have divide until you get to 1 or 0 . This would be your highest power of 2 for your original number.

Exception:
If the original number is an odd number first you need to -1 then do the divisions.

238 / 2 = 119
119 / 2 = 59
59 / 2 = 29
29 / 2 = 14
14 / 2 = 7
7 / 2 = 3
3 / 2 = 1
7 times dividing 238 by 2 will be the highest Power of 2 for 238

Now we know how the math bit works, let’s figure out the easy part!

iex(10)> AncientEgyptianMultiplication.of(238, []) |> Enum.count
7

I used Kernel.truncto get rid of the decimal points.

This is pretty good, however we are using Enum . We are not allowed to use Enum . We need a small recursion to count the number of items per list.

iex(13)> AncientEgyptianMultiplication.count_of([119, 59, 29, 14, 7, 3, 1])
7

Ok we have lots of pieces now. Hopefully you found that little bug by now. Anyway by finding the highest power of 2 programatically, that small bug will disappear.

Now lets put all together and finish the Part 1:

And this is how we use and test the decomposition

iex(23)> AncientEgyptianMultiplication.decompose(238)            
[128, 64, 32, 8, 4, 2]
iex(24)> AncientEgyptianMultiplication.decompose(238) |> Enum.sum
238

In Part to we try to create the Sum and Multiplication (simple version)

Hopefully, I see you in part 2.

Houman.