2
$\begingroup$

There are many different methods that tried to improve the calculation of $n!$. Few of them managed to halve the number of mulitplications. One of those methods is the basis to completely remove the need for multiplications.

The method in the following post will be used as a starting point to remove the need for multiplications.

https://scicomp.stackexchange.com/questions/42510/what-are-the-benefits-of-cutting-by-half-the-number-of-multiplications-needed-to/42645#42645

We consider two simple cases to show how to get rid of the multiplications.

$8!=8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$ where all the multiplications are done.
$8=8\cdot14\cdot18\cdot20=40320$ using half the number of multiplications as shown in the link above.
To get the numbers $8,14,18,20$, we did not need to do the multiplications $(1\cdot8)$, $(2\cdot7)$... There is a much better method to get those numbers without having to do any multiplication as explain in the post above.

Half the number of multiplications is an improvement but for large numbers half of the number of multiplications is still quite a lot of work to get the final result.

The first step is to get the numbers needed to calculate the factorial with half the multiplications. That step has not changed.

$8!=8\cdot14\cdot18\cdot20=40320$

Now we pair the numbers to rewrite $8!=(8\cdot14)(18\cdot20)$. We need to remember that here we have the factors which we need to convert to a difference of squares like it's done when factoring.

$8\cdot14=[(8+14)/2]^2 - [(14-8)/2]^2 = 11^2-3^2=112$
$18\cdot20=[(18+20)/2]^2 - [(20-18)/2]^2 = 19^2 -1^2=360$

Using pre-computed square we got:
$8!=112\cdot360=40320$. However, there is not need to use the $112\cdot360$ since it can also be converted to a difference of squares.

$112\cdot360 = [(112+360)/2]^2 - [(360-112)/2]^2 = 236^2 -124^2 = 40320=8!$

So we see that $8!$ was calculated without using a single multiplication, not counting of course the ones needed to pre-compute the squares. But the pre-computed squares can be used many times without having to re-calculate them to evaluate another factorial.

There are two small issues to resolve for factorials of odd numbers.

$7!=7\cdot12\cdot15\cdot4$. The mixture of odd and even will not allow us to transform $(7\cdot12)$ and $(15\cdot4)$ as a difference of squares. So we use the numbers of the even number $8=7+1$. But we need to remember that $8!=8\cdot7!$. So it's enough to use the numbers for $8!$ and discard $8$ itself.

$7!=14\cdot18\cdot20=5040$.

Here, we pair $18$ and $20$ to get:

$18\cdot20= [(18+20)/2]^2 - [(20-18)]^2 = 19^2 - 1^2= 360$

Now we pair $14$ with $360$ to get:

$7!=14\cdot360=[(14+360)/2]^2 - [(360-14)/2]^2= 187^2 - 173^2=5040$

In the end, it doesn't really matter if the number of numbers to be paired is odd of even. For example $10!=10\cdot18\cdot24\cdot28\cdot30=10\cdot(18\cdot24)(28\cdot30)$. Finally, $10$ will be paired with the result of $(18\cdot24)(28\cdot30)$.

I only used this method with small numbers. I know that in some posts, pre-computed factorials have been suggested but that does not eliminate the multiplications. I don't know how expensive it is to calculate squares, store them, retreive them when needed...So I can't conclude how efficient this method is. More testing needs to be done using large numbers (which I cannot do). So I will ask a simple question.

Edit #1: By pre-computing squares, it was meant to compute many squares, store them in a table for future use, not just the squares needed for a given factorial.
User Servaes in his comment said "...Computing all squares up to some large bound will definitely take a long time...". Yes but once calculated, they don't need to be calculated again, they just need to be retreived from a table.

The savings will be achieved when factorials are used extensively on a daily basis for whatever purpose.

Question: How efficient is this method?

$\endgroup$
6
  • 2
    $\begingroup$ Which squares would you precompute? As your examples show, even for $n=7$ you need squares up to $187^2$, though you only use $4$ squares. Computing all squares up to some large bound will definitely take a long time. If you can tell in advance which squares might/will be needed, that could provide some savings. $\endgroup$ Commented Jun 2, 2023 at 12:49
  • $\begingroup$ It's the last pair that is making the squares grow. I will try to find a better solution. Now I don't really know what the best way to compute squares. Using additions of odd ($1+3=2^2...$) numbers will get all the needed squares but also avoid doing multiplications but I am no expert on that. $\endgroup$ Commented Jun 2, 2023 at 13:55
  • $\begingroup$ The idea of the post is to pre-compute $10$ of $10,000$ of squares and store them for future use. If one is computing a single factorial, then it's not worth it to pre-compute a huge number of squares. But if someone is working with factorials on a daily basis and needs many of them, then it makes sense to pre-compute squares. $\endgroup$ Commented Jun 2, 2023 at 18:28
  • 4
    $\begingroup$ If someone is working with factorials on a daily basis, why not just precompute and store the factorials themselves? $\endgroup$ Commented Jun 3, 2023 at 18:28
  • $\begingroup$ The choice is between precomputing factorials and squares. It may seem useless today but some day someone will find a good use for precomputing squares. $\endgroup$ Commented Aug 26, 2023 at 14:04

1 Answer 1

Reset to default
3
$\begingroup$

Let say I need to calculate $1000!$.
$1000!$ has $2568$ digits in base$10$, so we have to pre-compute all the squares up to $10^{2568}$ (approx). It is not possible to store the table with this size in memory.

UPD: Moreover, in current PC architecture, accessing memory takes approximately 10 times longer than multiplying primitive integers (up to 2^32).

From that perspective, there is no difference between multiplication and addition in terms of time complexity.

$\endgroup$
3
  • $\begingroup$ There is obviously a limit to our abilities to do some calculations. $\endgroup$ Commented Dec 13, 2024 at 11:50
  • $\begingroup$ I like the way you’re thinking, but I think you're stuck in the first iteration of some unknown recursion. Also, please note that the complexity of multiplying two n-digit numbers using the fast Fourier transformation (Schönhage–Strassen algorithm) is O(n * log(n) * loglog(n)). Using this algorithm, you can multiply two numbers with 3 * 10^6 digits in just 20–50 milliseconds. $\endgroup$ Commented Dec 13, 2024 at 12:22
  • $\begingroup$ Not being a computer scientist or a professional mathematician, my interest is limited to finding new ways to do things, like the post above or this one: scicomp.stackexchange.com/questions/42510/… $\endgroup$ Commented Dec 13, 2024 at 19:29

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.