]> git.wincent.com - hextrapolate.git/blob - src/multiplyDigits.js
4350b36b181c51df80c8bab1d24e8fb5f237b06a
[hextrapolate.git] / src / multiplyDigits.js
1 /**
2  * Copyright 2003-present Greg Hurrell. All rights reserved.
3  * Licensed under the terms of the MIT license.
4  *
5  * @flow
6  */
7
8 import addDigits from './addDigits';
9
10 /**
11  * Multiply an array of decimal digits, `multiplicand`, by `number`, returning
12  * the result as an array of decimal digits in base `base`.
13  *
14  * Note that multiplication is implemented as repeated addition.
15  */
16 export default function multiplyDigits(
17   multiplicand: Array<number>,
18   multiplier: number,
19   base: number
20 ): Array<number> {
21   // Partial result being built up.
22   let result = [0];
23
24   // Running total of additions performed so far.
25   let count = 0;
26
27   // We memoize partial subresults in a faux-stack so they can be re-used.
28   // (Faux because we never actually pop, as an optimization.)
29   const memo = [];
30   let memoIndex = -1;
31
32   while (multiplier) {
33     if (count && count * 2 <= multiplier) {
34       // We can double the current result without exceeding the target.
35       result = addDigits(result, result, base);
36       multiplier -= count;
37       count *= 2;
38       memo.push({count, result});
39       memoIndex++;
40     } else {
41       const last = memoIndex >= 0 ? memo[memoIndex--] : null;
42       if (last && last.count <= multiplier) {
43         // We can use a previous result on the stack to leap ahead.
44         result = addDigits(result, last.result, base);
45         multiplier -= last.count;
46         count += last.count;
47       } else if (memoIndex < 0) {
48         // Stack is empty, so fall back to base case (single addition).
49         result = addDigits(result, multiplicand, base);
50         multiplier--;
51         count++;
52         memo.push({count, result});
53         memoIndex++;
54       }
55     }
56   }
57
58   return result;
59 }