Sunday, April 10, 2011

File under "Elegant": Factorial in Plan 9 rc (under Linux)

I've posted before that I find Plan 9's rc shell elegant.  I've been using a "slightly" modified (I've made read and echo builtins) version for a few months now and have been doing extensive scripting. I hope never to go back to bash.

Here is a small script to compute factorials. Since "bc" deals with arbitrary precision, we can go much higher than the 32 or 64 bits.

Chew on this:

#!/usr/local/plan9/bin/rc
fn fac {
num=0 factorial=1 frombc=$2 tobc=$3 {
for (num in `{seq $1}) {
echo $factorial '*' $num >$tobc
factorial=`{read <$frombc}
}
echo $factorial
}
}
fn fixlinebreaks {
awk -F '\\' '{printf("%s",$1)}
$0 !~ /\\$/ {printf("\n"); fflush("");}'
}
fac $1 <>{bc | fixlinebreaks}

There are several interesting things here:
  1. Concurrent processing (co-processes actually).
  2. Messaging through unix pipes.
  3. Lazy computation (generator).
The last line launches bc as a coprocessing service (filtering output through fixlinebreaks which is needed due to a "feature" of bc where it breaks up long numbers into multiple lines -- blech).  We treat bc as a service and send it requests (steps in the factorial computation) and it responds with our intermediate results.
This factorial algorithm is iterative rather than recursive, but rather than using an incrementing counter loop, we generate all numbers using the 'seq' program and loop through that lazily generated list!

How slow do you think this script will run?  Well on my Toshiba Portege r705 notebook with a Core i3, factorial of 1024 takes 2.4 seconds. Is that slow?

Earlier I said that I had enhanced rc with "echo" and "read" as builtins (normally they are external). Using the non-builtin "echo" and "read" increases the run time to 5.1 seconds.

Of course this isn't production code, but here is the take-away: "bc" gives you a bignum calculator for free.  Use it.

No comments: