# Digging around factorial function

Evolution of a Python programmer is a brilliant example of Python code produced by people with different backgrounds to solve a mostly simple problem of finding a factorial of the given number. Unfortunately it lacks solution which might be hypothetically produced by mathematician. Let’s add some entropy to the Universe and implement a weird factorial calculation using exponential function and logarithms: The series in the exponent can be represented as a list comprehension:

``[math.log(k) for k in range(1, x + 1)]``

For the final solution let’s find a `sum` of the series and put it inside `math.exp()`:

``````import math as m
def fact(x):
return m.exp(sum([m.log(k) for k in range(1, x+1)]))``````

But unfortunately, such calculation provides distorted results. We are dealing here with floating-point numbers, this results in the issues and limitations which are caused by the fact that floating-point numbers are represented in computer hardware as base 2 (binary) fractions. Let’s `import math as m` and examine the output: As can be seen there is a lot of ugliness after the decimal point. It is not allowable for our hypothetical mathematician! Moreover, our weird implementation is much more slower than the common iterative factorial function: Let’s fix the situation and try to write the function that calculates factorial of the given number and which is faster then the common iterative implementation. Recursive implementation is not considered because recursion in Python requires the allocation of a new stack frame and thus (in general) slower.

## Fast factorial

I was inspired by the method to half the amount of multiplying from this article.

To half the multiplication with even numbers, you will end up with the number, divided by two, factors. The first factor will be the number you are taking the factorial of, then the next will be that number plus that number minus two. The next number will be the previous number plus the lasted added number minus two. You are done when the last number you added was two.

Example from the article:

8! = 8 * (8 + 6 = 14) * (14 + 4 = 18) * (18 + 2 = 20)
8! = 8 * 14 * 18 * 20

Pay attention to the bold numbers:

8! = 8 * (8 + 6 = 14) * (14 + 4 = 18) * (18 + 2 = 20)

So, basically we have a list of the numbers `[8, 6, 4, 2]` which can be used to find factors of `8!`.

``````8! = 8 * 14 * 18 * 20 =

(8) *
(8 + 6) *
(8 + 6 + 4) *
(8 + 6 + 4 + 2) =
40320``````

Now, it becomes clear how to implement described logic in Python. All we need is:

1. Build a list of the even numbers including and below given number, e.g. for `10!` it should be `[10, 8, 6, 4, 2]`.
2. Each iteration finds next factor by adding the elements of the list: `10, 10 + 8, ..., 10 + 8 + 6 + 4 + 2`.
3. Each iteration multiplies found factors.

Here is the code:

``````def fast_fact(x):
res = 1
i = 0
nums = range(x, 0, -2)
for num in nums:
i += num
res *= i
return res``````

Wait. This method works for even numbers, how about odd ones? The most natural solution that comes to mind is finding a factorial of the even number before the odd and times it by the odd number `9! = 8! * 9`. Let’s add a hook to our function to handle odd numbers too:

``````def fast_fact(x):
if x % 2:
res = x
x -= 1
else:
res = 1

i = 0
nums = range(x, 0, -2)
for num in nums:
i += num
res *= i
return res``````

Article also mentions another method to handle odd numbers but we will not implement it since this makes solution more complicated and clarity also suffers. Now, let’s `timeit` against iterative factorial from the first part of our investigation: Now our hypothetical mathematician can be satisfied.

All code from the article is available here: some_factorials.py.

Previous post: Python zip( ) Fu

Next post: How to implement Tags at Jekyll website