I saw this question this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod\limits_{i=1}^{\frac{n}{2}}( \sum\limits_{z=0}^i (n - z\times2))((\lceil{\frac{n}{2}\rceil})\$ (if n is odd)\$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod\limits_{i=1}^{\frac{n}{2}}( \sum\limits_{z=0}^i (n - z\times2))((\lceil{\frac{n}{2}\rceil})\$ (if n is odd)\$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod\limits_{i=1}^{\frac{n}{2}}( \sum\limits_{z=0}^i (n - z\times2))((\lceil{\frac{n}{2}\rceil})\$ (if n is odd)\$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod_{i=1}^{n/2}( \sum_{z=0}^i (n - z*2))((\lceil{n/2\rceil})\$\$\prod\limits_{i=1}^{\frac{n}{2}}( \sum\limits_{z=0}^i (n - z\times2))((\lceil{\frac{n}{2}\rceil})\$ ((if n is odd))\$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod_{i=1}^{n/2}( \sum_{z=0}^i (n - z*2))((\lceil{n/2\rceil})\$ (if n is odd)\$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod\limits_{i=1}^{\frac{n}{2}}( \sum\limits_{z=0}^i (n - z\times2))((\lceil{\frac{n}{2}\rceil})\$ (if n is odd)\$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$\prod_1^n n\$\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod_{i=1}^{n/2}( \sum_{z=0}^i (n - z*2))((\lceil{n/2\rceil})\$ (if n is odd) \$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$\prod_1^n n\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod_{i=1}^{n/2}( \sum_{z=0}^i (n - z*2))((\lceil{n/2\rceil})\$ (if n is odd) \$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).
I saw this question, but was unable to answer because of my inexistant knowledge of Rust, so I decided to try and write an algorithm on my own and put it for review.
There is the casual way to compute factorials:
\$n! = \prod\limits_{k=1}^n k\$
public static BigInteger fact(BigInteger n) => n == 0 ? 1 : n*fact(n - 1);
The problem with this one is that with big factorials, it get's slow (or, in this case, throw a StackOverflowException.
Now, reading this "paper", I figured I'd try to implement a faster algorithm to compute factorials.
From what I understood, the equation would look something like this :
\$\prod_{i=1}^{n/2}( \sum_{z=0}^i (n - z*2))((\lceil{n/2\rceil})\$ (if n is odd) \$)\$
The idea is to reduce the number of multiplications by half.
public static BigInteger Factorial(int n)
{
BigInteger sum = n;
BigInteger result = n;
for (int i = n - 2; i > 1; i -= 2)
{
sum = (sum + i);
result *= sum;
}
if (n % 2 != 0)
result *= (BigInteger)Math.Round((double)n / 2, MidpointRounding.AwayFromZero);
return result;
}
I decided to keep a sum variable so I don't need to redo the sum computing at each multiplication's iteration.
I'd like to see if I missed something or if this can be optimized. (I'm doing this as a mathematical exercise, so there's no need for performance, I'm looking at ways to make it more performant just because I want to understant the maths behind it).