Ancient Egyptian Multiplication in C#

Clocks have gone back in the UK and I can’t sleep so decided to do a little light programming to try and send me off. I’ve basically coded up an ancient Egyptian multiplication algorithm in C# using a .net Dictionary object. If you want to read up on the algorithm itself, here’s the wikipedia article.

This algorithm is also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or Peasant Multiplication. I did also find an implementation of this over on Rosetta Code – the one they have there is much more streamlined than what I ended up doing (they even did a linq version that I’m very jelous of!) but this one’s more readable than the recursive version they give over there so thought it was at least worth posting.

Okay then here we go: Ancient Egyptian Multiplication in C#!

using System.Collections.Generic;
using System.Linq;

        public static int AncientEgyptianMultiplication(int multiplicand1, int multiplicand2)
        {
            Dictionary<int, int> pairs = new Dictionary<int, int>();            
            pairs.Add(multiplicand1, multiplicand2);
            return performMultiplicaiton(pairs);
        }

        private static int performMultiplicaiton(Dictionary<int, int> pairs)
        {
            if ((int)pairs.Last().Key == 1)
                return pairs.Last().Value;
            else
            {
                var latestPair = pairs.Last();
                pairs.Add(latestPair.Key / 2, latestPair.Value * 2);

                if (latestPair.Key % 2 != 0)
                    return (int)latestPair.Value + performMultiplicaiton(pairs);
                else
                    return performMultiplicaiton(pairs);
            }
        }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s