]> git.wincent.com - hextrapolate.git/commitdiff
Reuse stack more aggressively
authorGreg Hurrell <greg@hurrell.net>
Fri, 2 Jun 2017 15:32:00 +0000 (08:32 -0700)
committerGreg Hurrell <greg@hurrell.net>
Fri, 2 Jun 2017 15:32:00 +0000 (08:32 -0700)
We see that we can always find a re-usable item somewhere in the stack;
we don't have to give up after looking at the last item alone.

src/multiplyDigits.js

index 4350b36b181c51df80c8bab1d24e8fb5f237b06a..fd662028df1b6040a14b3dd0be8925555ae700a7 100644 (file)
@@ -37,21 +37,24 @@ export default function multiplyDigits(
       count *= 2;
       memo.push({count, result});
       memoIndex++;
       count *= 2;
       memo.push({count, result});
       memoIndex++;
-    } else {
-      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;
-      } 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});
-        memoIndex++;
+    } else if (memoIndex >= 0) {
+      // We can use a previous result from the stack to leap ahead.
+      while (memoIndex >= 0) {
+        const previous = memo[memoIndex--];
+        if (previous.count <= multiplier) {
+          result = addDigits(result, previous.result, base);
+          multiplier -= previous.count;
+          count += previous.count;
+          break;
+        }
       }
       }
+    } else {
+      // Stack is empty, so fall back to base case (single addition).
+      result = addDigits(result, multiplicand, base);
+      multiplier--;
+      count++;
+      memo.push({count, result});
+      memoIndex++;
     }
   }
 
     }
   }