From: Greg Hurrell <greg@hurrell.net>
Date: Thu, 1 Jun 2017 15:14:08 +0000 (-0700)
Subject: Avoid repeated `reverse()` calls in `getDigits` + `joinDigits`
X-Git-Url: https://git.wincent.com/hextrapolate.git/commitdiff_plain/54b28015d427b17e78bd7e30a7efbbe3454891c6

Avoid repeated `reverse()` calls in `getDigits` + `joinDigits`

Put most significant digits first, which means we avoid the `reverse()`
calls at the cost of having to use `unshift()`. It is indeed slower, but
I wanted to show my work. Next step will be replacing the `unshift()`
with `push()` + `reverse()`, but that probably still won't be enough to
get us back to perf parity.
---

diff --git a/src/addDigits.js b/src/addDigits.js
index 1d3b1a8..566b463 100644
--- a/src/addDigits.js
+++ b/src/addDigits.js
@@ -12,11 +12,13 @@ export default function addDigits(
 ): Array<number> {
   let result = [];
   let carry = 0;
-  for (let i = 0; i < aDigits.length || i < bDigits.length || carry; i++) {
-    const aDigit = i < aDigits.length ? aDigits[i] : 0;
-    const bDigit = i < bDigits.length ? bDigits[i] : 0;
+  const aLength = aDigits.length;
+  const bLength = bDigits.length;
+  for (let i = 0; i < aLength || i < bLength || carry; i++) {
+    const aDigit = i < aLength ? aDigits[aLength - i - 1] : 0;
+    const bDigit = i < bLength ? bDigits[bLength - i - 1] : 0;
     const sum = aDigit + bDigit + carry;
-    result.push(sum % base);
+    result.unshift(sum % base);
 
     // ~~ here is the equivalent of Math.floor; used to avoid V8 de-opt,
     // "Reference to a variable which requires dynamic lookup".
diff --git a/src/convert.js b/src/convert.js
index a7f80ae..05773f3 100644
--- a/src/convert.js
+++ b/src/convert.js
@@ -24,7 +24,7 @@ export default function convert(
   const digits = getDigits(number, inBase);
   let result = [0];
   let power = [1];
-  for (let i = 0; i < digits.length; i++) {
+  for (let i = digits.length - 1; i >= 0; i--) {
     if (digits[i]) {
       result = addDigits(
         result,
diff --git a/src/getDigits.js b/src/getDigits.js
index 0bdc7d1..ea82870 100644
--- a/src/getDigits.js
+++ b/src/getDigits.js
@@ -43,13 +43,13 @@ function parse(digit: string, base: number) {
 
 /**
  * Breaks the string repsentation of `number` in `base` into an array of decimal
- * digits (from least significant to most significant) for easier manipulation.
+ * digits (from most significant to least significant) for easier manipulation.
  *
- * For example, the hexadecimal representation `"40fa"` becomes `[10, 15, 0,
- * 4]`.
+ * For example, the hexadecimal representation `"40fa"` becomes
+ * `[4, 0, 15, 10]`.
  */
 export default function getDigits(number: string, base: number): Array<number> {
-  return stripPrefix(number, base).trim().split('').reverse().map(digit => {
+  return stripPrefix(number, base).trim().split('').map(digit => {
     const result = parse(digit, base);
     if (isNaN(result)) {
       throw new Error('Invalid digit `' + digit + '` for base `' + base + '`');
diff --git a/src/joinDigits.js b/src/joinDigits.js
index f31460e..bb0620b 100644
--- a/src/joinDigits.js
+++ b/src/joinDigits.js
@@ -26,6 +26,5 @@ export default function joinDigits(
 ): string {
   return digits
     .map(number => encode(number, base))
-    .reverse()
     .join('');
 }
diff --git a/src/multiplyDigits.test.js b/src/multiplyDigits.test.js
index 1e43f14..b369063 100644
--- a/src/multiplyDigits.test.js
+++ b/src/multiplyDigits.test.js
@@ -23,23 +23,23 @@ describe('multiplyDigits()', () => {
   });
 
   it('multiplies by 2', () => {
-    expect(multiplyDigits([1], 2, 2)).toEqual([0, 1]);
-    expect(multiplyDigits([5], 2, 8)).toEqual([2, 1]);
+    expect(multiplyDigits([1], 2, 2)).toEqual([1, 0]);
+    expect(multiplyDigits([5], 2, 8)).toEqual([1, 2]);
     expect(multiplyDigits([4], 2, 10)).toEqual([8]);
-    expect(multiplyDigits([12], 2, 16)).toEqual([8, 1]);
+    expect(multiplyDigits([12], 2, 16)).toEqual([1, 8]);
   });
 
   it('multiplies by 100', () => {
-    expect(multiplyDigits([1], 100, 2)).toEqual([0, 0, 1, 0, 0, 1, 1]);
-    expect(multiplyDigits([5], 100, 8)).toEqual([4, 6, 7]);
-    expect(multiplyDigits([4], 100, 10)).toEqual([0, 0, 4]);
-    expect(multiplyDigits([12], 100, 16)).toEqual([0, 11, 4]);
+    expect(multiplyDigits([1], 100, 2)).toEqual([1, 1, 0, 0, 1, 0, 0]);
+    expect(multiplyDigits([5], 100, 8)).toEqual([7, 6, 4]);
+    expect(multiplyDigits([4], 100, 10)).toEqual([4, 0, 0]);
+    expect(multiplyDigits([12], 100, 16)).toEqual([4, 11, 0]);
   });
 
   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]);
+    expect(multiplyDigits([1], 1000, 2)).toEqual([1, 1, 1, 1, 1, 0, 1, 0, 0, 0]);
+    expect(multiplyDigits([5], 1000, 8)).toEqual([1, 1, 6, 1, 0]);
+    expect(multiplyDigits([4], 1000, 10)).toEqual([4, 0, 0, 0]);
+    expect(multiplyDigits([12], 1000, 16)).toEqual([2, 14, 14, 0]);
   });
 });