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 [email protected].
For more options, visit https://groups.google.com/d/optout.
