[lisp] calcolatore pigreco

[Bronsa]

Boh mi annoiavo e così ho scritto questo script in Common Lisp che calcola n cifre di pi greco, utilizzando la formula di Machin,e la serie di Taylor per calcolare l'arcocotangente

per rendere piu' veloce l'esecuzione e per evitare stack overflow ha usato tail-recursion, con il quale sovrascrive continuamente lo stesso segmento di stack ad ogni ricorsione senza riempire la memoria ed evitare, appunto stackoverflow

inoltre per evitare di thrownare in floating-point-overflow ,ho deciso di operare su interi anziche' su floating

il tempo di esecuzione quadruplicizza al raddoppiare delle cifre da trovare; sul mio pc per calcolare 50mila cifre dopo la virgola impiega 15secondi, fate i conti voi.
===EDIT==
con la nuova version impiaga sulla mia macchina 17 secondi per calcolare 100mila cifre

il codice e' implementation dependent, l'ho volutamente reso compatibile solo usando sbcl dall momento che è l' unica implementazione in grado di svolgere questi conti e lo fa ottimamente poichè a differenza di altre implementazioni, compila in codice macchina anziche bytecode

purtroppo a causa dei limiti imposti dal linguaggio, viene eseguito senza sfruttare il multi core, l'unico modo che ho trovato per risolvere, è calcolare in parallelo su 2 thread diversi le 2 arcocotangenti, che limita comunque a massimo 2 core utilizzati


il sorgente si trova su http://sprunge.us/eCPK?cl
====EDIT==== dopo varie modifiche ho ottenuto un aumento delle prestazioni pari a circa del 70 %, il codice aggiornato è qui http://sprunge.us/cYNY?cl

commenti e suggerimenti sono ben accetti

P.S se riesco a trovare un modo per trasformare floating in interi anche con l'algoritmo di Gauss-Legendre, implementero quello che rendera' il calcolo _molto_ più veloce

[marco.r]

ciao, dando una rapida occhiata col profiler la maggior parte del tempo viene passato nelle operazioni tra bignum o altre funzioni interne di sbcl, per cui a meno di ridurre le operazioni stesse (o di cambiare algoritmo ovviamente) riuscirai a limare poco (ad esempio hai provato a spezzare in due arccos in modo da non dover moltiplicare per il segno, o di sfruttare entrambi i valori di floor ?).
In generale comunque quando vuoi ottenere le massime prestazioni aggiungi in cima al codice

(declaim (optimize speed))

In questo modo il compilatore salta un po' di controlli (ad esempio i bound degli array); se il programma e' corretto va piu' veloce, se non lo e' rischi che crashi.
Inoltre nelle funzioni piu' interne e' buona cosa specificare il tipo dei dati
Ad esempio

(defun arccot (x-rest n x-elevate sign product)
"Arccotangent calculator, using Taylor series"
(declare (type fixnum sign)
(type integer x-rest n x-elevate product))
...

Aumenta la velocita' delle operazioni numeriche , perche' il compilatore non deve aggiungere il codice per controllare il tipo dell'argomento.

[Bronsa]

guarda, mi son dimenticato di postare ma questa mattina mi son accorto di essermi dimenticato e ho inserito (declaim (optimize (speed 3) (safety 0) (debug 0)))

Per il fatto di definire il tipo delle variabili esplicitamente, non ci avevo pensato :)

Intendi una cosa tipo
(defun arccot+ (..)
...
(arccot- ..))
(defun arccot- (..)
...
(arccot+ ..))
?

==EDIT==
Effettivamente creando 2 funzioni ho guadagnato un pò di ottimizzazione...
http://sprunge.us/JgaZ?cl