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