forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
multiply.js
41 lines (37 loc) · 1.27 KB
/
multiply.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import multiplyByTwo from './multiplyByTwo';
import divideByTwo from './divideByTwo';
import isEven from './isEven';
import isPositive from './isPositive';
/**
* Multiply two signed numbers using bitwise operations.
*
* If a is zero or b is zero or if both a and b are zeros:
* multiply(a, b) = 0
*
* If b is even:
* multiply(a, b) = multiply(2a, b/2)
*
* If b is odd and b is positive:
* multiply(a, b) = multiply(2a, (b-1)/2) + a
*
* If b is odd and b is negative:
* multiply(a, b) = multiply(2a, (b+1)/2) - a
*
* Time complexity: O(log b)
*
* @param {number} a
* @param {number} b
* @return {number}
*/
export default function multiply(a, b) {
// If a is zero or b is zero or if both a and b are zeros then the production is also zero.
if (b === 0 || a === 0) {
return 0;
}
// Otherwise we will have four different cases that are described above.
const multiplyByOddPositive = () => multiply(multiplyByTwo(a), divideByTwo(b - 1)) + a;
const multiplyByOddNegative = () => multiply(multiplyByTwo(a), divideByTwo(b + 1)) - a;
const multiplyByEven = () => multiply(multiplyByTwo(a), divideByTwo(b));
const multiplyByOdd = () => (isPositive(b) ? multiplyByOddPositive() : multiplyByOddNegative());
return isEven(b) ? multiplyByEven() : multiplyByOdd();
}