Original von Munxar
Nur so ein kleiner Mathematischer Tip:
Die Mandelbrot Menge (Apfelmaennchen) ist zur Reellen Achse (x-Achse) Symmetrisch.
-> nur die positiven imaginaeren Teil rechnen und die Pixel spiegeln! Geht doppelt so schnell OHNE etwas besonderes gemacht zu haben.

Naja, aber das geht nur so lange gut, wie du nicht hineinzoomst. Dann müsstest du die Lage der Achse bestimmen und den Anteil der Pixel drüber bestimmen und und und. Außerdem wenn du nur im positiven Bereich gezoomt hast kannst du es auch nicht anwenden. Ich weiß ehrlich gesagt nicht, ob es den Aufwand wirklich lohnt...

Max

Original von Munxar
Gerade die länge deiner Zahl bestimmt wie tief du in die Menge hinein "zoomen" kannst.
Dazu kommt dass du keine einzige c mathe funktion brauchst (schon gar kein exp).

Braucht ich ja auch nicht. War nur ein Beispiel. Aber z.B. pow könnte Anwendung finden. Die Frage ist, ob das schneller ist...

Nur +-*/ und wenn du besonders hart bist machst du alles nur mit Integern (bzw. long ints) und ersetzt das * und / durch links und rechts shifts. Das geht etwas flotter als flops (ausser du machst das ganz vektoriell mit AltiVec).

An AltiVec hatte ich auch schon gedacht. Zur Zeit ist bei mir aber das langsamste die Darstellung

Max

An AltiVec hatte ich auch schon gedacht. Zur Zeit ist bei mir aber das langsamste die Darstellung

Mit was machst du deine Darstellung? NSImage? Probier mal glDrawPixels() aus OpenGL, damit kannst du direkt in den Framebuffer schreiben. Ist sehr schnell.

Ach ja und pow() aus math.h ist das schlimmst was du zum potenzieren nehmen kannst
Mach z.B. fuer x^2 lieber x*x das gehr wirklich merklich schneller.

Gruß Sascha

Hi.

long double mit gcc auf einem PowerPC ist ziemlich unsinng zur Zeit. Deswegen die Warnung des Compilers.

double ist 64bit groß. Auf einen PowerPC ist "long double" ebenfalls 64bit groß.

Auf einem x86 ist "long double" 96bit groß, was den Sinn erkärt.

Ich weiß nicht wie breit die FPU in einem G4/G5 ist, oder ob es mit einem IBM-Compiler anders wäre...

Lohnt sich gewiss. Du bestimmst die "größere" Seite und berechnest dann nur eine und setzt auf beiden. Notfalls machst du jeweil eine Abfrage, ob der Punkt gerade auf dieser Seite sichtbar ist. (Was du aber eigentlich nicht tun musst, da ein überflüssiger Punkt herausgeclipt wird. Aber die Abfrage ist freilich schneller als das setzen eines nicht notwendigen Punktes.)

Das ganze dürfte nur dann langsamer werden, wenn du einen Ausschnitt nur oberhalb oder unterhalb der Achse hast. (Oder nur einen ganz kleinen Teil der anderen "Achseseite" siehst.) Das lässt sich aber notfalls schnell abfragen. Und gerade im Zooming wird die Performance ja immer unwichtiger.

Was sich auch lohnt: Der Realteil berechnet sich durch



Das lässt sich auch so schreiben. Spart eine Multiplikation.

Ah, der gute alte Binom.

Man kann sich in der Beispielsource übrigens auch noch eine Zuweisung sparen, da z_i nach der Berechnung nicht mehr eingesetzt wird. Ob's was bringt ...

Original von Munxar
Mit was machst du deine Darstellung? NSImage? Probier mal glDrawPixels() aus OpenGL, damit kannst du direkt in den Framebuffer schreiben. Ist sehr schnell.

Ich machs mit ner BitmapImageRep und Quartz, das geht in Ordnung. Außerdem müssen ja nicht alle OpenGL machen Ich hab aber meine zeichen-prozedur insofern verbessert, als dann nicht mehr jedes Pixel einzeln, sondern nur noch reihen gezeichnet werden. und dass ich farben cache und so ein spaß...

Ach ja und pow() aus math.h ist das schlimmst was du zum potenzieren nehmen kannst
Mach z.B. fuer x^2 lieber x*x das gehr wirklich merklich schneller.

Ist mir schon klar. Ich hab das ja auch nur als BEISPIEL angebracht. Egal.

Max

Original von ponder

Quellcode

1. z.real= z.real*z.real-z.img*z.img+c.real;

Das lässt sich auch so schreiben. Spart eine Multiplikation.

Quellcode

1. z.real= (z.real+z.img)*(z.real-z.img)+c.real;

Ich moechte jetzt nicht rumpingeln aber


Spart 2 Multis und eine Addition und nene haufen weitere Rechenarbeit wenn du einen Punkt hast der nicht konvergiert (was in der Regel die interessanten Gebiete sind).
B. Mandelbrot hat u.A. bewiesen, dass eine komplexe Zahl die einmal den Konvergenzkreis verlassen hat (im Fall z=z^2+c ist der Radius r = 4), nie mehr zur Menge konvergiert.
Auf deutsch: ist der Betrag der komplexen Zahl z irgendwann waerend der Iteration groeßer als 4 kannste aufhoeren! Ohne die bloede Wurzel: z.real*z.real + z.imag*z.imag > 16

So genug Mathe

Sascha

So genug Mathe

Stimmt schon, hätte man auch selber drauf kommen können. naja egal, danke ich werd's weiter optimieren. *quetsch*

Wann war jetzt nochmal die Besprechung der Ergebnisse?

Das mit dem sqrt war ne gute Idee, hat bei mir einiges an Performance gebracht.

Wie bringt man denn jetzt Farbe ins Spiel?
Ich nehm den Iterationswert und setze damit gleichermassen die Farbwerte fuer RGB, da kommt halt dann Grau raus.Sieht auch soweit ganz net aus.
Fuer Farbe koennte man die Iterationswerte in verschiedene Bereiche aufteilen, wie macht Ihr das denn?

so long,
Manfred

Original von asrael
Wie bringt man denn jetzt Farbe ins Spiel?
Ich nehm den Iterationswert und setze damit gleichermassen die Farbwerte fuer RGB, da kommt halt dann Grau raus.Sieht auch soweit ganz net aus. ;)

Ohne daß ich beim Workshop mitmachen würde und ohne Deinen Ansatz zu kennen. (Also wie Du an die Bilddaten rangehst.)

Wenn Du nicht direkt auf die Rohdaten zugreifst könntest Du beispielsweise + (NSColor *)colorWithDeviceHue:(float)hue saturation:(float)saturation brightness:(float)brightness alpha:(float)alpha benutzen und einfach den Hue zwischen 0 und 1 benutzen statt das für Deinen Grauwert zu benutzen.

Nur ein Gedanke.

Wenn Du nicht direkt auf die Rohdaten zugreifst könntest Du beispielsweise + (NSColor *)colorWithDeviceHue:(float)hue saturation:(float)saturation brightness:(float)brightness alpha:(float)alpha benutzen und einfach den Hue zwischen 0 und 1 benutzen statt das für Deinen Grauwert zu benutzen

Hmm, ich greif zwar nicht direkt auf die Rohdaten zu. Habe aber von Cocoa auf CoreGraphics umgestellt, weils einfach zuegiger ist.
Von daher hab ich keinen Zugriff auf die Methode. Meine Farbe setze ich momentan mit CGContextSetRGBFillColor.

@asrael
Wenn du eigene Farbverlaeufe haben willst kannst du das im RGB Raum z.B. so machen.
Farben f1 (1, 0, 0) (rot) und Farbe f2(0,1,1) (gelb) kannst du überblenden mit:
f(t) = f1*(1-t) + t*f2
Für t=0 bekommt man rot und für t=1 bekommt man gelb. Für andere Werte von [0,1] hat man Farben dazwischen (hellrot, orange, ...)
(Achtung f1 und f2 sind Vektoren also komponentenweise multiplizieren)

Willst du mehr als zwei Farben überblenden kannst du die Farben auch über eine Bezierkurve interpolieren. Das ist nicht mehr in 2 Zeilen hingeschrieben

Falls Interesse besteht poste ich mal eine Funtion die beliebig (solange der Speicher reicht) viele Farben über einen Bezierkurve interpolieren kann.

Gruß Sascha

Original von ponder
Was sich auch lohnt: Der Realteil berechnet sich durch

Quellcode

1. z.real= z.real*z.real-z.img*z.img+c.real;

Das lässt sich auch so schreiben. Spart eine Multiplikation.

Quellcode

1. z.real= (z.real+z.img)*(z.real-z.img)+c.real;

Das wird jedoch nichts bringen. Das obere dürfte ein fmul, ein fmsub und ein fadd ergeben. Das untere ein fsub, fadd und ein fmadd. Unentschieden.

Original von Munxar
[...] und wenn du besonders hart bist machst du alles nur mit Integern (bzw. long ints) und ersetzt das * und / durch links und rechts shifts. Das geht etwas flotter als flops [...].

Nee. Das stimmte vor 10 Jahren vielleicht mal auf x86. Heute gilt das jedoch nicht mehr, und auf PowerPC hat das noch nie gegolten. Fixkomma-Arithmetik ist im Übrigen bei Fraktalen nicht geeignet, weil die auftetenden Wertebereiche so groß sind.

Optimale Zeichengeschwindigkeit erreicht man hier wohl indem man eine Offscreen-Bitmap

NSBitmapImageRep* meineBitmap;

meineBitmap = [[NSBitmapImageRep alloc] initWithBitmapDataPlanes:nil
pixelsWide:meineXAufloesung
pixelsHigh:meineYAufloesung
bitsPerSample:8
samplesPerPixel:4
hasAlpha:YES
isPlanar:NO
colorSpaceName:NSCalibratedRGBColorSpace
bytesPerRow:0
bitsPerPixel:0];

im Speicher hält und dort die RGB-Pixeldaten direkt manipuliert:

struct Farbe32Bit { unsigned char r,g,b,alpha; };
Farbe32Bit* meinePixeldaten = (Farbe32Bit*)[meineBitmap bitmapData];
meinePixeldaten[0].r = ...;
// ...

Die Bitmap kann man dann bei Bedarf mit

[meineBitmap drawInRect:meinRect];

in den NSView reinmalen.

Original von blutfink
Optimale Zeichengeschwindigkeit erreicht man hier wohl indem man eine Offscreen-Bitmap

Preisfrage:
Wo liegt der Nachteil bei diesem Ansatz? Schon die weiteren Auswirkungen im (GUI-)Design bedacht?

t.

Original von blutfink
Nee. Das stimmte vor 10 Jahren vielleicht mal auf x86. Heute gilt das jedoch nicht mehr, und auf PowerPC hat das noch nie gegolten.

??? Mac eine Wunderkiste
Ich habe nicht gesagt das es das schnellste ist, was ich auf dem Mac programieren kann, aber wenn ich KEINE Vektoreinheit für die flops benutze, möchte ich mal anzweifeln das ein shift (1 Takt) langsamer ist als eine float Division (ca. 3-6 Takte).
Wenn ich die int Register der AltiVec mitbenutze bin ich (auch heute noch) effizienter da einfach weniger (mindestens Faktor 3) zu rechnen ist.

Fixkomma-Arithmetik ist im Übrigen bei Fraktalen nicht geeignet, weil die auftetenden Wertebereiche so groß sind

Ähhhmm *räusper*:
sizeof(long long) = 8, sizeof(double) = 8 ( auf meinem Rechner )
Wo ist denn da bitte mehr "Genaugkeit"? 8 Byte sind 8 Byte ich kann in beiden Fällen immer gleich viele Zahlen darstellen. Oder hab ich da was nicht kappiert?

Gruß Sascha

Original von blutfink
Das wird jedoch nichts bringen. Das obere dürfte ein fmul, ein fmsub und ein fadd ergeben. Das untere ein fsub, fadd und ein fmadd. Unentschieden.

An sich ein guter Punkt, aber "dürfte"..?

Vielleicht prüfen wir das mal nach:
Wie sieht der Assembler-Output bei folgenden Funktionen aus?



Mit gcc -S -O0 -Wall -W test.c ergibt das:

_funcA:
stmw r30,-8(r1)
stwu r1,-64(r1)
mr r30,r1
stfd f1,32(r30)
stfd f2,40(r30)
lfd f13,32(r30)
lfd f0,40(r30)
fadd f13,f13,f0
lfd f12,32(r30)
lfd f0,40(r30)
fsub f0,f12,f0
fmul f13,f13,f0
fmr f0,f13
fmr f1,f0
lwz r1,0(r1)
lmw r30,-8(r1)
blr

_funcB:
stmw r30,-8(r1)
stwu r1,-64(r1)
mr r30,r1
stfd f1,32(r30)
stfd f2,40(r30)
lfd f13,32(r30)
lfd f0,32(r30)
fmul f13,f13,f0
lfd f12,40(r30)
lfd f0,40(r30)
fmul f0,f12,f0
fsub f13,f13,f0
fmr f0,f13
fmr f1,f0
lwz r1,0(r1)
lmw r30,-8(r1)
blr

Auf die relevanten Unterschiede beschränkt kommt das heraus:

_funcA:
fadd f13,f13,f0
fsub f0,f12,f0
fmul f13,f13,f0
blr

_funcB:
fmul f13,f13,f0
fmul f0,f12,f0
fsub f13,f13,f0
blr

Bei den genauen Instruktionen lagst Du mit Deiner Vermutung etwas daneben, aber bei der Anzahl der Instruktionen herrscht Gleichstand, so wie Du es gesagt hast. Also, Du hast recht und das ganze bringt nichts.
Aber was macht der Compiler mit höherer Optimierungseinstellung?
gcc -S -O2 -Wall -W test.c :

_funcA:
fsub f0,f1,f2
fadd f1,f1,f2
fmul f1,f1,f0
blr

_funcB:
fmul f2,f2,f2
fmsub f1,f1,f1,f2
blr

Huch!? Kein Gleichstand! Funktion B braucht eine Instruktion weniger. Funktion A schneidet schlechter ab. Aber ist das nicht ausgerechnet die Rechenart, die User ponder als die effizientere angepriesen hat? Ups.

ABER.... macht die Einsparung solch einer Instruktion den Kohl fett? Will das jemand nachmessen?

t.