Efficient Factorials Calculation !

Recursive Approach:def calculate_factorial_recursive(number):
”’
This function takes one agruments and
returns the factorials of that number
This is naive recursive approach
”’
#base case
if number == 1 or number == 0:
return 1
return number * calculate_factorial_recursive(number – 1)The Recursive approach is not the best approach. It will giveRuntimeError: maximum recursion depth exceeded. for large number as python doesn’t have optimizedtail recursionBut it have been written for pedagogical purposes, to illustrate the effect of several fundamental algorithmic optimizations in the n factorial of a very large number.First Improvement : Successive Multiplicative ApproachThis function uses the approach successive multiplication
like 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1def calculate_factorial_multi(number):

if number == 1 or number == 0:
return 1

result = 1 # variable to hold the result

for x in xrange(1, number + 1, 1):
result *= x
return resultThe profiled result for this function :For n = 1000 — Total time: 0.001115 sfor n = 10000 — Total time: 0.035327 sfor n = 100000 — Total time: 3.77454 s.Now If we see theresultfrom line_profiler we will see that most %time was spent in multiplication step of the above code i.eresult *= xwhich is almost 98%.Second Improvement : Reduce the number of successive multiplicationAs the multiplication is very costly especially for a large number , we can use the pattern and reduces the number of multiplication by half.
Lets group the above 8! example 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 – together:8! = (8 * 1) * (7 * 2) * (6 * 3) * (5 * 4)which can be written as8! = 8 * (8 + 6 = 14) * (14 + 4 = 18) * (18 + 2).so first factor is the number we are taking. second factor is the first factor
plus first factor minus two from the factor
and then in next we multiply the result with added result.
Odd number also follows the same pattern till even just handle the case of one odd.Code to do the same:Python :def calculate_factorial_multi_half(number):

if number == 1 or number == 0:
return 1

handle_odd = False
upto_number = number

if number & 1 == 1:
upto_number -= 1
print upto_number
handle_odd = True

next_sum = upto_number
next_multi = upto_number
factorial = 1

while next_sum >= 2:
factorial *= next_multi
next_sum -= 2
next_multi += next_sum

if handle_odd:
factorial *= number

return factorialThe profiled result for this function :For n = 1000 — Total time: 0.00115 sfor n = 10000 — Total time: 0.023636 sfor n = 100000 — Total time: 3.65019 sIt is not optimised very much, but are at least not obscenely slow.
It’s shows some improvement in the mid range but didn’t improved much with scaling.
In this function too most of the %time is spent on multiplication:Java Code for the same:private static void calculateFactorial(int uptoValue) {
BigInteger answer=BigInteger.ONE;
boolean oddUptoValue=((uptoValue&1)==1);
int tempUptoValue=uptoValue;
if(oddUptoValue){
tempUptoValue=uptoValue-1;
}

int nextSum = tempUptoValue;
int nextMulti = tempUptoValue;
while (nextSum >= 2){
answer=answer.multiply(BigInteger.valueOf(nextMulti));
nextSum -= 2;
nextMulti += nextSum;
// long product=(tempUptoValue-i+1L)*i;

}
if(oddUptoValue){
answer=answer.multiply(BigInteger.valueOf(uptoValue));
}
System.out.println(answer);
}Further Improvement : Usingprime decompositionto reduce the total number of multiplicationSince there are (number / ln number) prime number smaller than number
so we can further reduce the total number of multiplicationdef calculate_factorial_prime_decompose(number):

prime = [True]*(number + 1)
result = 1
for i in xrange (2, number+1):
if prime[i]:
#update prime table
j = i+i
while j <= number:
prime[j] = False
j += i
sum = 0
t = i
while t <= number:
sum += number/t
t *= i
result *= i**sum
return resultThe profiled result for this function :n = 1000 — Total time = 0.007484 sn = 10000 — Total time = 0.061662 sn = 100000 — Total time = 2.45769 sYou can see the detailed profiled result of all the discussed algorithms preparedhere, in case if you want to see.Practice ProblemSmall Factorial

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *