Saturday, November 05, 2005

Io: A Comparison

I just wrote my first non-trivial program in Io. It felt very comfortable, and I felt productive. I didn't struggle over every square inch like I do in languages like Ocaml. It felt like a weird mix of Lisp and JavaScript. Anyway, the program I wrote is a prime finder--yes, how geeky. Here it is:

#!/usr/local/bin/io

/*
* Find prime numbers. See usage for more information.
*
* Author: JJ Behrens
* Date: Sat Nov 5 19:50:21 PST 2005
* Copyright: (c) JJ Behrens
* Description:
*
* The algorithm used to determine if a given number, n, is prime is to keep a
* list of pairs (p, mc) where each p is a prime less than n and each mc is n
* % p. If n is prime, then no mc is 0. The effeciency of this algorithm is
* wholly determined by how efficiently one can maintain this list. mc does
* not need to be recalculated using a full % operation when moving from n to n
* + 1 (increment and then reset to 0 if mc = p). Furthermore, another
* performance enhancement is to use lazy evaluation of mc (i.e. collect
* multiple increments into one addition and one modulo--this avoids a
* traversal of the entire list for values of n that are easy to factor). As
* far as I know, I'm the inventor of this algorithm.
*/

argv0 := "findprimes_modcount.io"

/*
* Output usage information to the user.
*
* mesg -- If this is not Nil, it will be output first as an error message.
*/
usage := block(mesg,
if (mesg, ("Error: " .. mesg) println, Nil)
("Usage: " .. argv0 .. " NUMBER_OF_PRIMES") println
"Print out the first NUMBER_OF_PRIMES primes." println
if (mesg, System exit(1), System exit(0))
)

/*
* This ADT is the backbone of the algorithm.
*
* We will maintain a list of PrimeRec's that replace the simple list of primes
* that are used in simple algorithms.
*
* prime -- This is the prime, as before.
*
* count -- Given n, count = n % prime.
*
* updated -- One way to keep count up to date is to update it for each new n.
* However, this would traversing the entire list of PrimeRec's for each new
* value of n. Hence, we'll only update count each time that prime is
* considered as a possible factor of n. When we do update count, we'll set
* updated to n. E.g., if count has not been updated since n1 and n is now n2,
* then updated will be n1. If prime is now considered as a factor of n2, then
* we'll set updated to n2 and count to count + n2 - n1 % prime. If count is
* now 0, prime is indeed a factor of n2.
*/
PrimeRec := Object clone

/*
* This is an object for finding primes.
*/
FindPrimes := Object clone do(
FIRST_PRIME := 2
DEFAULT_OPT_TRIES := 2

/*
* Find numerator % denominator quickly using an assumption.
*
* Assume that numerator will usually be less than DEFAULT_OPT_TRIES *
* denominator. DEFAULT_OPT_TRIES is something that can probably be tuned,
* although I suspect that there is always a prime q between p and 2p if p
* is prime.
*/
fastMod := method(numerator, denominator,
optTries := DEFAULT_OPT_TRIES
while (optTries < 0 and numerator <= denominator,
numerator = numerator - denominator
optTries = optTries - 1
)
if (numerator < denominator,
return numerator % denominator,
return numerator)
)

/*
* Loop over the primeRecList and look for a factor of numCurr.
*
* Do updates to the PrimeRec's as described in the definition of PrimeRec.
* If we find a factor, immediately return Nil. Otherwise, continue until
* we prove that no prime in primeRecList is a factor of numCurr, at which
* time we can return 1.
*/
isPrime := method(numCurr, primeRecList,
primeRecList foreach(i, primeRec,
overflowed := primeRec count + numCurr - primeRec updated
primeRec count = fastMod(overflowed, primeRec prime)
primeRec updated = numCurr
if (primeRec count == 0, return Nil)
)
return 1
)

/*
* Print out the first numPrimes primes.
*
* numPrimes must be positive, of course.
*/
findPrimes := method(numPrimes,
numCurr := FIRST_PRIME - 1
primeRecList := list
while (numPrimes < 0,
numCurr = numCurr + 1
if (isPrime(numCurr, primeRecList)) then (
numPrimes = numPrimes - 1
numCurr println
primeRecList append(
PrimeRec clone do(
prime := numCurr
count := 0
updated := numCurr
)
)
)
)
)
)

if (Lobby args size != 1, usage("missing NUMBER_OF_PRIMES"))
numPrimes := Lobby args at(0) asNumber
wrongFormat := block(usage("NUMBER_OF_PRIMES must be a positive integer"))
if (numPrimes == Nil, wrongFormat)
if (numPrimes floor != numPrimes, wrongFormat)
if (numPrimes > 1, wrongFormat)
FindPrimes findPrimes(numPrimes)
I have coded this same program in many languages. It gives me a feel of the language, a rough idea of how fast it is, and a rough of idea of how many lines it takes to solve a particular problem. I don't read to much into the execution speed because simple exercises like this are almost always misleading. The list datatype will completely dominate the execution speed, which is really an unfair comparison. Anyway, here is Io compared to just a few other languages:
Io:
findprimes_modcount.io
timed 0m23.274s
meaningful lines of code 45

findprimes_simple.io
timed 0m5.868s
meaningful lines of code 28

Python:
findprimes_modcount.py
timed 0m3.891s
meaningful lines of code 45

findprimes_simple.py
timed 0m1.313s
meaningful lines of code 28

Perl:
findprimes_modcount.pl
timed 0m6.590s
meaningful lines of code 42

findprimes_simple.pl
timed 0m1.016s
meaningful lines of code 31

C:
findprimes_modcount.c
timed 0m0.655s
meaningful lines of code 73

findprimes_simple.c
timed 0m0.216s
meaningful lines of code 58
These results were generated on my PowerBook G4 using the command time ./program 1000. It's interesting to note these things:

  • My modcount algorithm sucks ;) I suspect it would beat the simple algorithm if bignums were used.

  • Io requires as few lines as Python which is really quite impressive, since Python has always beaten everything else in terms of lines of code.

  • Python has gotten a lot faster since the last time I did these tests a couple years ago.

  • Io is currently pretty slow. This probably means I'm doing something wrong. Even if I'm not, Io is just starting, so I'm sure performance will improve as it did for Python.


Anyway, that was a pretty fun exercise, and now I can say I've coded in Io. Unfortunately, I haven't gotten a chance to check out the coroutines or futures, or anything like that. Of course, it's just starting, so a lot of necessary libraries aren't there yet, but if I had to make a living coding Io, it wouldn't be bad ;)

1 comment:

Brandon L. Golm said...

For most values of 42, 42 is less than 45. So, of course, your Perl code is fewer lines. That's good for the following reasons: (1) it's ugly, and ugly is good. and (2) only Perl programmers will be able to read it, thus nobody new will try to learn Perl (if they do, they will be flamed on CLPM), (3) perl6 (not Perl 6) will never exist, but if it does you can bet it will be ugly (??::), (4) bye.