Speed up multiplyDigits even more

Implement the algorithm described in the last commit message.

diff --git a/src/__tests__/multiplyDigits-test.js b/src/__tests__/multiplyDigits-test.js
index b2de7e1a4654e06f024d9fc054d122d597457741..2bb733bfc7856002cde0408fe58c538fdfecbf91 100644 (file)
--- 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 5819bbf9cb66c6e5c37f76941c06bf80df981c6a..842a4150a03c1ad60259134d61082823e623ea2b 100644 (file)
--- 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});
+      }
     }
   }