8
$\begingroup$

I've been searching the internet for quite a while now to find anything useful that could help me to figure out how to calculate factorial of a certain number without using calculator but no luck whatsoever.

I'm well aware of the fact that there is a way to calculate any number of sigma (summation notation sigma) but haven't figured out anything for factorials yet. Could you please show me any method that should do the trick.

E.g. factorial of 10! is 3628800 but how do I calculate it without using any sorts of calculator or calculate the numbers from 10 to 1?

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Multiply 10 by 9 by 8....by 2. It's a lot of work, but that is how you would do it by "pen-and-paper" $\endgroup$ – Zach466920 Jun 29 '15 at 16:14
  • $\begingroup$ Thanks @Zach466920 but as I wrote in my last sentence, without any of these, no calculation from n to 1. So I assume there is not a possible way to do that? $\endgroup$ – Teo Carter Jun 29 '15 at 16:16
  • 2
    $\begingroup$ You could calculate $n! = \exp(\log(1) + \log(2) + \ldots + \log(n))$ using a log table. $\endgroup$ – Jair Taylor Jun 29 '15 at 16:18
  • 6
    $\begingroup$ @JairTaylor you could calculate $n!=1*2*3...*n$ using a multiplication table ;) $\endgroup$ – Zach466920 Jun 29 '15 at 16:20
  • $\begingroup$ There is no simpler exact formula, as far as I know. $\endgroup$ – user228113 Jun 29 '15 at 16:26
8
$\begingroup$

Rewriting the factorial as the Gamma function and Stirling's approximation we get what I think is the closest possible approximation that you could do by hand:

$$n! \approx \sqrt{2 \pi n} \cdot \left( \frac{n}{e} \right)^n$$

Where $e = 2.71828\dots$. Unfortunately, this might not be quicker than multiplying all the numbers together by hand, but it's certainly the only shortcut I can think of that could be done by hand.

$\endgroup$
  • 2
    $\begingroup$ That approximation actually involves $n$ multiplications....so it's equal to or less efficient than doing it by brute force. $\endgroup$ – Zach466920 Jun 29 '15 at 16:21
  • 2
    $\begingroup$ @Zach466920 not true - exponentiation can be done in $\log_2 (n)$ multiplications :) $\endgroup$ – lisyarus Jun 29 '15 at 16:22
  • $\begingroup$ @lisyarus I'll assume your joking, since this is pencil and paper we are talking about... ;) $\endgroup$ – Zach466920 Jun 29 '15 at 16:23
  • 1
    $\begingroup$ @Zach466920 actually, I'm not. It's very easy to put the power into binary form and reduce the multiplications to at most $\log_2 n$ multiplications plus at most $\log_2 n$ squarings. $\endgroup$ – lisyarus Jun 29 '15 at 16:26
  • 1
    $\begingroup$ @lisyarus Ok, yes. There are exceptions to exceptions, I get it...I just assumed since its used in many numerical systems, it might be the most efficient. $\endgroup$ – Zach466920 Jun 29 '15 at 17:12
4
$\begingroup$

I see that this is an old question and the conversation thread is most likely completely dead. However, there is a partial shortcut to calculating fairly length factorials. Being that multiplication is commutative, the order in which multiplication is done can be rearranged...

Take, for example, 10! which equals 1*2*3*4*5*6*7*8*9*10, this can be rearranged as (10*1)*(9*2)*(8*3)*(7*4)*(6*5) → 10*18*24*28*30

One thing that you will (or should) notice about the delta between the product of each pairing is that it always decreases by a value of 2, and always begins with a value of n-2. For n!, where n=10, the delta between the first two products will be n-2, or 8. The delta between the products of successive pairs will always decrease by 2. In other words, when the pairing is done as illustrated above (pairing the highest value number with the lowest, second highest with the second lowest, etc), then the product of each pairing will increase by a value that decreases by an amount of 2 for each successive pairing. This makes calculating the products of a long list of number pairs relatively easy.

For n!, where n=10, we know that 1*10=10, we also know that the next pairing will result in 10+8, or 18... the next paring will result in a product of 18+6=24, followed by 24+4=28, and finally by 28+2=30.

Without having to calculate each product, we can quickly predict what they will be.

This works for factorials of odd numbers as well, except that there will be one number at the end that will not have a pairing. 7!, for example, could be written as (1*7)*(2*6)*(3*5)*4 → 7*12*15*4. The initial product is 7, and the product of the next pairing is 7+(n-2) or 7+5, which of course equals 12. The next product is 12+3, or 15. So the solution to 7! would be 7*12*15*4.

As a generalized rule, it can be said that the initial delta between the products of the first and second pairings will be n-2, this delta will always decrease by a value of 2 for each successive pairing, and the final delta will always be either 2 or 3 (depending on whether we are dealing with the factorial of an even number or an odd number [2 or greater]).

Again, this is only a partial shortcut. It essentially reduces the number of calculations you need to perform by half... but if you absolutely need to do calculate 100! by hand, performing approximately half of the necessary steps would make a significant difference. :)

$\endgroup$
1
$\begingroup$

No, but you can if you accept approximations.

Since the factorial function is defined recursively, $(n+1)!=n! \cdot (n+1)$, your question boils down to whether or not the recurrence relation has a closed form solution, which it doesn't have. You want to be able to skip around calculating $1!$ through $9!$. However $10!$ is defined by $9!$, so there isn't a way of skipping the intermediate steps.

$\endgroup$
  • $\begingroup$ Ah.. well approximations is the best thing we can get I suppose since it involves multiple level of multiplications. Thanks @Zach466920 :) $\endgroup$ – Teo Carter Jun 29 '15 at 16:26
  • $\begingroup$ @Zach466920 I think there is a typo.$$(n+1)!=(n+1).n!$$ $\endgroup$ – Integrator Jun 29 '15 at 16:28
  • $\begingroup$ @Integrator thanks :) $\endgroup$ – Zach466920 Jun 29 '15 at 16:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.