Prelude

Writing about mathematics and general programming has been on my mind for quite some time, and it makes me very excited to finally begin.

In this series, I want to highlight how the concept of algorithms, often considered central to computer science actually predates modern computing. From ancient times, humans have devised algorithmic ways to solve problems long before the advent of computers. Through these writings, I hope to uncover the elegance of expressing mathematical ideas through code.

Ahmes Multiplication Algorithm

At its core multiplication is adding something to itself, below is a simple recursive code which achieves this

// considering n and a are positive integers
function multiply(n: number, a: number) {
  if (n == 1) return a;

  return multiply(n-1, a) + a;
}

Ahmes algorithm makes use of the associativity in addition to compute the addition in an optimized way by halving n and doubing down on a. This decomposes n into a sum of powers of 2, i.e., its binary representation. to achieve the result faster. Consider the following example

51 × 20 = (48 × 20) + (2 × 20) + (1 × 20)

Now, let’s see this idea in code

function isOdd(num: number) {
 return num & 1;
}

function multiply(n: number, a: number) {
  if (n == 1) return a;
  let res = multiply(Math.floor(n/2), a+a);

  if (isOdd(n)) res = res + a;

  return res;
}

We have now essentially improved our earlier algorithm from a time complexity of O(n) to O(log n)

💡 I highly recommend using a recusion visualizer to the recursion stack
https://recursion.vercel.app/ credits to Bruno Papa for building this

Improving Further

While this version reduces the number of addition steps but there is still imporvements we can do, currently the function is recursive which is expensive our goal now is to eliminate recursion by converting it into a proper Tail Recursion call. To transform it into tail-call recursion, we use accumulator-passing to accumulate the result of the addition.

n × a = r + (nₒ × aₒ)
when we have n as odd we can write it as 2k + 1 giving us
n × a = (r + a) + (kₒ × aₒ)
to compute (nₒ × aₒ) or (kₒ × aₒ) we follow the accumulator algorithm

this is the relation we are going to follow to accumulate the result of our multiplication

function isOdd(num: number) {
 return num & 1;
}

function half(num: number) {
  return Math.floor(num/2)
}

function multiplyAccumulator(res: number, n: number, a: number) {
  if (n == 1) return res + a;

  if (isOdd(n)) {
    return multiplyAccumulator(res + a, half(n), a + a)
  } else {
    return multiplyAccumulator(res, half(n), a + a)
  }
}

We can simplify this further there since the two recursive calls only differ on the first argument.

function isOdd(num: number) {
 return num & 1;
}

function half(num: number) {
  return Math.floor(num/2)
}

function multiplyAccumulator(res: number, n: number, a: number) {
  if (n == 1) return res + a;

  if (isOdd(n)) {
    res = res + a
  } 

  return  multiplyAccumulator(res, half(n), a + a)
}

Notice that we still check for n == 1 outside the isOdd block. We can tighten that by moving the base case under the isOdd condition

function isOdd(num: number) {
 return num & 1;
}

function half(num: number) {
  return Math.floor(num/2)
}

function multiplyAccumulator(res: number, n: number, a: number) {
  if (isOdd(n)) {
    res = res + a
    if (n === 1) return res
  } 

  return  multiplyAccumulator(res, half(n), a + a)
}

Now we have a tail call recursive accumulator function which we can successfully convert into a interative approach.

function isOdd(num: number) {
 return num & 1;
}

function half(num: number) {
  return Math.floor(num/2)
}

function multiplyAccumulator(res: number, n: number, a: number) {
  while (true) {
   if (isOdd(n)) {
     res = res + a
     if (n === 1) return res
   } 
   n = half(n)
   a = a + a 
  }
}

Now we can use this multiplyAccumulator to compute the multiplication as below

function multiply(n: number, a: number) {
 if (n == 1) return a;
 return multiplyAccumulator(0, n, a);
}

💡 you might be thinking that tail call recursive optimisation will be done by the compiler by default
but as of now V8 does not have TCO implemented

🔑 Key Takeaways

• The Ahmes (Egyptian) multiplication algorithm optimizes multiplication by leveraging binary decomposition, reducing it to O(log n).

• It can be further improved by converting it into an Iterative approach by converting it into a proper tail call recursion

📚 Further Reading

• From Mathematics to Generic Programming by Alexander A. Stepanov and Daniel E. Rose

• The Art of Computer Programming, Vol. 1 by Donald E. Knuth

💬 Feedback + Language Choice

If you’ve made it this far — thank you! I’d love to hear your thoughts on the article. Was the pacing right? Were the explanations clear? Did anything feel missing or confusing?

Also, a quick note on language choice: I’ve used TypeScript because I believe it strikes the right balance between readability and accessibility for the widest possible audience.

If you have suggestions, corrections, or just want to chat — feel free to reach out or leave a comment.