]> git.wincent.com - hextrapolate.git/blob - src/multiplyDigits.js
7554e8127d388827301567aae16adca7988aa979
[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  * Multiplication is repeated addition.
12  */
13 export default function multiplyDigits(
14   multiplicand: Array<number>,
15   multiplier: number,
16   base: number
17 ): Array<number> {
18   // Partial result being built up.
19   let result = [0];
20
21   // Running total of additions performed so far.
22   let count = 0;
23
24   // We memoize partial subresults in a stack so they can be re-used.
25   const memo = [];
26
27   while (multiplier) {
28     if (count && count * 2 < multiplier) {
29       // We can double the current result without exceeding the target.
30       result = addDigits(result, result, base);
31       multiplier -= count;
32       count *= 2;
33       memo.push({count, result});
34     } else {
35       const last = memo.pop();
36       if (last && last.count < multiplier) {
37         // We can use a previous result on the stack to leap ahead.
38         result = addDigits(result, last.result, base);
39         multiplier -= last.count;
40         count += last.count;
41       } else if (!memo.length) {
42         // Stack is empty, so fall back to base case (single addition).
43         result = addDigits(result, multiplicand, base);
44         multiplier--;
45         count++;
46         memo.push({count, result});
47       }
48     }
49   }
50
51   return result;
52 }