Factorial

Here's a contest I think most people can give a try. The goal is to implement a program in C or C++ that compute precisely the factorial of N (N being an non-negative integer) as fast as possible.

For people who wouldn't know what's a factorial: http://en.wikipedia.org/wiki/Factorial
But I guess most of us have all seen somewhere as an introduction to recursion this kind of code

Code:

unsigned int factorial(unsigned int N) { if (N == 0 || N == 1) return 1; return N * factorial(N - 1); }

Of course, this code when compiled on a "normal" machine will yields incorrect result if N is larger than 12. So this doesn't interest us.

The factorial to compute will be given as a command line argument.
The result has to be print to stdout. It can be either in decimal or in hexadecimal format.

The machine specifications are:

Intel Core2 Duo (64-bit instruction set, SSE4.1 support, dual core, 6 MB of L2 cache)
4 GB of RAM

The target compiler is GCC 4.2.3 on a 64-bits Linux system (I'm using Ubuntu 8.04 64-bits). Since i'm quite new to Linux-based operating systems, don't make your code overly complicated to compile or you'll have to explain me how to get it works :). A shell script (sh or bash) or a makefile would be ideal...

And here's some rules.

You can't use mathematics libraries, except if you are the author or if it's the standard C/C++ math library. In fact, if someone want to use an "advanced" mathematic library, he can but his program won't be taken into account when it will be time to declare the winner of the contest.
You can't use pre-calculated factorial, except for 1! and 0!. This is simply not interesting.

Note that every submission you submit (you can submit more than one if you want, I don't care) will be publicly available after, so everyone will be able to take a look at what people's did.

I encourage people with less experience to participate. That's just going to be more fun. And it's not that hard to make a working implementation.

Also, please put all your source code in a folder and include a README text file which would contains your cboard alias and directives on how to compile your solution. If you use libraries not easily found or not easily installable on a typical Linux distribution, gives indications where to get them. Also, specify in which base is the output. And zip the folder.

The contest ends in 3 weeks, which means June 15th, 22:00 GMT.

Have fun!
(And sorry for all the English mistakes i may have made)

Cool!

2 questions,
1. Did you want us to support any +ve value of N? Such as, I don't know -- 955858! ?
2. How do we actually submit our solutions? A PM? Email?

Quote:

1. Did you want us to support any +ve value of N? Such as, I don't know -- 955858! ?

Yes. The input number will be between 0 and 2^32 - 1. But since I don't want to leave my computer running for days for every program to terminate, consider it will be somewhere between 100 000 and maybe 1 000 000. But consider 2^32 - 1 being the "hard limit".

Quote:

How do we actually submit our solutions? A PM? Email?

I would say by PM, but i did not even check if it was actually possible to send attachment via PM. I'll give an email address if it's not possible. EDIT: Ok, it doesn't look possible to send attachments via PM, so you'll have to send them via email. If you go see my profile, there's an email address you can use.

I'm glad at least one people is interested for now. :) I'll have to begin on working on my solution... one day... it won't be mind blistering but it will touch to one things or two i don't usually. Won't be the fastest, but shouldn't be the slowest neither.

Hmm... there's not many options I can think of to optimize a N factorial. There is only one mathematical approach I know of. But I'm not sure how many people can define it. I surely can't. Lookup tables is the usual way. Heck, even boost uses them for i <= max_factorial<T>::value.

Also, an 2^32-1 input will overflow on the result unless provisions are also made for big numbers, even for 64bit computers, won't it?

I think there's not much one can do, other than cutting on the end instruction set the best they can.

I think that's part of the problem :)

Anyone can calculate 1 to 12! Even the solution is given in the original post.

Well there are actually optimizations for large N - possibilities are given in the wikipedia article (or a link or two deep, I don't remember).

Quote:

You can't use mathematics libraries, except if you are the author or if it's the standard C/C++ math library. In fact, if someone want to use an "advanced" mathematic library, he can but his program won't be taken into account when it will be time to declare the winner of the contest.

But we won't see them if we're not at least allowed to use a bignum library.

What I mean is that it's against the rules to use something like, example, GMP, except if you are one of the author.

Of course, if you want to be able to compute the factorial of a number larger than 12, you'll need some sort of data structure capable of manipulating "big integers". That's part of the challenge.

Is it clearer ?

> Is it clearer ?
Yes thanks :)

Quote:

Originally Posted by Mario F.

Also, an 2^32-1 input will overflow on the result unless provisions are also made for big numbers, even for 64bit computers, won't it?

Then you have to be more clever than that, won't you?

Here's my submission. It is password protected, btw, so no need to cheat. :)

Alright, thanks for participating Sang-drax. Don't forget to publish the password the day the contest ends.

I would like to add that when I say it has to be in C/C++, inline assembly is also accepted (of course), as long as it's incorporated through a C/C++ program and compile on gcc and run on the target architecture. And for those who would like this extra information:

sizeof(int) = 4
sizeof(long) = 8

ok, so an array of ~21 million bytes shoudl suffice to hold the largest value you specified (1 million), although 2^32-1 would require around 205 gigabytes of ram just for teh answer, so Im going to go ahead and just assume you wont give an input larger than 1 million. At that rate, assuming you can get the multiply for free adn just have to transfer the answer each iteration, adn only once, you are lookign at around 80+ minutes run time for 1000000!

I wasn't joking when I said that there were optimizations for large N, obviously. These are algorithm changes too, not just unrolling loops or something like that.

My submission contains no optimizations whatsoever.

> My submission contains no optimizations whatsoever.
In that case,

Here is my submission:

Code:

g++ -O3 -o mysubmission `find / -name fac.cpp`

Not sure what else I could optimize, because I actaully haven't read it :(

Just make sure you extract Sang-drax's first ;)

On a serious note, It's coming!

Alright, I'm done. We are waiting for you, zacs7. ;)

Someone else is working on something ? There's still 12 days left if you are interested.

Hey, I am interested too, I am just now seeing this, but I already have a bignum library I wrote so it won't take much to throw together an entry.

Alright, at least a bit of challenge for Sang-Drax solution.

Contest ends this sunday.

Ok, just as a reminder:

Contest ends tomorrow and I should be able to post the results and the solutions of everyone during evening (-05:00 GMT)
Right now, only Sang-drax and tabstop submitted something...
Personally, I also got 2 solutions...

So, Darryl, if you want to submit something, it's about time. As for zacs7, he's just a liar, don't listen to what he says, he's not working on anything. :p

If I can do my GMT conversions right, the deadline has come and gone, so I guess I can post my codes (plural!):
http://members.cox.net/tabstop/puzzles/factorial1.zip
http://members.cox.net/tabstop/puzzles/factorial2.zip

I really hope everything's good there -- apparently I had lost the skill of FTP for awhile but I think it's better now. We'll find out.

Thanks to foxman, not only for running the thing, but also for compiling/testing my entries early enough that I could find and fix all the places (I hope) where I relied on undefined behavior and got away with it on my machine.

Here's the result.

First, there was only two different people who submitted something: tabstop (who had 2 solutions) and Sang-drax. Thanks for their participation. ;)
I personnaly had 2 solutions + 1 reference implementation. The reference implementation is using the GMP library, and has nothing extravagant; it was only a way to compare the results on something I would be sure was the good answer. Also, since GMP is really nice, it can output the result in different base, which came in handy since Sang-drax was using the decimal base (tabstop and I were using hexadecimal).

Note that every solution got compiled with the -O3 flags with GCC 4.2.3 on a 64-bits Linux-based OS.

Every solution calculated 16 847! and 543 210! (random numbers I chose -- don't know if they have special properties but I doubt) twice. I timed the result with the "time" builtin command in bash. But I got some weird result and I'm really wondering why, more on this later.

16 847!
First run

Code:

foxman-1 real 0m0.043s user 0m0.052s sys 0m0.000s foxman-2 real 0m0.065s user 0m0.064s sys 0m0.000s sang-drax real 26m10.325s user 26m10.410s sys 0m0.012s tabstop-1 real 0m20.243s user 0m17.169s sys 0m3.052s tabstop-2 (Gave incorrect result -- but had the right numbers of digits) real 0m44.545s user 0m40.483s sys 0m4.064s

Second run

Code:

foxman-1 real 0m0.046s user 0m0.052s sys 0m0.000s foxman-2 real 0m0.063s user 0m0.064s sys 0m0.000s sang-drax real 39m15.274s user 39m15.415s sys 0m0.004s tabstop-1 real 0m25.470s user 0m21.129s sys 0m4.344s tabstop-2 (Gave incorrect result -- but had the right numbers of digits) real 0m33.005s user 0m29.698s sys 0m3.308s

This is where it gets really strange: there's a 13 minutes difference (which is 50% !!) in Sang-drax runs. I really don't know why, this is really a ........ing big difference. The test where on a comp I have since only 2 months; could it be a hardware problem ? And I'm quite sure it's not related to stuff running in background since I wasn't even running a desktop environment and there's was nothing running in background except the usual operating system stuff (no server or anything). Nothing to explain a that large difference. This is a bit ........ing me off. Still, it tooks 25 minutes to Sang-drax, 20 and 33 seconds to tabstop, and 0.043 and 0.063 seconds for myself. One of tabstop solution gave an incorrect answer, so let's say it's "disqualified".

That's it, since it was already quite long to calculate 16 847! for Sang-drax solution, it didn't had a try on 543 210!. :p

543 210!
First run

Code:

foxman-1 real 0m49.896s user 1m4.136s sys 0m0.008s foxman-2 real 2m38.058s user 2m38.038s sys 0m0.020s tabstop-1 real 12m2.838s user 10m27.055s sys 1m35.818s tabstop-2 (Gave incorrect result -- but had the right numbers of digits) real 21m17.304s user 17m37.050s sys 3m40.334s

Second run

Code:

foxman-1 real 0m49.972s user 1m4.104s sys 0m0.004s foxman-2 real 1m45.375s user 1m45.375s sys 0m0.004s tabstop-1 real 12m4.091s user 10m27.035s sys 1m37.102s

Again, some weird difference between first run and second run on foxman-2 solution.
So, congrats to tabstop for beating Sang-drax.
Still, great second place for Sang-drax. :p

Everyone's solution is included in this zipped file: factorial-contest.zip

So the end result: trying to make the multiplication faster (my second entry) not only took longer, but gave incorrect results. (I admit that past 40! or so, I wasn't checking digits, just the number of digits.) There's a moral in there somewhere.

oh man I thought I had till end of day today... I was just about to submit mine...oh well... I didn't get to finish it the way I wanted anyway. Mine was complete but I wanted to switch to Karatsuba multiplication and just couldn't find the time

Some personal feedback:

Sang-drax, your solution is indeed quite correct, but you should have think about optimisation if you wanted your solution to be fast (but I think it wasn't your goal, I know)... :p. Using a better base (that's it, some power of 2) and working a bit on the "memory management" could have make some noticeable performance gain for only a little effort.

tabstop, this is intesting. The high-level idea is nice, but the implementation might not be as good. One of the biggest implementation problem I see is that you aren't keeping track of the "most significant digit", so you go through the SIZE "digits" every time you need to do something with the data instead of just going through the "interesting" digits (or you are looping to determine which digits is the most significant). Plus there's a lot of creation and destruction of "MassiveNum" and this get expensive (we can clearly see it on your program system time). That last reason might be why your Karatsuba implementation is slower than your other (look, 3m40 in system time for that solution! heh). Also, you are using a "power of 2" base but I saw you were still using the % and / operator instead of & and >> respectively. I don't know if GCC was able to optimize this.
Still, we see the benefit from the better high level idea on big factorial : it took 470x more time for your solution to calculate 16 847! than my fastest solution but it only took only about 14x more time for 543 210!.

Oh and Darryl, sorry for you, but the contest's end time was cleary written in the first post of this thread... ;)

I did attempt the problem,despite never working with long numbers before (let alone in C). Well it didn't go that well. I was thinking of using three different multiplication algorithms peasant multiplication, Karatsuba (see post in C programming) and Strassen, depending on how any digits were in the number. But I didn't know of an algorithm to calculate the factorial other than the inaccurate one in the 1st post. Though I did learn about bit-shifting, multiplication algorithms and a minimal amount about Karatsuba and Strassen. I will post the code to prove it, it might come in useful. Thanks for posting the contest though even if it was too challenging for me.

Code:

#include <stdlib.h> #include <windows.h> #include <stdio.h> #include <math.h> long long multiply(long long multiplier, long long multiplicand) { long long product = 0; while (multiplicand) { if (multiplicand & 1) product = product + multiplier; multiplier = (long long)(multiplier <<= 1); multiplicand = (long long)(multiplicand >>= 1); } return product; } unsigned int factorial(unsigned int N) { if (N == 0 || N == 1) return 1; return multiply(N, factorial(N - 1)); } long divide(long dividend, long divisor) { long quotient = 0; while (divisor) { quotient = quotient << 1; if (divisor <= dividend) { dividend = divisor - dividend; quotient++; } divisor = divisor >> 1; } return quotient; } long divide10(long dividend) { //long quotient = 0; //quotient = multiply(dividend, 3) + (dividend >> 3); return (dividend >> 3) + multiply(dividend, 2); } long karatsubaAlg(long x, long y) { // doesn't work correctly int x1 = x >> 16; int x2 = (x & 0xFFFF);// >> 16; int y1 = y >> 16; int y2 = (y & 0xFFFF);// >> 16; long a, b, c, k; a = multiply(x1, y1); b = multiply(x2, y2); c = multiply(x1+x2, y1+y2); k = c - a - b; return ((a << 32) + b + (k << 16)); } int peasantAlg(int x, int y) { int total = 0; if (x % 2 != 0) total = total + y; while (x > 1) { x = (int)(x >> 1); // / y = (int)(y << 1); // * if (x % 2 != 0) total = total + y; } return total; } unsigned long long shift(unsigned long long a) { return a / 10000; } //Main function cut as it simply tests the above

I know it's to late for that question, but for future contests:
Is it allowed to use the inline-assembler? :P

I would love to try to enter a contest. Is it possible to maybe next time make it a bit easier so more people can participate?

Quote:

Originally Posted by mkruk

I know it's to late for that question, but for future contests:
Is it allowed to use the inline-assembler? :P

Well, every contest has it's own rules. So this question will remain unanswered.

Quote:

I would love to try to enter a contest. Is it possible to maybe next time make it a bit easier so more people can participate?

Well, I still think it wasn't really hard to produce a conforming implementation for this contest. Of course, it was a harder to write an efficient one. You did need to think a bit before coming with a solution, but if it would be too easy, it wouldn't be a fun contest, right ?