From 235c0a3df9cb9a483609b741d8c23bbcfd8bd698 Mon Sep 17 00:00:00 2001
From: Greg Hurrell <greg@hurrell.net>
Date: Fri, 31 Jul 2015 18:20:25 -0700
Subject: [PATCH] Speed up multiplyDigits even more

Implement the algorithm described in the last commit message.
---
 src/__tests__/multiplyDigits-test.js |  7 +++++++
 src/multiplyDigits.js                | 26 ++++++++++++++++++++++----
 2 files changed, 29 insertions(+), 4 deletions(-)

diff --git a/src/__tests__/multiplyDigits-test.js b/src/__tests__/multiplyDigits-test.js
index b2de7e1..2bb733b 100644
--- a/src/__tests__/multiplyDigits-test.js
+++ b/src/__tests__/multiplyDigits-test.js
@@ -35,4 +35,11 @@ describe('multiplyDigits()', () => {
     expect(multiplyDigits([4], 100, 10)).toEqual([0, 0, 4]);
     expect(multiplyDigits([12], 100, 16)).toEqual([0, 11, 4]);
   });
+
+  it('multiplies by 1000', () => {
+    expect(multiplyDigits([1], 1000, 2)).toEqual([0, 0, 0, 1, 0, 1, 1, 1, 1, 1]);
+    expect(multiplyDigits([5], 1000, 8)).toEqual([0, 1, 6, 1, 1]);
+    expect(multiplyDigits([4], 1000, 10)).toEqual([0, 0, 0, 4]);
+    expect(multiplyDigits([12], 1000, 16)).toEqual([0, 14, 14, 2]);
+  });
 });
diff --git a/src/multiplyDigits.js b/src/multiplyDigits.js
index 5819bbf..842a415 100644
--- a/src/multiplyDigits.js
+++ b/src/multiplyDigits.js
@@ -17,18 +17,36 @@ export default function multiplyDigits(
   multiplier: number,
   base: number
 ): Array<number> {
+  // Partial result being built up.
   let result = [0];
+
+  // Running total of additions performed so far.
   let count = 0;
 
+  // We memoize partial subresults in a stack so they can be re-used.
+  const memo = [];
+
   while (multiplier) {
     if (count && count * 2 < multiplier) {
+      // We can double the current result without exceeding the target.
+      result = addDigits(result, result, base);
       multiplier -= count;
       count *= 2;
-      result = addDigits(result, result, base);
+      memo.push({count, result});
     } else {
-      result = addDigits(result, multiplicand, base);
-      count++;
-      multiplier--;
+      const last = memo.pop();
+      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) {
+        // Stack is empty, so fall back to base case (single addition).
+        result = addDigits(result, multiplicand, base);
+        multiplier--;
+        count++;
+        memo.push({count, result});
+      }
     }
   }
 
-- 
2.37.1