Egyptian multiplication with Haskell
Very recently a saw a Youtube video from a friend, MathGurl , in which she explained the ancient Egyptian multiplication method. At the same time, and for no particular reason, I remembered Haskell, so I decided to implement the method. It was not a big feat of programming, but I did enjoy relearning the basics of Haskell I once knew. You can find the file with the implementation here. (The implementation only works for non-negative integers) The method is quite simple and works because of the binary expansion of a number. Basically, if you want to calculate a * b , either b is even or odd. If b is even, just cut b in half and duplicate a to compute (2a)(b/2) . If b is odd, then ab = a + (2a)*((b-1)/2) . Another way of thinking about this is by writing b in the form b = 2^(k_1) + 2^(k_2) + ... + 2^(k_n) and then having ab = a( 2^(k_1) + 2^(k_2) + ... + 2^(k_n)) = a2^(k_1) + a2^(k_2) + ... + a2^(k_n) . My formulation is just the recursive way of writing it. If I get the courage t...