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).

diff --git a/src/multiplyDigits.js b/src/multiplyDigits.js
index 7554e8127d388827301567aae16adca7988aa979..8925689ad796650a5aac37c86e648a70adc91cb3 100644 (file)
--- 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;
 
   // 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 = [];
   const memo = [];

+  let memoIndex = -1;

 
   while (multiplier) {
     if (count && count * 2 < multiplier) {
 
   while (multiplier) {
     if (count && count * 2 < multiplier) {


@@ -31,19 +33,21 @@ export default function multiplyDigits(
       multiplier -= count;
       count *= 2;
       memo.push({count, result});
       multiplier -= count;
       count *= 2;
       memo.push({count, result});

+      memoIndex++;

     } else {
     } 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;
       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});
         // Stack is empty, so fall back to base case (single addition).
         result = addDigits(result, multiplicand, base);
         multiplier--;
         count++;
         memo.push({count, result});

+        memoIndex++;

       }
     }
   }
       }
     }
   }