Get significant speed up via memoization
authorGreg Hurrell <greg@hurrell.net>
Fri, 2 Jun 2017 14:08:29 +0000 (07:08 -0700)
committerGreg Hurrell <greg@hurrell.net>
Fri, 2 Jun 2017 14:08:29 +0000 (07:08 -0700)
src/convert.js

index 6b46caa1770c26ca83243a85f0826ebcbb158877..a3395f3c1fa861946971566952124860c7c48ea3 100644 (file)
@@ -10,6 +10,26 @@ import getDigits from './getDigits';
 import joinDigits from './joinDigits';
 import multiplyDigits from './multiplyDigits';
 
+/**
+ * Memoization for reusable part of computation. The `power` value in
+ * the core loop of `convert()` varies only by `inBase`/`outBase`,
+ * independently of the `number` to be converted, so we keep it around
+ * and re-use it to avoid repeated calls to `multiplyDigits()`.
+ */
+const memo = [];
+
+function getPowers(inBase: number, outBase: number): Array<Array<number>> {
+  let outer = memo[inBase];
+  if (!outer) {
+    outer = memo[inBase] = [];
+  }
+  let nested = outer[outBase];
+  if (!nested) {
+    nested = outer[outBase] = [[1]];
+  }
+  return nested;
+}
+
 /**
  * Convert `number` in base `inBase`, to base `outBase`. Both the input `number`
  * and return value are string representations.
@@ -23,9 +43,10 @@ export default function convert(
     return number;
   }
   const digits = getDigits(number, inBase);
+  const powers = getPowers(inBase, outBase);
   let result = [0];
-  let power = [1];
   for (let i = 0; i < digits.length; i++) {
+    const power = powers[i];
     if (digits[i]) {
       result = addDigits(
         result,
@@ -33,7 +54,10 @@ export default function convert(
         outBase
       );
     }
-    power = multiplyDigits(power, inBase, outBase);
+
+    if (powers.length < i + 2) {
+      powers[i + 1] = multiplyDigits(power, inBase, outBase);
+    }
   }
   return joinDigits(result, outBase);
 }