Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Scheme Programming Language

Larceny Rocks Redux (or Lies, Damned Lies and Benchmarks (or Wake up and Smell the Coffee (or ...)))


Hi y'all,

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);
        }

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc