1
$\begingroup$

First we need to present the details of what makes that cut possible. The issue is linked to the sum of squares $1^2+2^2+3^2+4^2+...+n^2$.
We consider the two cases:
1-the case of a sum of even squares
2-the case of a sum of odd squares.
However both sums lead to practically the same result which is a cut of the number of multiplications by half.

Here we consider the two cases, odd and even squares, with a new way of calculating the sum of squares. The sum in both cases involves summing up numbers that are not squares and are located in diagonals perpendicular to the main diagonal of the squares $1^2,2^2,3^2,4^2,5^2...$.

1- case of the sum of odd squares: $1^2$ is just $1^2$. However the first sum we consider is $1^2+3^2=10$ but also $1^2+3^2=3+4+3=10$. Here $3+4+3$ are the elements of the perpendicular to the main diagonal and passing through $3,4,3$ to add up to $10$. The example of $1^2+3^2+5^2=35=5+8+9+8+5$ is another example. Here also $5+8+9+8+5$ are the elements of the perpendicular to the main diagonal and going through $5,8,9,8,5$. We can give other examples but they all add up to the sum of squares calculated with squares $1^2+3^2+5^2+...(2n+1)^2$.

2- case of the sum of even squares: In this case, the first element is always even but all the elements of the diagonal perpendicular to the main diagonal are even as opposed to the odd case where some elements can be even or odd, except of course the first one which is always odd. To give an example, $0^2+2^2+4^2=4+16=20=4+6+6+4$. So $4,6,6,4$ are the elements of the diagonal that add up to $20$. Like in the odd case, we can give more examples but they will confirm the rules for sums of odd or even squares. Formulas for the sums are given in the OEIS but no mention is made that they are calculated as shown in this post.

Calculating factorial $n$ using the sum of odd and even squares:

1- the odd case
factorial(5) is given by $5!=1⋅2⋅3⋅4⋅5=120$. Multiplying the elements given above for $1^2+3^2+5^2=35=5+8+9+8+5=35$ gives $5⋅8⋅9⋅8⋅5=14400=120^2$ which is exactly the square of $5!$. So it is clear that we need to eliminate some elements of the product $5⋅8⋅9⋅8⋅5$ and leave only $5⋅8⋅3=120$ which is basically half the number of multiplications needed to get $5!$. This is a general rule that applies to all cases involving factorial of odd numbers. The question of which numbers are involved is shown below. We will just copy the numbers from the multiplication table for factorial of odd numbers to show how the numbers to be multiplied are selected.
$3!=3⋅2$
$5!=5⋅8⋅3$
$7!=7⋅12⋅15⋅4$
$9!=9⋅16⋅21⋅24⋅5$
These few examples show that the element coming after the starting point $5$ is: $8=5+3$. The element to add to the number whose factorial we want is always the previous odd element in the first column, in this case $3$. The next element is $3$ which is the square root of $9$. The number of elements that need to be multiplied is $(n+1)/2=(5+1)/2=3$. A reminder for the case of a factorial of an odd number is that each element is always a square away from the element at the intersection of the main diagonal and the perpendicular diagonal. In the case of $5$ we see that $9−5=4=2^2$ and $8−9=1^2=1$. The last element is always the square root of the square on the diagonal of squares, in this case $3$. So now we have the 3 numbers needed to calculate $5!$. The last element is simply given by $l=(5+1)/2=3$, so in fact, there is no need to take any square root. This has to do with the fact that the diagonal starting with $5$ is aligned with the square $3^2=9$ so both $5$ and $9$ have the same sum of factors $6$. The last element is just the factor $q$ of $q^2$, which in this case is $3$ or $(5+1)/2$.

The element coming after the starting point 7 is: $7+5=12$. The element to add to the number whose factorial we want is always the previous odd element, in this case $5$. This can be easily checked by looking at the multiplication table. The next number to add to $12$ to get the next element is $3$ so that $7$ is distant from the square $16$ by $5+3+1=9$. The number of elements to multiply is $(7+1)/2=4$ so we have $7!=7⋅12⋅15⋅4=5040$. The element before the last number is always $1$ less than the square of the last element, here $15=4^2−1$.

2 the even case The even case is a bit different since the numbers involved are on a line perpendicular to the main diagonal but passing between two squares of the main diagonal. A quick look at the multiplication table will confirm that. In this case there are as many elements on each side of the main diagonal so there is no need to consider the square root or the factors of a square. We give few examples to show how the numbers involved in the multiplication are determined.
$2!=1⋅2=2$
$4!=4⋅6=24$
$6!=6⋅10⋅12=720$
$8!=8⋅14⋅18⋅20=40320$
Here too we see that the number of multiplications to get $n!$ has been halved. The same rule to determine the next element applies here. if we look at $6!$, we see that we need to add $4$ to get $10$ and $4$ is just the previous even number below $6$. The next number is $10+2=12$ and this will be the last number needed to calculate $6!$. The rule is to decrease the number by $2$ until we get to the last number. We stop when we have added $2$ to whatever previous number is. In summary, for the factorial of odd numbers $1,3,5,...2n+1$, we add odd numbers to the starting number whose factorial we want. For factorial of even numbers, we add even numbers $2,4,6...2n$. The numbers are given in reverse order as explained previously.

One last thing to show the equivalence between the two methods of calculating a factorial.
$8!=1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8=40320$.

The above method is equivalent to eliminating some of the factors, two at a time, but without having to do the multiplications. $7\cdot2$ was replaced by its value with the addition $8+6$ as explained above. $6\cdot3$ was replaced by $14+4$. Latsly, $5\cdot4$ was replaced by $18+2$ so we end up with $8!=8\cdot14\cdot18\cdot20=40320$. For the odd case the same principle of replacing factors in the classical way by their values calculated as shown above. The only difference is the handling of the middle term which is always a square and whose value is given by $(n+1)/2$ with $n$ the number whose factorial is to be calculated.

Edit March 21 2023 A further reduction of the number of multiply for odd numbers.

It turned out that we can calculate an odd factorial using numbers from an even factorial. This trick will decrease the number of multiplications needed by one.

$7!=1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7=5040$.
$7!=7\cdot12\cdot15\cdot4=5040$

Instead of using $7!$ and getting the numbers needed $7,12,15,4$, we consider the even number above $7$ and get the numbers needed as explained above (for even numbers).

$8!=8\cdot14\cdot18\cdot20$. Then to get $7!$, we just drop the first number from $8!$ to get:

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

So we went from $5$ (the classical method) multiply to $3$ (the method above) to $2$ (with using the numbers from the even factorial) which is more than half the multiplications needed.

Another potential improvment would be the use of pre-stored squares and convert the factorial into a product of squares. For example, $7!=14\cdot18\cdot20$ becomes $7!=(16^2-2^2)\cdot20=14\cdot(19^2-1)$.
There are rules that provide the square to be subtracted which depend on the position of the numbers used in the factorial and their distance from the main diagonal of the multiplication table. They are given by $1^2,2^2,3^2...$

Note: I am not a computer scientist so I am not familiar with the tags needed for this method. I already posted the above in the math stack exchange but it didn't get a good reception. I thought posting it here will get more interest since faster methods of doing calculations are always welcomed. Feel free to add tags, make corrections (if needed).

$\endgroup$
8
  • 1
    $\begingroup$ Yes, you can decompose the factorial $n!$ into products of factors $(k+1)(n-k)$, $k=0,...,n/2$, with a middle term remaining for odd $n$. How does that grouping reduce the number of multiplications? $\endgroup$ Feb 21, 2023 at 12:22
  • 1
    $\begingroup$ Just compare $8!=1*2*3*4*5*6*7*8$ with $8!=8*14*18*20$, the example given in the post. Here $14$ is not $2*7$ and $18$ is not $3*6$. It's explained in the post how $14$ and $18$ are the result of additions. $\endgroup$
    – user25406
    Feb 21, 2023 at 12:44
  • $\begingroup$ You know that there is a closed formula for the sum of squares, right? $\endgroup$ Feb 21, 2023 at 13:40
  • 1
    $\begingroup$ So you replace a few multiplications by additions. To find out whether that's a win, you need to evaluate how much each addition and multiplication actually costs. $\endgroup$ Feb 21, 2023 at 18:14
  • 2
    $\begingroup$ @user25406 as an aside, if you really want savings at runtime, just precompute all factorial values up until the largest one you could see yourself needing and store them so you can readily grab their value when you need them. Given you do not use extended precision and the fact $n!$ requires around $n \log_2(n)$ bits to store, this implies you can store up to around $\text{factorial}(16)$ in 64 bit unsigned integers. $\endgroup$
    – spektr
    Feb 24, 2023 at 17:53

2 Answers 2

2
$\begingroup$

What are the benefits of cutting by half the number of multiplications needed to calculate n!

The rest of your question doesn't really refine what you're asking and it's too long for me to want to evaluate, but, broadly speaking, there are two things to think about here.

  1. Algorithmic improvements. Calculating n! takes O(N) time. Even if you reduce the number of multiplications by half, it will still take O(N) time, so there's a clear algorithmic benefit to your technique.

  2. Algorithm engineering. Algorithm engineering is a field that looks at the interplay between algorithms as abstract concepts and how they're instantiated on hardware. This MIT course might give you additional context. Whether your algorithm has benefits will depend on the hardware, how much overhead the technique adds, and other factors. In a simple serial situation for "small" inputs it seems unlikely to me that it will do better than a simple serial implementation since the for-loop accumulator is so tight.

$\endgroup$
0
2
$\begingroup$

I found this article on a method that also cuts the number of multiplications by half using a different method to get the numbers used to calculate $N!$ than the one in the above post. This method was computationally tested by the authors and was found to be faster than many other well-known methods. I am surprised that the method seems not to be well-known:

Fikret Cihan, Fatih Aydin, Adnan Fatih Kocamaz, "A New Method for Fast Computation of Factorials of Numbers", Balkan Journal of Mathematics, vol. 1, pp. 16–27, 2013. (Balkan Journal website)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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