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.
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.
I hate real numbers.
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.
I hate real numbers.
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.
I hate real numbers.
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
Second runCode: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
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".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
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!.
543 210!
First run
Second runCode: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
Again, some weird difference between first run and second run on foxman-2 solution.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
So, congrats to tabstop for beating Sang-drax.
Still, great second place for Sang-drax.
Everyone's solution is included in this zipped file: factorial-contest.zip
Last edited by foxman; 06-16-2008 at 07:55 PM.
I hate real numbers.
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)... . 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 hate real numbers.
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
long time no C; //seige
You miss 100% of the people you don't C;
Code:if (language != LANG_C && language != LANG_CPP) drown(language);
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?
Well, every contest has it's own rules. So this question will remain unanswered.
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 ?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?
I hate real numbers.