hi,
i've been working a little on project euler problem 501.
my first attempt is a burte forcce loop.4iw rote it in java und racket and
found java to be faster by factor 3:
racket
#lang typed/racket
(require racket/unsafe/ops)
(require racket/fixnum)
(require racket/trace)
;(require typed/racket/performance-hint)
(: acht-teiler (-> Fixnum Boolean))
(define (acht-teiler (n : Fixnum))
(: loop (-> Fixnum Fixnum Fixnum Fixnum Boolean))
(define (loop (i : Fixnum) (count : Fixnum) (quadrat : Fixnum) (steigung :
Fixnum))
(cond ((unsafe-fx= quadrat n) #f)
((unsafe-fx> quadrat n) (unsafe-fx= count 3))
((unsafe-fx= (unsafe-fxmodulo n i) 0) (loop (unsafe-fx+ i 1)
(unsafe-fx+ count 1) (unsafe-fx+ quadrat steigung) (unsafe-fx+ steigung 2)))
(else (loop (unsafe-fx+ 1 i) count (unsafe-fx+ quadrat steigung)
(unsafe-fx+ steigung 2)))))
(loop 2 0 4 5))
(acht-teiler 36)
(: achter (-> Fixnum Fixnum))
(define (achter (n : Fixnum))
(: loop (-> Fixnum Fixnum Fixnum))
(define (loop (i : Fixnum) (count : Fixnum))
(cond ((unsafe-fx= i n) count)
((acht-teiler i) (loop (unsafe-fx+ i 1) (unsafe-fx+ count 1)))
(else (loop (unsafe-fx+ i 1) count))))
(loop 2 0))
(time (achter 1000000))
; for 100 = 24, 30, 40, 42, 54, 56, 66, 70, 78 and 88
; f(100) = 10, f(1000) = 180 and f(10e6) = 224427
for java:
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
public class EightDivs implements Runnable{
public static Object lock = new Object();
public static long count = 0;
private long low;
private long high;
public EightDivs(long low, long high){
this.low = low;
this.high = high;
}
public boolean hasEightDivsExact(long a){
int divs = 0;
for(long i =1;i<=a;i++){
if(a % i == 0){
divs++;
}
}
return divs == 8;
}
public boolean hasEightDivs(long a){
int divs = 0;
for(long i = 2; i*i <= a && divs < 4;i++){
if(a % i == 0){
divs++;
if (i*i == a && divs >= 3){
return false;
}
}
}
return divs == 3;
}
public static void main(String[] args) throws InterruptedException {
ExecutorService ex = Executors.newFixedThreadPool(4);
long old = 1;
long start = System.currentTimeMillis();
// for(long i = 0L; i<= 1000_000L;i+=100_00){
// ex.execute(new EightDivs(old, i));
//// System.out.println(old +" low " + i + " high");
// old = i;
// }
// ex.shutdown();
// ex.awaitTermination(300, TimeUnit.SECONDS);
new EightDivs(1, 1000_000).run();
long end = System.currentTimeMillis();
System.out.println((end-start)/1000d+" Seconds");
// new EightDivs(1, 1000).hasEightDivs(24);
System.out.println(count);
}
@Override
public void run() {
for(long i = low;i<high;i++){
if(hasEightDivs(i)){
// System.out.println(i);
synchronized (lock) {
count++;
}
}
}
System.out.println(low +" low " + high + " high done");
}
}
--END CODE
java code runs in 4.5 seconds
racket code takes 12.5 seconds to complete (in cli-mode)
i typed racket and used unsafe operations. some perfomance hints from the guide
don't seem to apply since i already tyyped racket.
the optimization coach hints to use define-inline but it seems to be available
only in non-typed-raket.
what can i do to speed things up (except better algorithms?)
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
