From 328ec43686e312c81df4ffcbc9342d4e2c3402e2 Mon Sep 17 00:00:00 2001
From: Greg Hurrell <greg@hurrell.net>
Date: Wed, 31 May 2017 08:11:11 -0700
Subject: [PATCH] Avoid calling `pop()` on stack

We only ever push as many as 3 items on this stack, so we don't have to
worry about unbounded growth. Let's just maintain an index for the top
of the stack. In a sample run under the Chrome profiler, this shaves off
several hundred milliseconds (hand-waves).
---
 src/multiplyDigits.js | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/src/multiplyDigits.js b/src/multiplyDigits.js
index 7554e81..8925689 100644
--- a/src/multiplyDigits.js
+++ b/src/multiplyDigits.js
@@ -21,8 +21,10 @@ export default function multiplyDigits(
   // Running total of additions performed so far.
   let count = 0;
 
-  // We memoize partial subresults in a stack so they can be re-used.
+  // We memoize partial subresults in a faux-stack so they can be re-used.
+  // (Faux because we never actually pop, as an optimization.)
   const memo = [];
+  let memoIndex = -1;
 
   while (multiplier) {
     if (count && count * 2 < multiplier) {
@@ -31,19 +33,21 @@ export default function multiplyDigits(
       multiplier -= count;
       count *= 2;
       memo.push({count, result});
+      memoIndex++;
     } else {
-      const last = memo.pop();
+      const last = memoIndex >= 0 ? memo[memoIndex--] : null;
       if (last && last.count < multiplier) {
         // We can use a previous result on the stack to leap ahead.
         result = addDigits(result, last.result, base);
         multiplier -= last.count;
         count += last.count;
-      } else if (!memo.length) {
+      } else if (memoIndex < 0) {
         // Stack is empty, so fall back to base case (single addition).
         result = addDigits(result, multiplicand, base);
         multiplier--;
         count++;
         memo.push({count, result});
+        memoIndex++;
       }
     }
   }
-- 
2.37.1