Mandelbrot Imposta implementazione in Common Lisp

Question

Ho lavorato a un'implementazione di Mandelbrot Set in diverse lingue. Ho un'implementazione funzionante in C++, C#, Java e Python, ma l'implementazione Common Lisp ha alcuni bug che non riesco a capire. Genera il set ma da qualche parte nella pipeline il set viene distorto. Ho provato e so con vicino a certezza che il file I/O CLO non è il problema - è improbabile ma possibile, l'ho testato abbastanza bene.

Si noti che l'intento di queste implementazioni è per loro punto di riferimento uno contro l'altro - così sto cercando di mantenere le implementazioni di codice il più possibile simili in modo che siano comparabili.

L'insieme di Mandelbrot (qui generato dalla implementazione di Python):

http://www.freeimagehosting.net/uploads/65cb71a873.png http://www.freeimagehosting.net/uploads/65cb71a873.png "Mandelbrot (generato da Python)"

Ma il mio programma di Common Lisp genera questo:

http://www.freeimagehosting.net/uploads/50bf29bcc9.png http://www.freeimagehosting.net/uploads/50bf29bcc9.png "Common Lisp distorta Mandelbrot Set di versione"

Il bug è identico in entrambi CLISP e SBCL.

CODICE:

Common Lisp:

(defun mandelbrot (real cplx num_iter) 
    (if (> (+ (* real real) (* cplx cplx)) 4) 
     1 
     (let ((tmpreal real) (tmpcplx cplx) (i 1)) 
     (loop 
      (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
      (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpcplx tmpcplx)) 
       real)) 
      (setq i (+ i 1)) 
      (cond 
       ((> (+ (* tmpreal tmpreal) 
        (* tmpcplx tmpcplx)) 4) (return i)) 
       ((= i num_iter) (return 0))))))) 

(defun floordiv (dend sor) (/ (- dend (mod dend sor)) sor)) 

(defclass xbm() (
    (data :accessor data :initarg :data) 
    (dim :reader dim :initarg :dim) 
    (arrsize :reader arrsize :initarg :arrsize))) 

(defmethod width ((self xbm)) (third (dim self))) 

(defmethod height ((self xbm)) (second (dim self))) 

(defun generate (width height) 
    (let ((dims (list 0 0 0)) (arrsize_tmp 0)) 
     (setq dims (list 0 0 0)) 
     (setf (second dims) height) 
     (setf (third dims) width) 
     (setf (first dims) (floordiv (third dims) 8)) 
     (unless (= (mod width 8) 0) (setf (first dims) (+ (first dims) 1))) 
     (setq arrsize_tmp (* (first dims) (second dims))) 
     (make-instance 'xbm 
     :data (make-array arrsize_tmp :initial-element 0) 
     :dim dims 
     :arrsize arrsize_tmp))) 

(defun writexbm (self f) 
    (with-open-file (stream f :direction :output :if-exists :supersede) 
     (let ((fout stream)) 
     (format fout "#define mandelbrot_width ~d~&" (width self)) 
     (format fout "#define mandelbrot_height ~d~&" (height self)) 
     (format fout "#define mandelbrot_x_hot 1~&") 
     (format fout "#define mandelbrot_y_hot 1~&") 
     (format fout "static char mandelbrot_bits[] = {") 
     (let ((i 0)) 
      (loop 
       (if (= (mod i 8) 0) 
        (format fout "~& ") 
        (format fout " ")) 
       (format fout "0x~x," (svref (data self) i)) 
       (unless (< (setf i (+ i 1)) (arrsize self)) 
        (return t))))))) 

(defmethod setpixel ((self xbm) (x integer) (y integer)) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-ior (svref (data self) val) (ash 1 (mod x 8))))))) 

(defmethod unsetpixel ((self xbm) (x integer) (y integer)) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-xor (boole boole-ior 
      (svref (data self) val) (ash 1 (mod x 8))) (ash 1 (mod x 8))))))) 

(defmethod draw_mandelbrot ((xbm xbm) (num_iter integer) (xmin number) 
    (xmax number) (ymin number) (ymax number)) 

    (let ((img_width (width xbm)) (img_height (height xbm)) (xp 0)) 
     (loop 
     (if (< xp img_width) 
      (let ((xcoord (+ (* (/ xp img_width) (- xmax xmin)) xmin)) (yp 0)) 
       (loop 
        (if (< yp img_height) 
        (let (
         (ycoord (+ (* (/ yp img_height) (- ymax ymin)) ymin))) 
         (let ((val (mandelbrot xcoord ycoord num_iter))) 
          (if (> val 0) (unsetpixel xbm xp yp) (setpixel xbm xp yp))) 
         (setq yp (+ yp 1))) 
        (return 0))) 
       (setq xp (+ xp 1))) 
      (return 0))))) 

(defun main() 
    (let ((maxiter 0) (xmin 0) (xmax 0) (ymin 0) (ymax 0) (file nil) (xsize 0) (ysize 0) (picture nil)) 
     (format t "maxiter? ") 
     (setq maxiter (read)) 
     (format t "xmin? ") 
     (setq xmin (read)) 
     (format t "xmax? ") 
     (setq xmax (read)) 
     (format t "ymin? ") 
     (setq ymin (read)) 
     (format t "ymax? ") 
     (setq ymax (read)) 
     (format t "file path: ") 
     (setq file (read-line)) 
     (format t "picture width? ") 
     (setq xsize (read)) 
     (format t "picture height? ") 
     (setq ysize (read)) 
     (format t "~&") 
     (setq picture (generate xsize ysize)) 
     (draw_mandelbrot picture maxiter xmin xmax ymin ymax) 
     (writexbm picture file) 
     (format t "File Written.") 
     0)) 

(main) 

e la più vicina ad essa è Python:

from xbm import * 

def mandelbrot(real_old,cplx_old,i): 
    real = float(real_old) 
    cplx = float(cplx_old) 
    if (real*real+cplx*cplx) > 4: 
     return 1 
    tmpreal = real 
    tmpcplx = cplx 
    for rep in range(1,i): 
     tmpb = tmpcplx 
     tmpcplx = tmpreal*tmpcplx*2 
     tmpreal = tmpreal*tmpreal - tmpb*tmpb 
     tmpcplx += cplx 
     tmpreal += real 
     tmpb = tmpcplx*tmpcplx + tmpreal*tmpreal 
     if tmpb > 4: 
     return rep+1 
    else: 
     return 0 

def draw_mandelbrot(pic, num_iter, xmin, xmax, ymin, ymax): 
    img_width = pic.width() 
    img_height = pic.height() 
    for xp in range(img_width): 
     xcoord = (((float(xp))/img_width) * (xmax - xmin)) + xmin 
     for yp in range(img_height): 
     ycoord = (((float(yp))/img_height) * (ymax - ymin)) + ymin 
     val = mandelbrot(xcoord, ycoord, num_iter) 
     if (val): 
      pic.unsetpixel(xp, yp) 
     else: 
      pic.setpixel(xp, yp) 

def main(): 
    maxiter = int(raw_input("maxiter? ")) 
    xmin = float(raw_input("xmin? ")) 
    xmax = float(raw_input("xmax? ")) 
    ymin = float(raw_input("ymin? ")) 
    ymax = float(raw_input("ymax? ")) 
    file = raw_input("file path: ") 
    xsize = int(raw_input("picture width? ")) 
    ysize = int(raw_input("picture height? ")) 
    print 
    picture = xbm(xsize, ysize) 
    draw_mandelbrot(picture, maxiter, xmin, xmax, ymin, ymax) 
    picture.writexbm(file) 
    print "File Written. " 
    return 0; 

main() 

[xbm.py] 

from array import * 

class xbm: 
    def __init__(self, width, height): 
     self.dim = [0, 0, 0] 
     self.dim[1] = height 
     self.dim[2] = width 
     self.dim[0] = self.dim[2]/8 
     if width % 8 != 0: 
     self.dim[0] += 1 
     self.arrsize = self.dim[0] * self.dim[1] 
     self.data = array('B', (0 for x in range(self.arrsize))) 
     self.hex = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'] 
    def __nibbletochar__(self, a): 
     if a < 0 or a > 16: 
     return '0' 
     else: 
     return self.hex[a] 
    def setpixel(self, x, y): 
     if x < self.dim[2] and y < self.dim[1]: 
     self.data[(x/8) + (y * self.dim[0])] |= 1 << (x % 8) 
    def unsetpixel(self, x, y): 
     if x < self.dim[2] and y < self.dim[1]: 
     self.data[(x/8) + (y * self.dim[0])] |= 1 << (x % 8) 
     self.data[(x/8) + (y * self.dim[0])] ^= 1 << (x % 8) 
    def width(self): 
     return self.dim[2] 
    def height(self): 
     return self.dim[1] 
    def writexbm(self, f): 
     fout = open(f, 'wt') 
     fout.write("#define mandelbrot_width ") 
     fout.write(str(self.dim[2])) 
     fout.write("\n#define mandelbrot_height ") 
     fout.write(str(self.dim[1])) 
     fout.write("\n#define mandelbrot_x_hot 1") 
     fout.write("\n#define mandelbrot_y_hot 1") 
     fout.write("\nstatic char mandelbrot_bits[] = {") 
     for i in range(self.arrsize): 
     if (i % 8 == 0): fout.write("\n\t") 
     else: fout.write(" ") 
     fout.write("0x") 
     fout.write(self.__nibbletochar__(((self.data[i] >> 4) & 0x0F))) 
     fout.write(self.__nibbletochar__((self.data[i] & 0x0F))) 
     fout.write(",") 
     fout.write("\n};\n") 
     fout.close(); 

posso postare il C++, C#, o il codice Java come pure bisogno di essere

Grazie!

EDIT: Grazie per la risposta di Edmund Ho trovato il bug-Solo qualcosa che scivolò attraverso le fessure sul porting. codice modificato:

(defun mandelbrot (real cplx num_iter) 
    (if (> (+ (* real real) (* cplx cplx)) 4) 
     1 
     (let ((tmpreal real) (tmpcplx cplx) (i 1) (tmpb cplx)) 
     (loop 
      (setq tmpb tmpcplx) 
      (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
      (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpb tmpb)) 
       real)) 
      (setq i (+ i 1)) 
      (cond 
       ((> (+ (* tmpreal tmpreal) 
        (* tmpcplx tmpcplx)) 4) (return i)) 
       ((= i num_iter) (return 0))))))) 

(defun floordiv (dend sor) (/ (- dend (mod dend sor)) sor)) 

(defclass xbm() (
    (data :accessor data :initarg :data) 
    (dim :reader dim :initarg :dim) 
    (arrsize :reader arrsize :initarg :arrsize))) 

(defun width (self) (third (dim self))) 

(defun height (self) (second (dim self))) 

(defun generate (width height) 
    (let ((dims (list 0 0 0)) (arrsize_tmp 0)) 
     (setq dims (list 0 0 0)) 
     (setf (second dims) height) 
     (setf (third dims) width) 
     (setf (first dims) (floordiv (third dims) 8)) 
     (unless (= (mod width 8) 0) (setf (first dims) (+ (first dims) 1))) 
     (setq arrsize_tmp (* (first dims) (second dims))) 
     (make-instance 'xbm 
     :data (make-array arrsize_tmp :initial-element 0) 
     :dim dims 
     :arrsize arrsize_tmp))) 

(defun writexbm (self f) 
    (with-open-file (stream f :direction :output :if-exists :supersede) 
     (let ((fout stream)) 
     (format fout "#define mandelbrot_width ~d~&" (width self)) 
     (format fout "#define mandelbrot_height ~d~&" (height self)) 
     (format fout "#define mandelbrot_x_hot 1~&") 
     (format fout "#define mandelbrot_y_hot 1~&") 
     (format fout "static char mandelbrot_bits[] = {") 
     (let ((i 0)) 
      (loop 
       (if (= (mod i 8) 0) 
        (format fout "~& ") 
        (format fout " ")) 
       (format fout "0x~x," (svref (data self) i)) 
       (unless (< (setf i (+ i 1)) (arrsize self)) 
        (return t))))))) 

(defun setpixel (self x y) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-ior (svref (data self) val) (ash 1 (mod x 8))))))) 

(defun unsetpixel (self x y) 
    (if (and (< x (third (dim self))) (< y (second (dim self)))) 
     (let ((val (+ (floordiv x 8) (* y (first (dim self)))))) 
     (setf (svref (data self) val) (boole boole-xor (boole boole-ior 
      (svref (data self) val) (ash 1 (mod x 8))) (ash 1 (mod x 8))))))) 

(defun draw_mandelbrot (xbm num_iter xmin xmax ymin ymax) 

    (let ((img_width (width xbm)) (img_height (height xbm)) (xp 0)) 
     (loop 
     (if (< xp img_width) 
      (let ((xcoord (+ (* (/ xp img_width) (- xmax xmin)) xmin)) (yp 0)) 
       (loop 
        (if (< yp img_height) 
        (let (
         (ycoord (+ (* (/ yp img_height) (- ymax ymin)) ymin))) 
         (let ((val (mandelbrot xcoord ycoord num_iter))) 
          (if (> val 0) (unsetpixel xbm xp yp) (setpixel xbm xp yp))) 
         (setq yp (+ yp 1))) 
        (return 0))) 
       (setq xp (+ xp 1))) 
      (return 0))))) 

(defun main() 
    (let ((maxiter 0) (xmin 0) (xmax 0) (ymin 0) (ymax 0) (file nil) (xsize 0) (ysize 0) (picture nil)) 
     (format t "maxiter? ") 
     (setq maxiter (read)) 
     (format t "xmin? ") 
     (setq xmin (read)) 
     (format t "xmax? ") 
     (setq xmax (read)) 
     (format t "ymin? ") 
     (setq ymin (read)) 
     (format t "ymax? ") 
     (setq ymax (read)) 
     (format t "file path: ") 
     (setq file (read-line)) 
     (format t "picture width? ") 
     (setq xsize (read)) 
     (format t "picture height? ") 
     (setq ysize (read)) 
     (format t "~&") 
     (setq picture (generate xsize ysize)) 
     (draw_mandelbrot picture maxiter xmin xmax ymin ymax) 
     (writexbm picture file) 
     (format t "File Written.") 
     0)) 

(main) 

Anche se il codice non è molto LISP-ish (che è una parola?) funziona. Grazie a tutti coloro che ha postato/commentato/risposto :)

Answer 1

Non sono sicuro che questa parte è corretto:

 (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
     (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpcplx tmpcplx)) 
      real)) 

Isn' t tempcplx viene sovrascritto con il suo nuovo valore sulla prima riga, nel senso che la seconda riga utilizza il nuovo valore, non quello originale?

Nella versione di Python si sta evitando questo problema utilizzando tmpb:

tmpb = tmpcplx 
    tmpcplx = tmpreal*tmpcplx*2 
    tmpreal = tmpreal*tmpreal - tmpb*tmpb 
    tmpcplx += cplx 
    tmpreal += real 

Mi sembra la versione Lisp dovrebbe fare qualcosa di simile, cioè memorizzare il valore originale di tmpcplx prima, e utilizzare quel negozio per il calcolo di tmpreal:

 (setq tmpb cplx) 
     (setq tmpcplx (+ (* (* tmpreal tmpcplx) 2) cplx)) 
     (setq tmpreal (+ (- (* tmpreal tmpreal) (* tmpb tmpb)) 
      real)) 

Answer 2

Alcune osservazioni circa il vostro codice:

• Mandelbrot: mancano le dichiarazioni, le piazze sono calcolati due volte nel ciclo

• mandelbrot: nel calcolo per TMPREAL si sta utilizzando il nuovo valore di TMPCLX, non quello precedente

• Non si desidera utilizzare METODI per impostare i pixel. LENTO.

• FLOORDIV è uno dei pavimento o TRUNCATE (a seconda di ciò che si desidera) in Common Lisp, vedi (FLOOR 10 3)

• dichiarazioni di tipo utilizzo

• in writexbm non lo fanno più volte chiamata dati e ARRSIZE

• setPixel, unsetpixel sembra molto costoso, di nuovo più volte dereferenziazione struttura

• draw-Mandelbrot ha un sacco di r calcoli epeated che si possono fare una volta

• Common Lisp ha array 2d che semplificano il codice

• Common Lisp ha numeri complessi, che semplificano anche il codice

• un nome di variabile 'sé' non fa senso in Common Lisp. Chiamalo per quello che è.

Generalmente il codice è pieno di rifiuti. Non ha molto senso confrontare il tuo codice, poiché è scritto in uno stile che si spera nessuno usi in Common Lisp. Common Lisp è stato progettato con l'esperienza di grandi software matematici come Macsyma e consente di scrivere codice matematico in modo diretto (niente oggetti, solo funzioni su numeri, matrici, ...). I migliori compilatori possono sfruttare i tipi primitivi, le operazioni primitive e le dichiarazioni di tipo. Quindi lo stile è diverso da quello che si potrebbe scrivere in Python (che di solito è Python orientato agli oggetti o chiamate ad un certo codice C) o Ruby. In un codice numerico pesante, di solito non è una buona idea avere dispatch dinamico come con CLOS. Impostare i pixel in bitmap tramite le chiamate CLOS in un LOOP stretto è davvero qualcosa che si vuole evitare (a meno che non si sappia come ottimizzarlo).

I migliori compilatori Lisp compileranno le funzioni numeriche per indirizzare il codice macchina. Durante la compilazione danno indicazioni su quali operazioni sono generiche e non possono essere ottimizzate (fino a quando lo sviluppatore aggiunge più informazioni sul tipo). Lo sviluppatore può anche "SMONTARE" le funzioni e verificare il codice generico o le chiamate di funzioni non necessarie. 'Nel codice consing numerico del ' "TIME' fornisce informazioni di runtime e informa anche lo sviluppatore per la quantità di memoria' Consed galleggia' è un normale problema di prestazioni

Quindi, per riassumere:

• se si scrive il codice e pensare che lo fa lo stesso in diverse lingue, in cui il codice è simile o ha una struttura simile, questo potrebbe non essere il caso - a meno che tu non sappia entrambe le lingue e entrambe le implementazioni lingua

• . se scrivi il codice in una lingua e lo porti in uno stile simile a una lingua diversa, potresti perdere un wh ole culture esistenti per scrivere soluzioni a questi tipi di problemi in un modo diverso. Ad esempio si può scrivere codice in C++ in uno stile orientato agli oggetti e portarlo in un modo simile a FORTRAN. Ma nessuno scrive questo codice in FORTRAN. Scritto in stile FORTRAN, tipicamente si tradurrà in un codice più veloce, soprattutto perché i compilatori sono fortemente ottimizzati per il codice FORTRAN idiomatico.

• "When in Rome, parlare come i romani"

Esempio:

in SetPixel c'è una chiamata a (prima (auto dim)). Perché non rendere quel valore uno slot nella struttura in primo luogo, invece di fare sempre una lista di accesso? Ma poi il valore è costante durante il calcolo. Ancora la struttura viene passata e il valore viene recuperato continuamente. Perché non solo ottenere il valore al di fuori del ciclo principale e passarlo direttamente? Invece di fare più calcoli di esso?

Per darvi un'idea di come il codice potrebbe essere scritto (con dichiarazioni di tipo, cicli, numeri complessi, ...), ecco una versione leggermente diversa del calcolo di mandelbrot.

L'algoritmo di base:

(defvar *num-x-cells* 1024) 
(defvar *num-y-cells* 1024) 
(defvar *depth* 60) 


(defun m (&key (left -1.5) (top -1.0) (right 0.5) (bottom 1.0) (depth *depth*)) 
    (declare (optimize (speed 3) (safety 0) (debug 0) (space 0))) 
    (loop with delta-x-cell float = (/ (- right left) *num-x-cells*) 
     and delta-y-cell float = (/ (- bottom top) *num-y-cells*) 
     and field = (make-array (list *num-x-cells* *num-y-cells*)) 
     for ix fixnum below *num-x-cells* 
     for x float = (+ (* (float ix) delta-x-cell) left) 
     do (loop for iy fixnum below *num-y-cells* 
       for y = (+ (* (float iy) delta-y-cell) top) 
       do (loop for i fixnum below depth 
          for z of-type complex = (complex x y) 
          then (+ (complex x y) (* z z)) 
          for exit = (> (+ (* (realpart z) (realpart z)) 
              (* (imagpart z) (imagpart z))) 
             4) 
          finally (setf (aref field ix iy) i) 
          until exit)) 
     finally (return field))) 

Sopra funzione restituisce una matrice 2D di numeri.

Scrivere un file xbm:

(defun writexbm (array pathname &key (black *depth*)) 
    (declare (fixnum black) 
      (optimize (speed 3) (safety 2) (debug 0) (space 0))) 
    (with-open-file (stream pathname :direction :output :if-exists :supersede) 
    (format stream "#define mandelbrot_width ~d~&" (array-dimension array 0)) 
    (format stream "#define mandelbrot_height ~d~&" (array-dimension array 1)) 
    (format stream "#define mandelbrot_x_hot 1~&") 
    (format stream "#define mandelbrot_y_hot 1~&") 
    (format stream "static char mandelbrot_bits[] = {") 
    (loop for j fixnum below (array-dimension array 1) do 
      (loop for i fixnum below (truncate (array-dimension array 0) 8) 
       for m fixnum = 0 then (mod (1+ m) 8) do 
       (when (zerop m) (terpri stream)) 
       (format stream "0x~2,'0x, " 
         (let ((v 0)) 
          (declare (fixnum v)) 
          (dotimes (k 8 v) 
          (declare (fixnum k)) 
          (setf v (logxor (ash (if (= (aref array 
                   (+ (* i 8) k) j) 
                 black) 
                1 0) 
               k) 
              v))))))) 
    (format stream "~&}~&"))) 

Sopra funzione prende un array e un percorso e scrive la matrice in formato XBM. Un numero di 'nero' sarà 'nero' e gli altri numeri sono 'bianco'

chiamata

(writexbm (m) "/tmp/m.xbm")