Factorials (C#)
-
Marc Clifton wrote:
why people call something fast that has an unnecessary recursive call.
Not only slow, but dangerous as well - give it a big enough number and you will have a stack overflow.
Nemanja Trifunovic wrote:
give it a big enough number and you will have a stack overflow
Or small numbers like 0, -1, -2 Since 0! = 1, it is not implemented correctly for 0.
My .NET Business Application Framework My Home Page My Younger Son & His "PET"
-
This is not a programming question. I was annoyed to find that the Math class doesn't include a Factorial method, so I went off to google and found this page Fast Recursive Factorial function[^] Here's the fellow's code:
public static long Factorial(long val)
{
return val == 1 ? val:val*Factorial(val - 1);
}I gotta wonder, why people call something fast that has an unnecessary recursive call. [grandpa Marc] Back in the days, function calls were expensive. I realize these things can now be optimized by CPU caching and all that, but still... [/grandpa Marc] OK, so why did I even bother to google for this function? Because first off, I wasn't ready to accept that the Math class doesn't have a factorial method. I figured it might be called "ObfuscatedJustForMarc". And, I figured, there's probably something more going on than just an iterative multiplication, which is the obvious answer. Sure enough! Marc
Well that shows why the Math class should contain a Factorial method -- "they" should pick the best (or most difficult to implement) and provide it so "we" can simply use it.
-
Well that shows why the Math class should contain a Factorial method -- "they" should pick the best (or most difficult to implement) and provide it so "we" can simply use it.
IF they did our CS professors would wear out their 0 keys grading assignments like this:
int FactorialHomeWork(int i)
{
Return System.Math.Factorial(i);
}Today's lesson is brought to you by the word "niggardly". Remember kids, don't attribute to racism what can be explained by Scandinavian language roots. -- Robert Royall
-
Marc Clifton wrote:
public static long Factorial(long val) { return val == 1 ? val:val*Factorial(val - 1); } why people call something fast that has an unnecessary recursive call
I think that's the least of its problems. Try the following and call me tomorrow (or next century):
long Result = Factorial(-1);:-DMy .NET Business Application Framework My Home Page My Younger Son & His "PET"
...or when he gets stack overflow, which should be pretty fast matter of seconds I guess.
-
...or when he gets stack overflow, which should be pretty fast matter of seconds I guess.
Mladen Jankovic wrote:
...or when he gets stack overflow, which should be pretty fast matter of seconds I guess.
Don't you know Marc's other name is Chuck Norris? He is using 64,000,000,000 bit long integers, unlike the rest of us. :-D
My .NET Business Application Framework My Home Page My Younger Son & His "PET"
modified on Thursday, September 18, 2008 3:24 PM
-
IF they did our CS professors would wear out their 0 keys grading assignments like this:
int FactorialHomeWork(int i)
{
Return System.Math.Factorial(i);
}Today's lesson is brought to you by the word "niggardly". Remember kids, don't attribute to racism what can be explained by Scandinavian language roots. -- Robert Royall
Partial credit if the student makes it an Extension Method?
-
This is not a programming question. I was annoyed to find that the Math class doesn't include a Factorial method, so I went off to google and found this page Fast Recursive Factorial function[^] Here's the fellow's code:
public static long Factorial(long val)
{
return val == 1 ? val:val*Factorial(val - 1);
}I gotta wonder, why people call something fast that has an unnecessary recursive call. [grandpa Marc] Back in the days, function calls were expensive. I realize these things can now be optimized by CPU caching and all that, but still... [/grandpa Marc] OK, so why did I even bother to google for this function? Because first off, I wasn't ready to accept that the Math class doesn't have a factorial method. I figured it might be called "ObfuscatedJustForMarc". And, I figured, there's probably something more going on than just an iterative multiplication, which is the obvious answer. Sure enough! Marc
Marc Clifton wrote:
I was annoyed to find that the Math class doesn't include a Factorial method
Too bad C# doesn't support extension methods for static classes. You could have written something like:
public static class MyExtensions
{
public static ulong factorial(this System.Math, int factor) { ... } ; // THIS WONT WORK
}and called :
ulong factorial = Math.factorial(10);But... nope. I guess you could do this:namespace MarcsCoolStuff
{
public static class Math
{
public static ulong factorial(int factor)
{
ulong[] factorials = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
39916800, 479001600, 6227020800, 87178291200, 1307674368000,
20922789888000, 355687428096000, 6402373705728000,
121645100408832000, 2432902008176640000, 14197454024290336768 };return factorials\[factor\]; } }}
Wrap the array lookup around a try/catch IndexOutOfRange exception if you want bounds checking. And now you can call:
ulong factorial = MarcsCoolStuff.Math.factorial(10);;) Nah, don't do that. It's too obtuse to "fake" a Math class. It's screaming fast though. -
Marc Clifton wrote:
I was annoyed to find that the Math class doesn't include a Factorial method
Too bad C# doesn't support extension methods for static classes. You could have written something like:
public static class MyExtensions
{
public static ulong factorial(this System.Math, int factor) { ... } ; // THIS WONT WORK
}and called :
ulong factorial = Math.factorial(10);But... nope. I guess you could do this:namespace MarcsCoolStuff
{
public static class Math
{
public static ulong factorial(int factor)
{
ulong[] factorials = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
39916800, 479001600, 6227020800, 87178291200, 1307674368000,
20922789888000, 355687428096000, 6402373705728000,
121645100408832000, 2432902008176640000, 14197454024290336768 };return factorials\[factor\]; } }}
Wrap the array lookup around a try/catch IndexOutOfRange exception if you want bounds checking. And now you can call:
ulong factorial = MarcsCoolStuff.Math.factorial(10);;) Nah, don't do that. It's too obtuse to "fake" a Math class. It's screaming fast though.Brilliant!
The narrow specialist in the broad sense of the word is a complete idiot in the narrow sense of the word. Advertise here – minimum three posts per day are guaranteed.
-
This is not a programming question. I was annoyed to find that the Math class doesn't include a Factorial method, so I went off to google and found this page Fast Recursive Factorial function[^] Here's the fellow's code:
public static long Factorial(long val)
{
return val == 1 ? val:val*Factorial(val - 1);
}I gotta wonder, why people call something fast that has an unnecessary recursive call. [grandpa Marc] Back in the days, function calls were expensive. I realize these things can now be optimized by CPU caching and all that, but still... [/grandpa Marc] OK, so why did I even bother to google for this function? Because first off, I wasn't ready to accept that the Math class doesn't have a factorial method. I figured it might be called "ObfuscatedJustForMarc". And, I figured, there's probably something more going on than just an iterative multiplication, which is the obvious answer. Sure enough! Marc
The largest number representable in .NET for UInt64, Decimal, and Double are about 1.84E19, 3.96E28, and 1.80E308 respectively. The factorial of 28 is already 3.05E29, which is bigger than what any number type (except the Double) can represent in .NET. The Double type has its own problems too. Beyond 4.50E15, integers can't be represented accurately anymore since a Double only has a maximum of 52 bits to represent an integer with. You might as well as craft a method to look up the answer in a pre-made dictionary or table of some sort. I don't know what your needs are or if I'm completely wrong, so feel free to correct me.
So the creationist says: Everything must have a designer. God designed everything. I say: Why is God the only exception? Why not make the "designs" (like man) exceptions and make God a creation of man?
-
Mladen Jankovic wrote:
...or when he gets stack overflow, which should be pretty fast matter of seconds I guess.
Don't you know Marc's other name is Chuck Norris? He is using 64,000,000,000 bit long integers, unlike the rest of us. :-D
My .NET Business Application Framework My Home Page My Younger Son & His "PET"
modified on Thursday, September 18, 2008 3:24 PM
loving the chuck norris references! :laugh:
Billy. MCPD Windows Developer "Duct tape is like the force, it has a light side, a dark side and it holds the universe together!" - Anonymous my holding page..more coming soon!
-
The largest number representable in .NET for UInt64, Decimal, and Double are about 1.84E19, 3.96E28, and 1.80E308 respectively. The factorial of 28 is already 3.05E29, which is bigger than what any number type (except the Double) can represent in .NET. The Double type has its own problems too. Beyond 4.50E15, integers can't be represented accurately anymore since a Double only has a maximum of 52 bits to represent an integer with. You might as well as craft a method to look up the answer in a pre-made dictionary or table of some sort. I don't know what your needs are or if I'm completely wrong, so feel free to correct me.
So the creationist says: Everything must have a designer. God designed everything. I say: Why is God the only exception? Why not make the "designs" (like man) exceptions and make God a creation of man?
Ri Qen-Sin wrote:
You might as well as craft a method to look up the answer in a pre-made dictionary or table of some sort.
I just posted this above:
public static ulong factorial(int factor) { ulong\[\] factorials = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 14197454024290336768 }; return factorials\[factor\]; }An unsigned long value will overrun after 21!.
-
The largest number representable in .NET for UInt64, Decimal, and Double are about 1.84E19, 3.96E28, and 1.80E308 respectively. The factorial of 28 is already 3.05E29, which is bigger than what any number type (except the Double) can represent in .NET. The Double type has its own problems too. Beyond 4.50E15, integers can't be represented accurately anymore since a Double only has a maximum of 52 bits to represent an integer with. You might as well as craft a method to look up the answer in a pre-made dictionary or table of some sort. I don't know what your needs are or if I'm completely wrong, so feel free to correct me.
So the creationist says: Everything must have a designer. God designed everything. I say: Why is God the only exception? Why not make the "designs" (like man) exceptions and make God a creation of man?
Ri Qen-Sin wrote:
I don't know what your needs are or if I'm completely wrong, so feel free to correct me.
I need to get the # of combinations for C(58, 8) or even larger numbers like C(64, 12). Since the math is n! / (k! * (n-k)!) It seems I can simplify this to: ((n) * (n-1) * (n-2) * ... * (n-(k+1)) / k! Which becomes a computation that even a long can handle. Marc
-
Ri Qen-Sin wrote:
You might as well as craft a method to look up the answer in a pre-made dictionary or table of some sort.
I just posted this above:
public static ulong factorial(int factor) { ulong\[\] factorials = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 14197454024290336768 }; return factorials\[factor\]; }An unsigned long value will overrun after 21!.
Using my calculator, it appears that the Decimal type can handle up to 27!, and the Decimal type happens to have 95-bits for the integer part. I suppose a BigInt type would be used beyond 27! if an exact result is needed.
So the creationist says: Everything must have a designer. God designed everything. I say: Why is God the only exception? Why not make the "designs" (like man) exceptions and make God a creation of man?
-
Ri Qen-Sin wrote:
I don't know what your needs are or if I'm completely wrong, so feel free to correct me.
I need to get the # of combinations for C(58, 8) or even larger numbers like C(64, 12). Since the math is n! / (k! * (n-k)!) It seems I can simplify this to: ((n) * (n-1) * (n-2) * ... * (n-(k+1)) / k! Which becomes a computation that even a long can handle. Marc
Ah, nice. I played around with it, and it seems that n_C_r will work as long as n is less than 68.
So the creationist says: Everything must have a designer. God designed everything. I say: Why is God the only exception? Why not make the "designs" (like man) exceptions and make God a creation of man?
-
This is not a programming question. I was annoyed to find that the Math class doesn't include a Factorial method, so I went off to google and found this page Fast Recursive Factorial function[^] Here's the fellow's code:
public static long Factorial(long val)
{
return val == 1 ? val:val*Factorial(val - 1);
}I gotta wonder, why people call something fast that has an unnecessary recursive call. [grandpa Marc] Back in the days, function calls were expensive. I realize these things can now be optimized by CPU caching and all that, but still... [/grandpa Marc] OK, so why did I even bother to google for this function? Because first off, I wasn't ready to accept that the Math class doesn't have a factorial method. I figured it might be called "ObfuscatedJustForMarc". And, I figured, there's probably something more going on than just an iterative multiplication, which is the obvious answer. Sure enough! Marc
Marc Clifton wrote:
I gotta wonder, why people call something fast that has an unnecessary recursive call.
Of course, if you write your code in a tail-recursive form, using a language/compiler combo that does tail-call optimisations, it will be as fast as the imperative form. Too bad your fellow's done none of that :-)
