I just had a fairly pleasant surprise w/rt Larceny/IAssassin on
Windows. I've been working on some tools to help my home-schooled
family do just that bit better at basic arithmetic, and building them
in Java for the easy cross-platform UI as well as bringing my buzzword
compliance up-to-date. Well the wee ones were complaining that the
problems suggested were too hard and couldn't Daddy *please* make it
so it had levels or something?

Unfortunately, I know just enough maths that it's *not* entirely
obvious to me what makes the 8 times table so much more difficult than
the 4 times table, but when the Princess speaks, things must be done.
Anyway, I whipped out my favorite Scheme impl (Larceny) and began
prototyping out some tools to see if my intuitions about quantify
arithmetic difficulty might actually be accurate. Everything
eventually worked in a semi-satisfactory fashion and I needed to re-
code it all in Java.

And here is where it gets kinda fun: the Java implementation that made
the most sense to me, ended up with all of the main tools fitting into
a single class which is used to tear numbers apart for generating my
difficulty metrics. And obviously there's a high level of congruence
in the test suites. So I timed both sets of code, just for grins :)

Drumroll please.........

Larceny/IAssassin: 64094 ms
        Sun Java 1.6: 96312 ms

And just to add insult to injury, Larceny came in with 25% less LOC:)

Congratulations to Will and his team of serf^Wstudents for winning a
race they weren't even running :) In the spirit of utter openness, the
code is appended below. It will eventually end up on my new web-site
at http://cyber-rush.org/drr, but don't hold your breath...

david rush
--
; Larceny code
(require 'srfi-1)
(define primes '(2))
(define max-prime 2)

(define (prime-stream)
  (let ((primes* primes)
        (start 1))

    (define (update-primes! i other-known)
      (set! start i)
      (if (null? other-known)
          (if (not (memq i primes))
              (begin
                (set! primes
                      (sort (append (list i)
                                    primes)
                            <))
                (set! max-prime (car (reverse primes)))))
          (set! primes* other-known))
      start)

    (lambda ()
      (if (null? primes*)
          (let search ((i (+ start 1)))
            (cond ((< i max-prime)
                   (let search-primes ((primes* primes))
                     (if (< (car primes*) i)
                         (search-primes (cdr primes*))
                         (update-primes! (car primes*) (cdr primes*))
                         )))
                  ((prime? i) (update-primes! i '()))
                  (else
                   (search (+ i 1)))
                  ))
          (begin
            (set! start (car primes*))
            (set! primes* (cdr primes*))
            start)
          ))))

(define (prime? n)
  (if (memq n primes)
      #t
      (let ((limit (sqrt n))
            (primes (prime-stream)))
        (let search ((i (primes)))
          (cond ((< limit i) #t)
                ((= 0 (remainder n i)) #f)
                (else
                 (search (primes)))
                ))
        )))

(define (exponent-of p n)
  (cond ((< n p) 0)
        ((= 0 (remainder n p))
         (+ 1 (exponent-of p (quotient n p))))
        (else 0)
        ))

(define (factors n)
  (let ((limit (sqrt n))
        (stream (prime-stream)))
    (let find-factors ((p (stream)) (factors '()))
      (if (> p n)
          factors
          (let ((exponent (exponent-of p n)))
            (if (> exponent 0)
                (find-factors (stream) (cons (cons p exponent)
factors))
                (find-factors (stream) factors)
                ))
          ))
    ))

(define (unfactors f)
  (let build ((f f) (n 1))
    (if (null? f)
        n
        (build (cdr f)
               (* n (expt (caar f) (cdar f))))
        )))

(define (digits base)
  (lambda (n)
    (let split ((n n) (digits '()))
      (if (> n base)
          (split (quotient n base)
                 (cons (remainder n base) digits))
          (cons n digits))
      )))

(define (digits-reversed base)
  (let ((digits (digits base)))
    (lambda (n) (reverse (digits n)))))

(define (multiplicative-complexity base n)
  (let ((fbase (factors base)))
    (let sum ((f* (factors n)) (complexity 0))
      (if (null? f*)
          complexity
          (let ((f (car f*))
                (rest (cdr f*)))
            (cond ((member f fbase) (sum rest complexity))
                  ((assq (car f) fbase)
                   => (lambda (bf)
                        (let ((bexp (cdr bf))
                              (fexp (cdr f)))
                          (if (> fexp bexp)
                              (sum rest
                                   (+ complexity
                                      (+ (car f)
                                         (- fexp bexp))))
                              (sum rest
                                   (+ complexity (car f)))
                              ))))
                  (else
                   (sum rest
                        (+ complexity
                           (+ (car f)
                              (cdr f)))))
                  ))))))

(define (o f g) (lambda (x) (g (f x))))

(time
 (let ((ps (prime-stream)))
   (for-each (lambda (i) (write `(prime ,i => ,(ps))) (newline)) (iota
10))
   (pretty-print (factors 420)) (newline)
   (write `(max factorial digits = ,(fold max 0 (map (o factors
length) (iota 100000)))))
   (newline)
   ))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
///////////////////////////////////////////////////////////////////////
// Java code
package org.rush;

import java.util.Enumeration;
import java.util.Vector;

public class MetaNumber
    extends Number
{
    // Prime number memoization and management
    static int[] bakedPrimes
        = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

    static Vector<Integer> primes;

    public static Vector<Integer> GetPrimes() {
        if(primes == null) {
            primes = new Vector<Integer>(bakedPrimes.length);
            for(int i = 0; i < bakedPrimes.length; i++)
primes.add(bakedPrimes[i]); }
        return primes; }

    private static Integer getPrime(int i) { return
GetPrimes().get(i); }
    private static int nPrimes() { return GetPrimes().size(); }

    public static class PrimeStream
        implements Enumeration<Integer>
    {
        private Integer nth = 0;

        public boolean hasMoreElements() {
            return true;}

        public Integer nextElement() {
            Integer p = GetNthPrime(nth);
            nth = nth + 1;
            return p; }
    }

    public static boolean IsPrime(Integer p) {
        if(GetPrimes().contains(p))
            return true;
          else {
            double limit = Math.sqrt(p);
            PrimeStream ps = new PrimeStream();
            for(int test = ps.nextElement();
                test <= limit;
                test = ps.nextElement())
                if(p % test == 0) return false;
            return true; }}

    public static Integer GetNthPrime(Integer nth) {
        if(nth > nPrimes() - 1)
            for(int i = nPrimes() - 1; i <= nth; i++) {
                Integer p = GetNthPrime(i) + 1;
                for(; !IsPrime(p); p++);
                GetPrimes().add(p); }
        return
            getPrime(nth); }

    // MetaNumber factoid generators...
    public static Vector<Integer> DigitsReversed(Integer base, Integer
n) {
        MetaNumber m = new MetaNumber(n);
        return m.GetReversedDigits(base); }

    public static PrimeFactors Factors(Integer n) {
        MetaNumber m = new MetaNumber(n);
        return m.GetFactors(); }

    public static int MultiplicativeComplexity(Integer base, Integer
n) {
        int complexity = 0;
        PrimeFactors fbase = MetaNumber.Factors(base);
        PrimeFactors factors = MetaNumber.Factors(n);

        for(int i = 0; i < factors.size(); i++) {
            PrimeFactor factor = factors.get(i);
            if(fbase.contains(factor)) continue;
              else if(fbase.ContainsFactor(factor.Prime)) {
                Integer bexp = fbase.GetExponent(factor.Prime);
                if(bexp > factor.Exponent)
                    complexity += factor.Prime + (factor.Exponent -
bexp);
                  else
                    complexity += factor.Prime; }
              else
                complexity += factor.Prime + factor.Exponent; }

        return
            complexity; }

    public static class PrimeFactor
    {
        public Integer Prime;
        public Integer Exponent;

        public PrimeFactor(Integer prime, Integer exponent) {
            Prime = prime;
            Exponent = exponent; }

        public String toString() {
            return
                "(" + Prime.toString()
                + " . " + Exponent.toString()
                + ")"; }
    }

    public static class PrimeFactors
        extends Vector<PrimeFactor>
    {
        public boolean ContainsFactor(Integer prime) {
            for(int i = 0; i < size(); i++)
                if(get(i).Prime == prime) return true;
            return false; }

        public  Integer GetExponent(Integer prime) {
            for(int i = 0; i < size(); i++)
                if(get(i).Prime == prime) return get(i).Exponent;
            return 0; }

    }

    Number n = 0;

    public MetaNumber(Integer _n) { n = _n; }

    public PrimeFactors GetFactors() {
        PrimeFactors pf = new PrimeFactors();
        Integer k = n.intValue();
        PrimeStream ps = new PrimeStream();
        for(int f = ps.nextElement(); f < k; f = ps.nextElement()) {
            int exponent = 0;
            for(int kk = k; kk % f == 0; kk = kk / f) exponent += 1;
            if(exponent > 0) pf.add(new PrimeFactor(f, exponent)); }
        return pf; }

    public Vector<Integer> GetReversedDigits(int base) {
        Vector<Integer> digits = new Vector<Integer>();
        Integer k = n.intValue();
        while(k > 0) {
            Integer digit = k % base;
            digits.add(digit);
            k = k / base; }
        return digits; }

    // Number interface...
    public int intValue() {
        return n.intValue(); }

    public long longValue() {
        return n.longValue(); }

    public float floatValue() {
        return n.floatValue(); }

    public double doubleValue() {
        return n.doubleValue(); }

    // Testing...
    public static void main(String[] args) {
        long start = (new
java.util.GregorianCalendar()).getTimeInMillis();
        bakedPrimes = new int[] { 2 };
        for(int i = 0; i < 10; i++)
            System.out.printf("prime %d => %s%n", i, GetNthPrime(i));

        PrimeFactors pfs = MetaNumber.Factors(420);
        for(int i = 0; i < pfs.size(); i++)
            System.out.println(pfs.get(i).toString());

        int nFactors = 0;
        for(int i = 0; i < 100000; i++) {
            pfs = MetaNumber.Factors(i);
            if(pfs.size() > nFactors) nFactors = pfs.size(); }
        System.out.printf("max factorial digits = %d%n", nFactors);
        System.out.printf("elapsed time in millis: %d%n", (new
java.util.GregorianCalendar()).getTimeInMillis() - start);
        }