Ancient Egyptian Multiplication

egyptianMultiply(12, 99);

// trace(12 * 99) // test to make sure it works

/* outputs:
/64 768
/32 384
 16 192
 8 96
 4 48
/2 24
/1 12
---
1188
*/
 

function egyptianMultiply(valueA:Number, valueB:Number):void {
	
	var left:Array = [];
	var right:Array = []
	
	// swap if valueB is smaller than value A
	if (valueB < valueA){
		var swap:int = valueB;
		valueB = valueA;
		valueA = swap; 
	}
	
	// create left and right columns
	var currentLeft:int = 1;
	var currentRight:int = valueA;
	
	while (currentLeft < valueB){
		left.push(currentLeft);
		right.push(currentRight);
		currentRight += currentRight;
		currentLeft += currentLeft; 
	}
	
	
	// add up the right column based on the left
	currentLeft = 0;
	var rightSum:int;
	var leftSum:int;
	var i:int = left.length - 1;
	
	while (currentLeft != valueB){
	 
	  leftSum = currentLeft + left[i];
	  // if the next number causes the sum
	  // to go above valueB, skip it
	  if (leftSum <= valueB){
		currentLeft = leftSum;
		rightSum += right[i];
		trace("/" + left[i]  + " " + right[i]);
	  } else {
		trace(" " + left[i]  + " " + right[i]);
	  }
	  i--;
	}
	trace("---");
	trace(rightSum);
}

Someone mentioned egyptian multiplication to me yesterday… So read a little about it here and whipped up this example. For some reason I decided to do it in processing … once it worked I ported it to ActionScript.

The above link describing the technique I used is from http://www.jimloy.com/… I haven’t spent much time digging around the site, but it appears to have some pretty nice stuff on it…

If you’re curious, here is the original processing version:

Vector left = new Vector();
Vector right = new Vector();

int valueA = 10;
int valueB = 8;

if (valueB < valueA){
    int swap = valueB;
    valueB = valueA;
    valueA = swap; 
}

int currentLeft = 1;
int currentRight = valueA;
while (currentLeft < valueB){
    left.add(currentLeft);
    right.add(currentRight);
    currentRight += currentRight;
    currentLeft += currentLeft; 
}
 
currentLeft = 0;
 
int result = 0;
int i = left.size() - 1;
while (currentLeft != valueB){
 
  int temp = currentLeft + (Integer) left.get(i);
  if (temp <= valueB){
    
    currentLeft = temp;
    result += (Integer) right.get(i);
    println("/" + left.get(i) + " " + right.get(i));
  } else {
    println(" " + left.get(i)  + " " + right.get(i));
  }
    
  i--;
}
println("---");
println(result);

After writing, this I took a look at the wikipedia entry… I also found myself on this short page about a scribe called Ahmes. (I recommend reading this if you are interested in PI)