I was comparing some code in Qi with that of sbcl, I posted a question in
comp.lang.lisp asking for a way to improve the perfomance, WJ gave a typed
racket version that was slower than sbcl and also much slower than cpp.
Daniel Rupis wrote:
Note: The code compute the number of primes below 30000 by a very
brute force attack. (I know there are far better algorithms for this
task :))
(defun divisibleRec(I J)
(declare (optimize (speed 3) (safety 0) (compilation-speed 0))
(type (integer 0 300000) I J))
(when (= J 1) (return-from divisibleRec nil))
(if (zerop (rem I J)) t (divisibleRec I (1- J))))
Typed Racket:
#lang typed/racket
(define: (divisible-rec (i : Integer) (j : Integer)) : Boolean
(cond ((= j 1) #f)
((zero? (modulo i j)) #t)
(else (divisible-rec i (sub1 j)))))
(defun divisible(N)
(declare (optimize (speed 3) (safety 0) (compilation-speed 0))
(type (integer 0 300000) N))
(divisibleRec N (1- N)))
(define: (divisible (n : Integer)) : Boolean
(divisible-rec n (sub1 n)))
(defun totalprimes(k)
(declare (optimize (speed 3) (safety 0) (compilation-speed 0)))
(loop for n of-type (integer 0 300000) from 2 to k count (not
(divisible n)))
(define: (total-primes (k : Integer)) : Integer
(for/sum ([n (in-range 2 (add1 k))])
(if (divisible n) 0 1)))
(displayln (total-primes 30999))
3340
Thanks to all that responded.
Results:
Original code 5.280 seconds of real time
Benjamin Kreuter code: 6.582 seconds of real time
WJ code (typep racket) 10.544 seconds
Conclusion:
1.- Typep racket is deceptively slow, I was expecting something better here
(racket people are developing a math library with typep racket)
2.- Benjamin code is not a solution, it gives worse performance.
3.- Paul Khuong tell us that this problem will be here to stay for ever.
What's the better way to include machine code like the one generate by C++ in
Lisp. That is inline the code for example only for functions from integer to
integers.
Thanks again.
I should say that I like racket, but I find macros in racket rather difficult.
I can use macros in common-lisp but I still can't use racket macros. (I am
trying to say that perhaps macros in racket are something difficult to grasp).
Original Qi code and C++ code (30000 -> 30999)
------- Qi Code ----------------------------------------
(define divisibleRec
{number --> number --> boolean}
I J -> (if (= J 1) false (if (= (fmod I J) 0) true (divisibleRec I (- J 1)))))
(define divisible
{number --> boolean}
I -> (divisibleRec I (- I 1)))
(define totalPrimesAcc
{number --> number --> number}
1 Acc -> Acc
I Acc -> (if (= (divisible I) false) (totalPrimesAcc (- I 1) (+ 1 Acc))
(totalPrimesAcc (- I 1) Acc)))
(define totalPrimes
{number --> number}
I -> (totalPrimesAcc I 0))
(totalPrimes 30000)
----------------------------------------------------------------------
#include <stdio.h>
bool divisibleRec(int i, int j){
if(j==1){ return false; }
else if(i%j==0){ return true; }
else{ return divisibleRec(i,j-1); }
}
bool divisible(int i){ return divisibleRec(i, i-1); }
int main(void){
int i, count =0;
for(i=2; i<30000; ++i){
if(divisible(i)==false){
count = count+1;
}
}
printf("number of primes = %d\n",count);
return 0;
}
----------------------------------------------------------
____________________
Racket Users list:
http://lists.racket-lang.org/users
