Logiciel Libre

While thumbing through a Ruby guide, I saw an example of computing factorials. Just out of curiosity, I decided to see how Ruby stacks up against C, Python, and Perl for this particular problem. Comments/suggestions/criticisms welcome. It would also be cool to see examples in other languages, so send ‘em in!

I “cheated” in Perl and C by using the GNU Multiple Precision Arithmetic Library. Just seemed easier that way. All code examples on this page are hereby released under the GPL.

The Code

Python

#!/usr/bin/python

# Computes factorial for number passed as first command
# line argument.

import sys

total = 0
def fact(n):
    total = n
    while n > 1:
        total *= (n - 1)
        n -= 1
    return total

print fact(int(sys.argv[1]))

Perl

#!/usr/bin/perl

# Computes factorial for number passed as first command
# line argument.

use Math::BigInt lib => 'GMP';
$b = Math::BigInt->new($ARGV[0]);
print $b->bfac(),"\n";

Ruby

#!/usr/bin/ruby

# Computes factorial for number passed as first command
# line argument.

def fact(n)
  if n == 0
    1
  else
    n * fact(n-1)
  end
end

print fact(ARGV[0].to_i), "\n"

C

/*
 * Computes factorial for number passed as first command
 * line argument.
 *
 * Uses the GNU Multiple Precision Arithmetic Library (see
 * http://www.swox.com/gmp/ ).
 *
 * The best "quick start" guide I could find was in the
 * INSTALL file in the gmp tarball.
 *
 * Compile with the -lgmp command line switch.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int
main (int argc, char **argv)
{
  mpz_t fact;

  if (argc != 2)
  {
    printf ("Usage: %s <number>\n", argv[0]);
    printf ("The factorial of <number> will be returned.\n");
    return EXIT_FAILURE;
  }

  mpz_init (fact);
  mpz_fac_ui (fact, atoi(argv[1]));
  gmp_printf ("%Zd\n", fact);

  return EXIT_SUCCESS;
}

The Results

Here are my one-off timings of each on my 1.8Ghz Pentium 4 desktop. To get the results, I just executed the code a bunch of times and took the best one.

$ time python/factorial/factorial.py 40
815915283247897734345611269596115894272000000000

real    0m0.039s
user    0m0.024s
sys     0m0.010s

$ time perl/factorial/factorial.pl 40
815915283247897734345611269596115894272000000000

real    0m0.164s
user    0m0.140s
sys     0m0.014s

$ time ruby/factorial/factorial.rb 40
815915283247897734345611269596115894272000000000

real    0m0.015s
user    0m0.005s
sys     0m0.007s

$ time c/factorial/factorial 40
815915283247897734345611269596115894272000000000

real    0m0.006s
user    0m0.001s
sys     0m0.002s

Of the scripting languages, Ruby led the pack. I used the recursive factorial example right out of that Ruby guide I mentioned earlier, so it has a limit of about 2,800! or so.

So, how ’bout 100,000!? Well, first I have to rewrite the Ruby solution to be non-recursive. Sorry if I’m not using “canonical” Ruby, this is the first time I’ve written any.

#!/usr/bin/ruby

# Computes factorial for number passed as first command
# line argument. Non-recursive (iterative) version.

total = 0
def fact(n)
  total = n
  while n > 1
    total *= (n - 1)
    n -= 1
  end
  return total
end

print fact(ARGV[0].to_i), "\n"

And here are some more quick-and-dirty benchmarks:

$ time python/factorial/factorial.py 100000 > /tmp/python_fact.txt

real    6m41.018s
user    5m14.327s
sys     0m18.453s

$ time perl/factorial/factorial.pl 100000 > /tmp/perl_fact.txt
<CTRL-C>
real    63m41.182s
user    48m54.874s
sys     0m12.881s

$ time ruby/factorial/nonrecursive.rb 100000 > /tmp/ruby_fact.txt

real    9m22.536s
user    6m51.273s
sys     0m19.430s

$ time c/factorial/factorial 100000 > /tmp/c_fact.txt

real    0m3.834s
user    0m3.769s
sys     0m0.023s

I got tired of waiting for the Perl script to complete. No idea how/why Python nosed out Ruby in this example. /tmp/python_fact.txt, /tmp/ruby_fact.txt, and /tmp/c_fact.txt turned out identical (as expected), but since I interrupted the Perl process, I never got a result.

Synopsis

Basically, C is fast (duh), but I was really surprised at Ruby’s speed. Python and Ruby do something cool: whenever a number gets too large, it’s automatically converted into a bignum-kind of object. I’m not sure I’m too into Ruby’s syntax.

Other Tidbits

Those interested in how to find large factorials might enjoy this Google answer on how to compute 1,000,000!

Interesting: apparently, Ruby can be translated into C.

For others interested in multiple-language programming, check out the ACM “Hello World” project, which shows “Hello, World!” programs in many different languages.

While I’m at it…

$ time c/factorial/factorial 1000000 > /dev/null 

real    2m32.795s
user    1m49.357s
sys     0m1.374s

Fast enough for me!

Update

Patrick rightly pointed out that Perl is not slow, and I completely agree. However, there is a loss of precision if Perl is left to handle numbers on its own. For example, the following implies something less than unlimited precision:

$ cat factorial.pl
#!/usr/bin/perl -w
use strict;

sub fact($) {
  my $total = my $n = shift;
  while ($n > 1) {
    $total *= ($n-- - 1);
  }
  return $total;
}

printf("%.0f\n", fact($ARGV[0]));
$ perl t.pl 40
815915283247898008314102179727920573516005507072

Speed gains in Perl might also be achieved by not use’ing strict and by disabling warnings.

I should be more specific on the requirements of the challenge, so here goes: compute factorials of numbers while supporting as much precision as possible.