Factorial

This is a discussion on Factorial within the Contests Board forums, part of the Community Boards category; Alright, I'm done. We are waiting for you, zacs7. Someone else is working on something ? There's still 12 days ...

  1. #16
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.

  2. #17
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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.

  3. #18
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    Alright, at least a bit of challenge for Sang-Drax solution.

    Contest ends this sunday.
    I hate real numbers.

  4. #19
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.

  5. #20
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  6. #21
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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!.

    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.

    Everyone's solution is included in this zipped file: factorial-contest.zip
    Last edited by foxman; 06-16-2008 at 06:55 PM.
    I hate real numbers.

  7. #22
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  8. #23
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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

  9. #24
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.

  10. #25
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    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);

  11. #26
    FOSS Enthusiast
    Join Date
    Jun 2008
    Location
    Germany
    Posts
    64
    I know it's to late for that question, but for future contests:
    Is it allowed to use the inline-assembler? :P

  12. #27
    Registered User
    Join Date
    Oct 2006
    Location
    UK/Norway
    Posts
    485
    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?

  13. #28
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    Quote Originally Posted by mkruk View Post
    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.

    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 ?
    I hate real numbers.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation fault using recursion to find factorial
    By kapok in forum C++ Programming
    Replies: 4
    Last Post: 02-23-2009, 10:10 AM
  2. Calculating Factorial
    By ice661666 in forum C++ Programming
    Replies: 3
    Last Post: 06-12-2008, 04:58 AM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  4. Basic Factorial from 1-10
    By AaA in forum C Programming
    Replies: 20
    Last Post: 05-28-2005, 07:39 AM
  5. factorial output
    By maloy in forum C Programming
    Replies: 1
    Last Post: 03-13-2002, 02:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21