(re)Learning CoffeeScript. Decided to build a prime number generator.

prime-generator.txt

$ time ./primes-c 10000000 > primes10M.csv

real    2m23.426s
user    2m20.229s
sys     0m0.329s

$ time coffee primes.coffee 10000000 > primes10M.csv

real    5m35.077s
user    5m6.806s
sys     0m28.262s

$ time ./primes-go -t 6 10000000 > primes10M.csv 

real  1m7.012s
user  5m13.209s
sys	0m48.497s

$ time ./primes 100000000 > primes100M.csv ; tail -n 1 primes100M.csv

real    75m22.288s
user    71m47.830s
sys     0m6.150s

2038074743

primes.c

//
//  main.c
//  primes
//
//  Created by Rick Osborne on 6/15/13.
//  Copyright (c) 2013 rick osborne dot org. All rights reserved.
//

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#define NOT_PRIME 0
#define PRIME 1

struct PrimeNode {
    long value;
    struct PrimeNode* next;
};

typedef struct PrimeNode prime;

static long _lastChecked = 1;
static long _iterations = 0;
static clock_t _started;
static int _stats = 0;
static long _primeCount = 0;
static size_t _primeSize = sizeof(prime);

prime* _firstPrime = NULL;
prime* _lastPrime = NULL;

void clearPrimes() {
    prime* nextPrime = _firstPrime;
    while (nextPrime) {
        _firstPrime = nextPrime;
        nextPrime = nextPrime->next;
        // printf("free: %ld\n", _firstPrime->value);
        free(_firstPrime);
    }
    _firstPrime = NULL;
    _lastPrime = NULL;
}

int check(long n) {
    long maxDivisor = sqrt(n);
    long primeIndex = 0;
    long divisor;
    prime* nextPrime = _firstPrime;
    _lastChecked = n;
    while (++_iterations && nextPrime && (divisor = nextPrime->value) && (divisor <= maxDivisor) && ++primeIndex) {
        if (!(n % divisor)) return NOT_PRIME;
        nextPrime = nextPrime->next;
    }
    nextPrime = (prime*)malloc(_primeSize);
    if (!nextPrime) exit(-1);
    nextPrime->value = n;
    nextPrime->next = NULL;
    if (!_firstPrime) _firstPrime = nextPrime;
    if (_lastPrime) _lastPrime->next = nextPrime;
    _lastPrime = nextPrime;
    _primeCount++;
    if (_stats) printf("%ld,%ld,%ld,%.16Lf,%lu\n", _primeCount, _lastPrime->value, _iterations, log10l(_iterations) / log10l(_lastChecked), (clock() - _started) * 1000 / CLOCKS_PER_SEC);
    else printf("%ld\n", _lastPrime->value);
    return PRIME;
}

int isPrime(long n) {
    int result = NOT_PRIME;
    if (_lastChecked >= n) {
        prime* nextPrime = _firstPrime;
        while (nextPrime) {
            if (nextPrime->value == n) return PRIME;
            nextPrime = nextPrime->next;
        }
        return NOT_PRIME;
    }
    while (_lastChecked < n) result = check(_lastChecked + 1);
    return result;
}

void primeCount(long count) {
    _started = clock();
    while (_primeCount < count) isPrime(_lastChecked + 1);
}

int main(int argc, const char * argv[])
{
    _started = clock();
    int i;
    long n = 10, l;
    for (i = 1; i < argc; i++) {
        if (!strcmp("-v", argv[i])) {
            printf("Count,Prime,Iterations,Exponent,MS\n");
            _stats = 1;
        }
        else {
            l = atol(argv[i]);
            if (l) n = l;
        }
    }
    primeCount(n);
    clearPrimes();
    return 0;
}

primes.coffee

# Prime Number Generator
# @author Rick Osborne
# @since 2013-06-15

class PrimeNumberGenerator
  # Private
  _primes = []
  _lastChecked = 1
  _iterations = 0
  _started = Date.now()
  _stats = false

  check = (n) ->
    _lastChecked = n
    # Only check divisors up to sqrt(n)
    maxDivisor = Math.floor(Math.sqrt(n))
    primeCount = _primes.length
    primeIndex = 0
    while ++_iterations && (primeIndex < primeCount) && (divisor = _primes[primeIndex]) && (divisor <= maxDivisor) && ++primeIndex
      # if n is divisible then it's not prime
      return false unless n % divisor
    # add this to our list of primes
    _primes.push n
    # log it out
    if _stats
      console.log [
        _primes.length
        _lastChecked
        _iterations
        Math.log(_iterations) / Math.log(_lastChecked)
        Date.now() - _started
      ].join(",")
    else
      console.log n
    # yep, it's prime
    true

  # Public
  showStats: (verbose) ->
    _stats = !!verbose
    console.log [
      "Count"
      "Prime"
      "Iterations"
      "Exponent"
      "MS"
    ].join(",") if _stats
    @

  isPrime: (n) ->
    result = false
    if _lastChecked >= n
      # We've already tried this number
      result = _primes.indexOf(n) > -1
    else
      # Catch up to this number
      while _lastChecked < n
        result = check _lastChecked + 1
    result

  primeCount: (count) ->
    # reset the clock
    _started = Date.now()
    # Keep going until we've got as many as we need
    @isPrime _lastChecked + 1 while _primes.length < count
    @

# main
verbose = false
count = 10
for arg in process.argv
  verbose = true if arg.match /^(-v|--verbose|--stats)$/
  count = arg if arg.match /^\d+/
png = new PrimeNumberGenerator
png.showStats verbose
png.primeCount count

primes.go

// Rick Osborne
// 2013-06-16

package main 

import (
    "flag"
    "fmt"
    "math"
    "strconv"
    "time"
    "runtime"
//    _ "runtime/race" 
)

const (
    PRIME bool = true
    NOT_PRIME bool = false
    LARGE_CHANNEL uint = 100
)

type (
    Stats struct {
        seq uint64
        prime uint64
        iter uint64
        ns int64
        isPrime bool
    }
    Worker struct {
    	id uint
        nextNumber chan uint64
        results chan *Stats
    }
)

var (
    statsFlag *bool = flag.Bool("v", false, "Print extended stats.")
    debugFlag *bool = flag.Bool("d", false, "Print debugging information.")
    threadCount *uint = flag.Uint("t", uint(runtime.NumCPU()) - 2, "Number of threads")
    primes []uint64
    lastChecked uint64 = 1
    iterations uint64 = 0
    primeCount uint64 = 0
    started = time.Now()
)

func check(stats *Stats) (isPrime bool) {
    var (
    	n = stats.prime
        maxDivisor uint64 = uint64(math.Sqrt(float64(n)))
        divisor uint64 = 0
        primeIndex uint64 = 0
        iter uint64 = 0
    )
    isPrime = PRIME
    for primeIndex < primeCount {
        iter++
        divisor = primes[primeIndex]
        if divisor <= maxDivisor {
            if (n % divisor) == 0 {
                isPrime = NOT_PRIME
                primeIndex = primeCount
            } else {
                primeIndex++
            }
        } else {
            primeIndex = primeCount
        }
    }
    stats.iter = iter
    stats.isPrime = isPrime
    if (isPrime == PRIME) && *statsFlag {
		stats.ns = time.Now().Sub(started).Nanoseconds()
    }
    return stats.isPrime
}

func giveWork (count uint64, nextWorker <-chan *Worker, nextToPrint chan<- *Worker) {
	var (
		n uint64 = lastChecked
		worker *Worker = nil
		threadsLeft uint = *threadCount
		step uint64 = 2
	)
	if *debugFlag { fmt.Printf("controller started counting %d .. %d\n", n, count) }
	// For the first few we need to step by 1
	for n < 7 {
		n++
		worker = <-nextWorker
		nextToPrint <- worker
		worker.nextNumber <- n
		if *debugFlag { fmt.Printf("controller gave %d to #%d\n", n, worker.id) }
	}
	if (n % 2) == 0 { n-- } // even -> odd
	if ((n - 1) % 3) == 0 {
		step = 4 // 7 + 4, 13 + 4, ...
	} else { 
		step = 2 // 5 + 2, 11 + 2
	} // 5 + 2
	// after that we can follow the pattern 2, 4, 2, 4, ...
	for primeCount < count {
		worker = <-nextWorker
		nextToPrint <- worker
		n += step
		step = 6 - step // 4, 2, 4, 2 ...
		worker.nextNumber <- n
		if *debugFlag { fmt.Printf("controller gave %d to #%d\n", n, worker.id) }
	}
	for threadsLeft > 0 {
		worker = <-nextWorker
		threadsLeft--
		if *debugFlag { fmt.Printf("controller terminating #%d (%d left)\n", worker.id, threadsLeft) }
		worker.nextNumber <- 0
		close(worker.nextNumber)
	}
	if *debugFlag { fmt.Printf("controller done\n") }
	close(nextToPrint)
}

func countPrimes(nextWorker chan<- *Worker, workerId uint) {
	var (
		thisWorker = Worker{
			workerId,
			make(chan uint64, 2), // we don't need 2, but this keeps the controller from blocking
			make(chan *Stats, LARGE_CHANNEL),
		}
		stats *Stats
	)
	if *debugFlag { fmt.Printf("worker #%d started\n", workerId) }
	for lastChecked < uint64(workerId) {
		time.Sleep(100)
	}
	if *debugFlag { fmt.Printf("worker #%d ready\n", workerId) }
	nextWorker <- &thisWorker
	for n := range thisWorker.nextNumber {
		if *debugFlag { fmt.Printf("worker #%d got %d\n", workerId, n) }
		if n > 0 {
			stats = &Stats{ 0, n, 0, 0, false }
			check(stats)
    		thisWorker.results <- stats
    		nextWorker <- &thisWorker
        }
	}
    close(thisWorker.results)
	if *debugFlag { fmt.Printf("worker #%d finished\n", workerId) } 
}

func printWork (target uint64, printIn <- chan *Worker, out chan <- string) {
	if *debugFlag { fmt.Printf("printer started\n") }
	for worker := range printIn {
		stats := <-worker.results
		iterations += stats.iter
		if (stats.isPrime) {
			if (primeCount < target) {
		        primes[primeCount] = stats.prime
		        primeCount++
				if *statsFlag {
					out <- fmt.Sprintf("%d,%d,%d,%.16f,%d,%d\n", primeCount, stats.prime, iterations, math.Log(float64(iterations)) / math.Log(float64(stats.prime)), stats.ns, worker.id);
				} else {
					out <- fmt.Sprintf("%d\n", stats.prime)
				}
			} else if *debugFlag {
				fmt.Printf("printer got extra prime %d from #%d\n", stats.prime, worker.id)
			}
		} else if *debugFlag {
			fmt.Printf("printer got non-prime %d from #%d\n", stats.prime, worker.id)
		}
		lastChecked = stats.prime
	}
	if *debugFlag { fmt.Printf("printer done\n") }
	close(out)
}

func main() {
    var (
        target uint64 = 10
        err error
        nextWorker = make(chan *Worker, *threadCount + 1)
        stdout = make(chan string, LARGE_CHANNEL)
        nextToPrint = make(chan *Worker, *threadCount * *threadCount)
        i uint = 0
    )
    flag.Parse()
    runtime.GOMAXPROCS(int(*threadCount))
    if flag.NArg() > 0 {
        target, err = strconv.ParseUint(flag.Arg(0), 10, 0)
        if err != nil {
            target = 10
        }
    }
    primes = make([]uint64, target, target)
    if *statsFlag {
        fmt.Printf("Count:%d,Prime,Iterations,Exponent,NS,Thread\n", target)
    }
    go giveWork(target, nextWorker, nextToPrint)
    go printWork(target, nextToPrint, stdout)
    for i = 0; i < *threadCount; i++ {
    	go countPrimes(nextWorker, i)
    }
    for msg := range stdout {
    	fmt.Print(msg)
    }
    if *debugFlag { fmt.Printf("Done\n") }
}