Interview Question
Country: United States
Count the powers of 2 that will be included in the factorial, and use a right shift for those. Something like:
for (m = n>>1, powers_of_two = m; m; m >>= 1, powers_of_two += m);
result = 1<<powers_of_two;
for (; n>1; n--) { if (!is_power_of_two(n)) result *= n; }
That said, 13! is already larger than 2^32, so normal arithmetic isn't really practical here.
Abhishek ,
There is no improvement in no.of arthimetic operations .still it requires n-1 multiplications
Abhishek is actually right: this technique is called "binary splitting": imagine if you wish to compute factorial of a large number, then performing arithmetic on balanced operands (ie of comparable size) is more efficient than computing x! in a usual way
also to give a hint how to reduce the # of muls, observe that we can remove the power-of-two factors from the factorial expression and combine the remaining ones according to multiplicity:
e.g.: 10! = 2^8 * ( 1 * 3 * 1 * 5 * 3 * 7 * 1 * 9 * 5) =
2^8 * (3 * 5)^2 * 7 * 9
hence we need to perform 4 multiplications instead of 8..
My solution would be:
1.) use an array or hashtable or tree with the prime number + count.
2.) each number of n! can be represented by prime numbers so add count the prime numbers used in 1.
3.) iterate from the structure in 1.) and multiply
3.1) here you can optimize a little - shift left when there is multiplication of 2 instead of multiply
We can do it with all additions. For e.g. 5! can be calculated like. Add 5 four times and now the result is added 3 times and so on.
- Anonymous January 28, 2012