Avoid repeated `reverse()` calls in `getDigits` + `joinDigits`
authorGreg Hurrell <greg@hurrell.net>
Thu, 1 Jun 2017 15:14:08 +0000 (08:14 -0700)
committerGreg Hurrell <greg@hurrell.net>
Thu, 1 Jun 2017 15:14:08 +0000 (08:14 -0700)
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.

src/addDigits.js
src/convert.js
src/getDigits.js
src/joinDigits.js
src/multiplyDigits.test.js

index 1d3b1a88ebe72de751df5afce6faa3171f699b90..566b463062fdccc9b09fb6f769aa384e4a23fe63 100644 (file)
@@ -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".
index a7f80aecd48256be193f860600a9d568dfdca0b0..05773f33c23e5d856ec04125e1bbd68a7f2f1f1a 100644 (file)
@@ -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,
index 0bdc7d16846c18c4ccd09ca8e55cf63c501bbd4b..ea828707fbba578d77d6dc87c1995a6b0fbec7dd 100644 (file)
@@ -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 + '`');
index f31460e2713f8213418bc79d94514407d406fc96..bb0620b1837601e968f0a5efc3967c39180af414 100644 (file)
@@ -26,6 +26,5 @@ export default function joinDigits(
 ): string {
   return digits
     .map(number => encode(number, base))
-    .reverse()
     .join('');
 }
index 1e43f14018aa18c19e1e2f9cddcf79044b93041e..b3690633defd9f46395963e39f908e27224d8cc5 100644 (file)
@@ -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]);
   });
 });