Speed up multiplyDigits

If we can double the length of the result in a single operation, we do.
This makes us faster for larger multipliers.

Note that I could make this even faster for really big multipliers by
employing some kind of memoization:

eg. multiply X by 1000:

  - iteration 0: X + X (2X)
  - iteration 1: 2X + 2X (4X)
  - iteration 2: 4x + 4X (8X)
  - iteration 3: 8X + 8X (16X)
  - iteration 4: 16x + 16X (32X)
  - iteration 5: 32X + 32X (64X)
  - iteration 6: 64X + 64X (128X)
  - iteration 7: 128X + 128X (256X)
  - iteration 8: 256X + 256X (512X)
  - iteration 9: 512X + 256X (768X) [use largest possible prev value)
  - iteration 10: 768X + 128X (896X) [largest possible is smaller now)
  - iteration 11: 896X + 64X (960X) [and smaller]
  - iteration 12: 960X + 32X (992X) [smaller]
  - iteration 13: 992X + 8X (1000X) [smaller still; note skip as well]

This might be hard to implement though. I was thinking it might call for
a heap but I don't think so; it just needs a stack, and we pop off until
we get a usable value from it.

diff --git a/src/multiplyDigits.js b/src/multiplyDigits.js
index afd2146ffd75bb41bc114eee77d668f153c07857..5819bbf9cb66c6e5c37f76941c06bf80df981c6a 100644 (file)
--- a/src/multiplyDigits.js
+++ b/src/multiplyDigits.js
@@ -18,8 +18,19 @@ export default function multiplyDigits(
   base: number
 ): Array<number> {
   let result = [0];
-  for (let i = 0; i < multiplier; i++) {
-    result = addDigits(result, multiplicand, base);
+  let count = 0;
+
+  while (multiplier) {
+    if (count && count * 2 < multiplier) {
+      multiplier -= count;
+      count *= 2;
+      result = addDigits(result, result, base);
+    } else {
+      result = addDigits(result, multiplicand, base);
+      count++;
+      multiplier--;
+    }
   }
+
   return result;
 }