Comparing Lisp to C# (and F#)

OK, so the title is really misleading, as you can’t really compare such different languages, but it’s interesting to try to anyway.

Most people’s first reaction when seeing Lisp is “Huh? How can you read all those brackets?” Lisp is famous for its brackets, and has been described as a write-only language. The truth is, once you get used to them, they don’t look so daunting.

Anyway, being a rank beginner, I had to start with everyone’s favourite recursive function, the factorial. This is a good one, as it’s so simple, but quickly generates numbers so big that it’s pretty useless unless you do something more than the basic coding.

A simple implementation in C# could look like this…

public static int Fac(int n) =>
  n == 1
    ? 1
    : n * Fac(n - 1);

This works fine, as long as you don’t want to compute numbers bigger than 27! (the exclamation mark there does not indicate surprise, it’s the standard way writing “factorial 27”). Once you try this with 28, the result goes negative, due to the limitations of the 32-bit integer than int can store. Once you try 34!, the result is zero, and remains so for any bigger values.

No problem, we can use BigInteger, which is designed for this. A quick adjustment gives us…

public static BigInteger Fac(BigInteger n) =>
  n == 1
    ? 1
    : n * Fac(n - 1);

This handles big numbers with ease, at least as long as you don’t want to go above about 5000, at which point you get a StackOverflowException. You can get around this by rewriting the method, but it gets complicated, and isn’t what I really want to be thinking about when coding.

So, how does Racket handle this? Surprisingly well actually. The function definition is simple enough…

(define (fac n)
  (if (= n 1)
      1
      (* n (fac (- n 1)))))

I know, all those brackets! Believe me, they really aren’t that bad when you get into it. Also, DrRacket does a great job of highlighting their scope, so it’s pretty easy to see what encloses what. It also looks better when highlighted properly, but the syntax highlighter I use on this blog doesn’t seem to support Lisp ☹.

I was very pleasantly surprised to see that Racket handled big numbers without any problems. Obviously, execution time increased with bigger numbers, but it could handle hundreds of thousands without any errors. For those of you who are interested, 100,000! has 456575 digits ?.

Again, I’m sure an experienced Lisp programmer could write much more efficient code, but given that this computed reasonably large factorials fairly quickly, I’m not sure you’d need to.

As for execution speed, Racket won the prize again. Timing the calls was fairly easy. In C# I used a StopWatch

Stopwatch sw = Stopwatch.StartNew();
var f = Fac(5000);
Console.WriteLine(sw.ElapsedMilliseconds);

…and in Racket I used the time function…

(time (fac 5000))

The results? C# took about 30ms, and Racket took about 15ms.

No, I’m not intending on switching my main programming language based on this very simple and naïve experiment, but it was an interesting exercise.

Update: Just out of curiosity, I tested this against an F# factorial function. Again, this is a simple implementation, without any thought for optimisation…

let factorial n = Seq.fold ( * ) 1I [1I .. n]
let n = 5000I
let stopWatch = System.Diagnostics.Stopwatch.StartNew()
let fn = (factorial n)
stopWatch.Stop()
printfn "%f" stopWatch.Elapsed.TotalMilliseconds

I cheated and used a StopWatch as I was running this in LinqPad (couldn’t be bothered firing up VS just for this test), but the result should be the same.

F# computed the factorial in about 10ms, beating Racket hands down. It also computed 100,000! in around 4.5 seconds, as opposed to Racket taking about 8.6 seconds.

So yes, this does raise the question why I am learning Lisp when I already have experience in an apparently faster (from one very simple test) language that integrates very well with the .NET ecosystem I use every day. I’ve been asking myself that a lot over the past couple of weeks, and can only put it down to a weird compulsion to learn something completely different!

2 Comments

  1. Kryštof Žáček said:

    // .NET 6. C#10: fac(10_000) took 38 ms 🙂
    var fac = (int n) => Enumerable.Range(1, n).Aggregate(BigInteger.One, (accu, element) => accu * (BigInteger)element);
    var result = fac(10_000);

    December 22, 2021
    Reply
    • Avrohom Yisroel Silver said:

      Thanks for that, very neat solution. Handles bigger numbers with ease.

      On my PC, didn’t matter which version of .NET I used (tried 3.1, 5 and 6), all took around 22ms.

      December 22, 2021
      Reply

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.