Sometimes maths really confuses me... I have to be honest, I work with computers because I'm pretty good at asking them for results for things, and I know really quite well how to feed a calculation into the machine.

But, the source of these calculations is generally going to be mathematical and I find maths just to be so annoying...

Here's the information from Numberphile about Factorials...

Right, so they started with the factorial of 5 (5!) being 4 x 3 x 2 x 1 = 120. And yes you can do this and ask your computer code to do it for you:

int factorial = 5 x 4 x 3 x 2 x 1;

cout << factorial;

Not problem, we can even write a program to do this function for us, quickly...

int factorial (const int& p_Factorial)

{

int l_result = p_Factorial;

int l_temp = p_Factorial - 1;

while ( l_temp > 0 )

{

l_result = l_result * l_temp;

l_temp--;

}

return l_result;

}

This code follows the first example they give in the video, and it presents correct results for all factorials of 1 and above. This also matches with the graph drawn in the video.

This also goes back to what is stated in the video around the 0:45 second mark... "you can go down to 3 x 2 x 1", does Dr Grime mean you can take factorials down to one? If so, then this code is correct, and this rule controls the while loop in there.

Except of course zero raises its ugly head, and breaks everything, now to explain zero the pattern above is not followed, a new pattern is invented, and this is where it gets sticky for computers and my brain, because the new pattern is not multiplication, its division...

If we approach the pattern above as multiplication, then my brain tells me the pattern, the parameter even, for the function starts 0, and then ends. So to my mind zero factorial is immediately zero and the function ends:

int factorial (const int& p_Factorial)

{

int l_result = p_Factorial;

if ( p_Factorial > 0 )

{

int l_temp = p_Factorial - 1;

while ( l_temp > 0 )

{

l_result = l_result * l_temp;

l_temp--;

}

}

return l_result;

}

Or in fact I'd like to make the function throw an "invalid argument" and only let it calculate for integers of value one and above.

But this is not the pattern held to, no as you can see the pattern becomes "Take a factorial you've not calculated and use it as a parameter into the local calculation" this is a bit alien to a programming language function, take something you've not calculated as the parameter... what?

So, the function becomes something cyclic, or even two functions:

int factorialPreStep (const int& p_Factorial)

{

int l_result = p_Factorial;

if ( p_Factorial > 0 )

{

int l_temp = p_Factorial - 1;

while (l_temp > 0)

{

l_result = l_result * l_temp;

l_temp--;

}

}

return l_result;

}

int factorial (const int& p_Factorial)

{

int l_result = factorialPreStep(p_Factorial+1);

l_result = l_result / (p_Factorial + 1);

return l_result;

}

Now, the function "factorial" will always need to be passed 0 or higher, and it'll therefore always pass 1 or higher to the pre-calculation.

The full application therefore is:

#include <iostream>

using namespace std;

int factorialPreStep (const int& p_Factorial)

{

int l_result = p_Factorial;

if ( p_Factorial > 0 )

{

int l_temp = p_Factorial - 1;

do

{

l_result = l_result * l_temp;

l_temp--;

}

while ( l_temp > 0 );

}

return l_result;

}

int factorial (const int& p_Factorial)

{

int l_result = factorialPreStep(p_Factorial+1);

l_result = l_result / (p_Factorial+1);

return l_result;

}

int main (int p_argc, char** p_argv)

{

cout << factorial(5) << endl;

cout << factorial(4) << endl;

cout << factorial(3) << endl;

cout << factorial(2) << endl;

cout << factorial(1) << endl;

return 0;

}

And we see the output:

Right, so this code works? With zero?...... HMmmm, lets see....

Yes, it works for zero factorial, which as per the video comes out as one, but this was by using the division pattern... 1 / 1 = 1, that's fair I get that... But it is not the same as the original multiplication pattern.

The original pattern, the original function, is a x b x c... so 5 x 4 x 3 x 2 x 1.... What is that pattern for one factorial?... Well the pattern is just 1... so what's the pattern for 0... well it's bleeding 0....

As a programmer this is an obvious avenue of research, we like to find multiple ways to get the same result, usually so we can find the most efficient solution for runtime, but what we don't like is two seemingly matching patterns, giving different results...

So for this code we could have written:

cout << factorial(5) << endl;

cout << factorial(4) << endl;

cout << factorial(3) << endl;

cout << factorial(2) << endl;

cout << factorial(1) << endl;

as:

cout << (5 * 4 * 3 * 2 * 1) << endl;

cout << (4 * 3 * 2 * 1) << endl;

cout << (3 * 2 * 1) << endl;

cout << (2 * 1) << endl;

cout << (1) << endl;

The pattern is right, the results are right, the code is right, but then we add 0!...

cout << (0) << endl;

And it most certainly is not right, the pattern is broken, so was it a valid pattern? Well it must have been because we use this pattern in our loop to calculate the prefactorial step...

Argh, see my head just exploded.... I hate maths for this.

And it only hurts my head more as I understand my solution code, and that solution code works... GRRRR.

I was reading your blog and i was very, very fucking bored.

ReplyDeleteSo i was wondering why you didn't just stuff the base case in the return value, like so:

inline long long unsigned int factorial(unsigned int num) {

long long unsigned int ret=1;

for(;num>=1;ret*=num,num--);

return ret;

}

And used correct typing because, well, factorials only work with positive numbers.

Glad you were bored, that's the whole point... Your point is mute however, I'm not interested in efficiency, if I were I'd have told you to pass by preference. My point it the maths confuses me, not the programming... The Maths video points out a factorial of zero does not compute, but I can compute it with the code shown... Which is why I find maths so annoying at times.

DeleteYour code does not compute zero, because it skips, with its iterator starting at one...

So thanks for the fucking comment, but you miss the point... which is why can't a factorial compute as zero?... My code computes other factorials AND will compute the zero case.