Punkte gleichverteilen

19.12.2020, 23:24

ChRed

Auf diesen Beitrag antworten »

Punkte gleichverteilen

Meine Frage:
Hi,
Es geht bei der Aufgabe um ein Computerprogramm. Es sollen punkte gleichmäßig
auf einer Kreisfläche verteilt werden. Gegeben habe ich die üblichen gleichverteilten Zufallszahlen von 0 bis 1. Die Punkte am Kreisrand kommen häufiger vor. Aber ich weiß nicht wie ich das machen soll

Meine Ideen:
Mein Idee ist,dass sich 2 Wahrscheinlichkeiten irgendwie überlagern
Zunächst werden Zufallszahlen erzeugt z=R*rand. Dann noch ein Winkel w=360*rand und dann z noch so verändern dass r zum Kreisrand hin häufiger vorkommt
Vielleicht kann mir da jemand weiterhelfen

19.12.2020, 23:40

Dopap

Auf diesen Beitrag antworten »

RE: Punkte gleichverteilen

Zitat:

Die Punkte am Kreisrand kommen häufiger vor. Aber ich weiß nicht wie ich das machen soll

Was ist damit konkret gemeint oder ist das egal?

Apropos: Punkte $\begin{eqnarray*} (R\cdot rand,2\pi \cdot rand ) \end{eqnarray*}$ sind in der Fläche nicht gleichverteilt.

------------------

Was Simples: Punkte $\begin{eqnarray*} (rand,rand) \end{eqnarray*}$ sind Einheitsquadrat gleichverteilt. Wiederholen bis der Abstand zum Mittelpunkt $\begin{eqnarray*} \leq 1/2 \end{eqnarray*}$ ist. Das ist dann ein Kreispunkt.
Der "Abfall" an Punkten hält sich in Grenzen.
Zur zunehmenden Flächendichte vom Mittelpunkt aus fällt mir gerade nichts passendes ein.

20.12.2020, 08:52

HAL 9000

Auf diesen Beitrag antworten »

Reden wir mal o.B.d.A. von der Einheitskreisfläche, d.h., $\begin{eqnarray*} x^2+y^2\leq 1 \end{eqnarray*}$ .

Eine ziemlich simple Variante ist die nach Verwerfungsmethode:

1. Würfle aus $\begin{eqnarray*} x,y \end{eqnarray*}$ stetig gleichverteilt auf $\begin{eqnarray*} [-1,1] \end{eqnarray*}$ .
2. Überprüfe $\begin{eqnarray*} x^2+y^2\leq 1 \end{eqnarray*}$ . Falls ja, bist du fertig - falls nein, gehe wieder zu 1).

Die Anzahl Schleifen, die du auf diese Weise drehen musst, ist Geometrisch verteilt mit Parameter $\begin{eqnarray*} \frac{\pi}{4} \end{eqnarray*}$ , man benötigt daher im Mittel $\begin{eqnarray*} \frac{4}{\pi}\approx 1.27 \end{eqnarray*}$ Versuche, bis es klappt.

Zitat:

Original von Dopap
Apropos: Punkte $\begin{eqnarray*} (R\cdot rand,2\pi \cdot rand ) \end{eqnarray*}$ sind in der Fläche nicht gleichverteilt.

Sehr richtig. Lässt sich übrigens mit $\begin{eqnarray*} (R\cdot \sqrt{rand},2\pi \cdot rand) \end{eqnarray*}$ reparieren, um mal in dieser Syntax zu bleiben.

20.12.2020, 11:28

Dopap

Auf diesen Beitrag antworten »

... weil durch die Umkehrfunktion bedingt die lineare Dichte quadratisch zunimmt.

wenn jetzt, durch eine Umkehrfunktion bedingte lineare Dichte ( Radius ) noch stärker zunehmen würde, dann würde doch die Flächendichte am Rand zunehmen... oder?

20.12.2020, 14:40

HAL 9000

Auf diesen Beitrag antworten »

OK, begründen wir das völlig seriös mit dem Transformationssatz (nebenbei fällt dabei auch die Unabhängigkeit von Radius und Winkel mit ab):

Sei $\begin{eqnarray*} (X,Y) \end{eqnarray*}$ ein stetig gleichverteilter Zufallsvektor auf der Einheitskreisfläche, und $\begin{eqnarray*} (R,W) \end{eqnarray*}$ dessen Polarkoordinaten. Dann gilt

$\begin{eqnarray*} X &=& R\cos(W)\\ Y &=& R\sin(W) \end{eqnarray*}$

und der Transformationssatz liefert die Dichte $\begin{eqnarray*} f_{R,W}(r,w) = \left|\det(J)\right|\cdot f_{X,Y}\left(r\cos(w),r\sin(w)\right) \end{eqnarray*}$ mit Jacobi-Matrix

$\begin{eqnarray*} J = \begin{pmatrix} \cos(w) & \sin(w)\\ -r\sin(w) & r\cos(w)\end{pmatrix} \end{eqnarray*}$ .

Es folgt damit $\begin{eqnarray*} \det(J)=r \end{eqnarray*}$ , außerdem gilt für $\begin{eqnarray*} 0\leq r\leq 1 \end{eqnarray*}$ gemäß der vorausgesetzten Kreisflächen-Gleichverteilung $\begin{eqnarray*} f_{X,Y}\left(r\cos(w),r\sin(w)\right)=\frac{1}{\pi} \end{eqnarray*}$ . Insgesamt bekommt man damit

$\begin{eqnarray*} f_{R,W}(r,w) = \frac{r}{\pi} \end{eqnarray*}$ für $\begin{eqnarray*} 0\leq r\leq 1 \end{eqnarray*}$ und $\begin{eqnarray*} 0\leq w\leq 2\pi \end{eqnarray*}$ .

Offensichtlich sind die Randverteilungen davon $\begin{eqnarray*} f_R(r) = 2r \end{eqnarray*}$ und $\begin{eqnarray*} f_W(w) = \frac{1}{2\pi} \end{eqnarray*}$ mit dann $\begin{eqnarray*} f_{R,W}(r,w) = f_R(r) \cdot f_W(w) \end{eqnarray*}$ :

Letzteres bedeutet Unabhängigkeit von $\begin{eqnarray*} R \end{eqnarray*}$ und $\begin{eqnarray*} W \end{eqnarray*}$ . Die Verteilung von $\begin{eqnarray*} W \end{eqnarray*}$ ist die Gleichverteilung auf $\begin{eqnarray*} [0,2\pi] \end{eqnarray*}$ , und aus der $\begin{eqnarray*} R \end{eqnarray*}$ -Dichte folgt für $\begin{eqnarray*} 0\leq r\leq 1 \end{eqnarray*}$ die $\begin{eqnarray*} R \end{eqnarray*}$ -Verteilungsfunktion $\begin{eqnarray*} P(R\leq r) = F_R(r) = r^2 \end{eqnarray*}$ . Gemäß Inversionsmethode kann man $\begin{eqnarray*} R \end{eqnarray*}$ somit durch $\begin{eqnarray*} F_R^{-1}(rand) \end{eqnarray*}$ simulieren.

P.S.: Ich würde dennoch die Verwerfungsmethode propagieren, die ist i.d.R. weniger rechenaufwändig. Eine leichte Adaption des obigen Algorithmus macht daraus übrigens die Polarmethode zur Erzeugung zweier standardnormalverteilter Zufallszahlen:

1. Würfle aus $\begin{eqnarray*} x,y \end{eqnarray*}$ stetig gleichverteilt auf $\begin{eqnarray*} [-1,1] \end{eqnarray*}$ .
2. Berechne $\begin{eqnarray*} t=x^2+y^2 \end{eqnarray*}$ und überprüfe $\begin{eqnarray*} t\leq 1 \end{eqnarray*}$ . Falls ja, gehe zu 3. - falls nein, gehe wieder zu 1).
3. Berechne $\begin{eqnarray*} r = \sqrt{-\frac{2\ln(t)}{t}} \end{eqnarray*}$ und damit $\begin{eqnarray*} n_x=r\cdot x \end{eqnarray*}$ sowie $\begin{eqnarray*} n_y= r\cdot y \end{eqnarray*}$ .

20.12.2020, 22:55

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
[...]
Sehr richtig. Lässt sich übrigens mit $\begin{eqnarray*} (R\cdot \sqrt{rand},2\pi \cdot rand) \end{eqnarray*}$ reparieren, um mal in dieser Syntax zu bleiben.

Für den Schulbereich habe ich mal beispielhaft
$\begin{eqnarray*} (\text{R}\cdot \sqrt[5] {rand}\,,\, 2\pi \cdot rand) \end{eqnarray*}$ in Polarkoordinaten probiert. Sieht gut aus.

Anzeige

20.12.2020, 23:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Sieht gut aus.

Solange es nur um "gutes Aussehen" statt um Gleichverteilung geht, ist das Ok. smile

smile

21.12.2020, 06:27

Dopap

Auf diesen Beitrag antworten »

Verstehe ich nicht so ganz.

Mit $\begin{eqnarray*} (\rm R\cdot \sqrt{rand}, 2\pi \cdot rand)_{polar} \end{eqnarray*}$ entsteht ein flächenmäßig gleichverteilter Kreis, mit
zum Beispiel $\begin{eqnarray*} (\rm R\cdot \sqrt{\sqrt{rand}}, 2\pi \cdot rand)_{polar} \end{eqnarray*}$

ein im Winkel gleichverteilter, zum Rand hin dichter werdender Kreis, also das von CHRed Gewünschte.

In der Simulation entsteht das Bild einer schattierten Kugel.

21.12.2020, 08:26

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ChRed
Es sollen punkte gleichmäßig auf einer Kreisfläche verteilt werden. [...] Die Punkte am Kreisrand kommen häufiger vor.

Das sind zwei sich widersprechende Aussagen. Ich hab mich an die erste gehalten - du dich womöglich an die zweite.

21.12.2020, 09:11

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Letzteres bedeutet Unabhängigkeit von $\begin{eqnarray*} R \end{eqnarray*}$ und $\begin{eqnarray*} W \end{eqnarray*}$ . Die Verteilung von $\begin{eqnarray*} W \end{eqnarray*}$ ist die Gleichverteilung auf $\begin{eqnarray*} [0,2\pi] \end{eqnarray*}$ , und aus der $\begin{eqnarray*} R \end{eqnarray*}$ -Dichte folgt für $\begin{eqnarray*} 0\leq r\leq 1 \end{eqnarray*}$ die $\begin{eqnarray*} R \end{eqnarray*}$ -Verteilungsfunktion $\begin{eqnarray*} P(R\leq r) = F_R(r) = r^2 \end{eqnarray*}$ . Gemäß Inversionsmethode kann man $\begin{eqnarray*} R \end{eqnarray*}$ somit durch $\begin{eqnarray*} F_R^{-1}(rand) \end{eqnarray*}$ simulieren.

Freude

Sehr nützlich HAL ! Das habe ich auch gleich umgesetzt. Dazu habe ich die Ververfungunsmethode zur Generierung von 10000 im Einheitskreis gleichverteilten roten Punkten benutzt. Die 10000 blauen ebenso gleichverteilten Punkt habe ich erzeugt, indem ich mir in $\begin{eqnarray*} w=2\pi\cdot \text{rand} \end{eqnarray*}$ gleichvetreilte Winkel erzeugt habe und jeweils mit $\begin{eqnarray*} r=\sqrt{\text{rand}} \end{eqnarray*}$ einen Zufallsradus dazu erzeugt habe.
[attach]52311[/attach]

Zum Vergleich dazu habe ich noch mal geschaut, was passiert, wenn man die Radien über $\begin{eqnarray*} r = \text{rand} \end{eqnarray*}$ erzeugt. Man erkennt hier deutlich, daß die blauen Punkte nicht mehr gleichverteilt sind.
[attach]52310[/attach]

Zitat:

P.S.: Ich würde dennoch die Verwerfungsmethode propagieren, die ist i.d.R. weniger rechenaufwändig. Eine leichte Adaption des obigen Algorithmus macht daraus übrigens die Polarmethode zur Erzeugung zweier standardnormalverteilter Zufallszahlen:

1. Würfle aus $\begin{eqnarray*} x,y \end{eqnarray*}$ stetig gleichverteilt auf $\begin{eqnarray*} [-1,1] \end{eqnarray*}$ .
2. Berechne $\begin{eqnarray*} t=x^2+y^2 \end{eqnarray*}$ und überprüfe $\begin{eqnarray*} t\leq 1 \end{eqnarray*}$ . Falls ja, gehe zu 3. - falls nein, gehe wieder zu 1).
3. Berechne $\begin{eqnarray*} r = \sqrt{-\frac{2\ln(t)}{t}} \end{eqnarray*}$ und damit $\begin{eqnarray*} n_x=r\cdot x \end{eqnarray*}$ sowie $\begin{eqnarray*} n_y= r\cdot y \end{eqnarray*}$ .

Was das hier für einen Sinn haben soll, erschließt sich mir nicht. Man schließt hier viele Zufallszahlen aus und hat zudem noch den Nachteil, daß viele Radien > 1 erzeugt werden. Außerdem ist mir nicht klar, was $\begin{eqnarray*} n_x \end{eqnarray*}$ und $\begin{eqnarray*} n_y \end{eqnarray*}$ bedeuten sollen.

21.12.2020, 10:39

Leopold

Auf diesen Beitrag antworten »

@ Ulrich

Hast du mal geschaut, welches Verfahren von der Komplexität her für deine Bilder aufwendiger ist? Ich meine das im Sinne der Zeit, die der Rechner braucht, bis das Bild fertig ist. Bei der kartesischen Methode verliert man Zeit durch die Berechnung überflüssiger Punkte, die man dann verwerfen muss, wofür man die Wurzelfunktion einsetzen muss. Auf der anderen Seite muß man bei der Polarkoordinatenvariante schließlich zum Zeichnen Sinus und Cosinus verwenden, die wohl auch zeitaufwendiger für den Rechner sind. Das würde mich interessieren, beim konkreten Experiment am Rechner, nicht als theoretische Berechnung.

21.12.2020, 13:34

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Hallo Leopold,

unter Matlab wird die meiste Zeit dafür gebraucht, Zufallszahlen einzeln zu erzeugen oder einzelne Punkte in eine Grafik einzutragen. Meine erste Implementierung benötigte deshalb 15 Sek. Ausführungszeit. Meine zweite Implementierung braucht dagegen nur noch etwa 50 ms. Da werden alle benötigten Zufallszahlen vorab erzeugt und in eine Matrix eingetragen. Anschließend wird die Grafik in einem Rutsch gezeichnet.
Zum Generieren von 10000 zufälligen (x,y)-Punkten benötigt Matlab 0,5 ms (am Stück mit sin, cos) oder ca. 15 ms mit Verwerfung von ungeeigneten Zufallszahlen.
Alle hier gemachten Zeitangaben schwanken mit einem Sigma von etwa 15 % bei der Messung.

21.12.2020, 14:02

Leopold

Auf diesen Beitrag antworten »

Danke für die Informationen. Dann wäre also die Polarkoordinatenmethode vom Zeitaufwand her günstiger. Da schlägt wohl im andern Fall das Erzeugen überflüssiger Zufallszahlen mit HALs 127 % zu Buche. Mich überrascht, daß die Geschwister Sinus und Cosinus scheinbar keine Rolle spielen. Offenbar gibt es da inzwischen schnelle Algorithmen.

21.12.2020, 15:28

Ulrich Ruhnau

Auf diesen Beitrag antworten »

@Leopold
sin und cos sind im Hauptprozessor intern fest implementiert. Pseudo-Zufallszahlen werden dagegen mit Algorithmen außerhalb des Prozessors generiert, was vermutlich länger dauert.

21.12.2020, 15:49

Leopold

Auf diesen Beitrag antworten »

Interessehalber frage ich einmal weiter nach Sinus und Cosinus im Hauptprozessor. Läuft da ein Algorithmus zur Berechnung dieser Werte ab oder sind die Werte in genügender Feinheit fest in einer Matrix vorberechnet und werden dann Zwischenwerte auf geeignete Art interpoliert? Wegen der Symmetrien genügen ja eigentlich Werte für eine der Funktionen im Intervall $\begin{align*} \left[ 0 , \frac{\pi}{2} \right] \end{align*}$ , bei Heranziehung geeigneter Funktionalgleichungen wohl noch weniger.

21.12.2020, 17:22

HAL 9000

Auf diesen Beitrag antworten »

Ok, hab mal ein bisschen diese Gleichverteilung auf der Einheitskreisscheibe simuliert:

i7-4790K 4GHz, Single-Thread, implementiert in C++ (MS Visual Studio 2017 64Bit)
Zufallszahlengenerator: 64Bit-Integer generiert durch MT 19937 skaliert auf [0,1].

Simuliert wurden jeweils $\begin{eqnarray*} 10^8 \end{eqnarray*}$ Punkte.

Über Polarkoordinaten (also Methode Dopap/Ruhnau): 3.6s
Über Verwerfungsmethode: 2.3s

Ok, ist nicht revolutionär schneller, aber signifikant.

==================================================

Nun das gleiche mit der zweidimensionalen Standardnormalverteilung:

Über Box-Muller (auch mit Sin/Cos): 4.3s
Über Polarmethode: 3.5s

Zitat:

Original von Leopold
Bei der kartesischen Methode verliert man Zeit durch die Berechnung überflüssiger Punkte, die man dann verwerfen muss, wofür man die Wurzelfunktion einsetzen muss.

Letzteres muss man nicht: Um festzustellen, dass $\begin{eqnarray*} (x,y) \end{eqnarray*}$ im Einheitskreis liegt, muss man nur $\begin{eqnarray*} x^2+y^2<1 \end{eqnarray*}$ testen. Da stattdessen $\begin{eqnarray*} \sqrt{x^2+y^2}<1 \end{eqnarray*}$ zu rechnen ist schon Zeitverschwendung.

Zitat:

Original von Ulrich Ruhnau
sin und cos sind im Hauptprozessor intern fest implementiert.

Da bist du aber in den 1990er Jahren stehen geblieben - das war beim x87-Koprozessor so. Aber erstens wird das auf leidlich modernen Intel-Architekturen (SSE/AVX) eher nur noch selten genutzt, und selbst wenn, dauert dort die Berechnung sehr, sehr viele Takte. Da können SSE/AVX-optimierte Software-Bibliotheken durchaus in der Performance mithalten.

21.12.2020, 18:43

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von ChRed
Es sollen punkte gleichmäßig* auf einer Kreisfläche verteilt werden. [...] Die Punkte am Kreisrand kommen häufiger** vor.

(*) das habe ich als isotrop bezüglich Drehung gesehen
(**) als steigende Dichte ungefähr wie beim Pizzaboden

@Ulrich Ruhnau: noch ein Bild in einer Farbe mit z.B. $\begin{eqnarray*} \big(\sqrt[5]{rand}\, , \, 2\pi \cdot rand\big)_{\rm polar} \end{eqnarray*}$
und der Fragesteller hätte die Auswahl für sein "Lieblingsbild" Augenzwinkern

Augenzwinkern

21.12.2020, 21:38

HAL 9000

Auf diesen Beitrag antworten »

Eine Nachfrage hätte ich noch:

Zitat:

Original von Ulrich Ruhnau
Zum Generieren von 10000 zufälligen (x,y)-Punkten benötigt Matlab 0,5 ms (am Stück mit sin, cos) oder ca. 15 ms mit Verwerfung von ungeeigneten Zufallszahlen.

Ist das so zu verstehen, dass bei dir die Verwerfungsmethode um sage und schreibe den Faktor 30 (!) langsamer läuft als die SinCos-Methode??? Und das, obwohl im Mittel nur 1.27-mal so viele Zufallsgrößen benötigt werden und die übrige Rechnung leichter (und damit schneller) sein sollte? Wie ist dir denn das "gelungen" ? Erstaunt1

Erstaunt1

21.12.2020, 23:54

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ist das so zu verstehen, dass bei dir die Verwerfungsmethode um sage und schreibe den Faktor 30 (!) langsamer läuft als die SinCos-Methode??? Und das, obwohl im Mittel nur 1.27-mal so viele Zufallsgrößen benötigt werden und die übrige Rechnung leichter (und damit schneller) sein sollte? Wie ist dir denn das "gelungen" ? Erstaunt1

Erstaunt1

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

function [] = zu1(n)
%Gleichverteilung im Kreis erzeugen
%n = Anzahl der Zufallspunkte im Kreis
tic
z = ones(n,2);
w = linspace(0,2*pi,1001);
xr = cos(w);                            % Kreislinie berechnen
yr = sin(w);
for k=1:n                              % Zufallszahlen mit Verwerfungsmehtode generieren
    while z(k,:)*z(k,:)' >= 1
        z(k,:) = 2*rand(1,2)-1;
    end
end
f = rand(n,2);                          % sin-cos-Methode
r = sqrt(f(:,1));
w = 2*pi*f(:,2);
x = r.*cos(w);
y = r.*sin(w);
figure(2)
plot(xr,yr,'k-',z(:,1),z(:,2),'r.',x,y,'b.')
axis equal
title('r = sqrt(rand)')
toc
end

Die Zeilen 9 - 13 brauchen aus Gründen, die ich nicht verstehe, eben mehr Zeit als die Zeilen 14 - 18. Da C++ sicherlich viel schneller ist als Matlab, würde ich sagen, was HAL festgestellt hat, relativiert meine Spekulation von eben. Das C++ hat aber auch einen Nachteil. HAL konnte nicht ohne weiteres ein Diagramm posten, daß die Homogenität der Verteilung belegt.

21.12.2020, 23:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ulrich Ruhnau
HAL konnte nicht ohne weiteres ein Diagramm posten, daß die Homogenität der Verteilung belegt.

Unwürdige, fadenscheinige Ausrede. Es war überhaupt nicht meine Absicht, ein Diagramm hier zu posten - weil das NICHT das geringste mit dem Problem der Zufallszahlenerzeugung zu tun hat. Finger2

Finger2

22.12.2020, 00:42

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
(**) als steigende Dichte ungefähr wie beim Pizzaboden

@Ulrich Ruhnau: noch ein Bild in einer Farbe mit z.B. $\begin{eqnarray*} \big(\sqrt[5]{rand}\, , \, 2\pi \cdot rand\big)_{\rm polar} \end{eqnarray*}$
und der Fragesteller hätte die Auswahl für sein "Lieblingsbild" Augenzwinkern

Augenzwinkern

Der Fragesteller möchte eine homogene Verteilung. Diese wird mit $\begin{eqnarray*} r=\sqrt[5]{\text{rand}} \end{eqnarray*}$ nicht erreicht, wie sich an diesem Bild zeigen läßt.
[attach]52313[/attach]

22.12.2020, 02:45

Dopap

Auf diesen Beitrag antworten »

Sehr schönes Bild gemäß meiner Interpretation! Freude

Freude

22.12.2020, 03:53

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Und wo ist der Fragesteller? Er könnte sich doch mal melden und sagen, ob er zufrieden ist. fröhlich

fröhlich

22.12.2020, 08:47

HAL 9000

Auf diesen Beitrag antworten »

Der fürchterliche Performanceeinbruch bei U.Ruhnaus Implementierung der Verwerfungsmethode hängt wohl damit zusammen, dass Matlab eine Interpretersprache ist:

Solange man mit Vektoren arbeiten kann, fällt das nicht weiter auf, da die internen Bibliotheksroutinen hochoptimiert sind. So berechnen Zeilen wie "xr = cos(w)" die 100000 Kosinuswerte schnell in einem Rutsch.

Fällt man allerdings auf Einzelwertberechnung via Schleife zurück - wie das in den Zeilen 9-13 geschieht - dann wird es rechenzeitmäßig desaströs. Für einen FAIREN Vergleich wäre es daher geboten, auch die Verwerfungsmethode zu "vektorisieren": Falls dies innerhalb Matlab nicht gelingt, dann eben durch Schreiben eines Moduls (was vlt. dann auch wieder auf C/C++ hinausläuft).

22.12.2020, 09:40

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Für einen FAIREN Vergleich wäre es daher geboten, auch die Verwerfungsmethode zu "vektorisieren": Falls dies innerhalb Matlab nicht gelingt, dann eben durch Schreiben eines Moduls (was vlt. dann auch wieder auf C/C++ hinausläuft).

Gegen die Vekorisierung der Verwerfungsmethode spricht aber, daß man nie genau weiß, wieviele Schleifendurchläufe man benötigt. Wenn man damit zufrieden wäre im Mittel 10000 Zufallspunkte zu generieren, wäre eine Vektorisierung der Verwerfungsmethode aber möglich. Man müßte nur mit einer parallelisierten Suchanweisung (Matlabfunktion find) ungeeignete Zufallswerte entfernen. Das könnte aber vielleicht wiederum länger dauern.

Andererseits könnte man Matlab mit C++ verbinden (Matlabfunktion mex). Das ist aus meiner Sicht aufwendig und nicht mal ebenso gemacht, für wenige ms nicht der Mühe wert.

22.12.2020, 10:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ulrich Ruhnau
Gegen die Vekorisierung der Verwerfungsmethode spricht aber, daß man nie genau weiß, wieviele Schleifendurchläufe man benötigt.

Na und? Dafür hat man doch den Vergleich. Die anderen Vektorroutinen laufen doch intern auch mit einer Schleife ab, ggfs. vielleicht noch unter Nutzung paralleler Threads. Hier ist innerhalb noch eine kleine While-Schleife, die eben im Mittel 1.27 Durchläufe hat. Klar, wird natürlich auf einer externe Routine hinauslaufen.

Zitat:

Original von Ulrich Ruhnau
für wenige ms nicht der Mühe wert.

Es gibt auch Simulationen, wo man sich nicht mit 10000 Werten begnügt: Nicht alle solche Rechnungen sind nur dafür da "schöne Bilder" zu fabrizieren.

22.12.2020, 12:03

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Es gibt auch Simulationen, wo man sich nicht mit 10000 Werten begnügt: Nicht alle solche Rechnungen sind nur dafür da "schöne Bilder" zu fabrizieren.

Es gibt mehrere Möglichkeiten die Rechengeschwindigkeit anwachsen zu lassen. C++ zu benutzen ist schon ein guter Anfang. Ferner könnte man mithilfe von Intel Performance Primitives die Rechengeschwindigkeit um einen Faktor 4 oder vielleicht mit Multithreading um Faktor 16 steigern. Alternativ könnte ich auch das Multitheadingmodell meiner PC-Gaming-Grafikkarte bemühen, indem ich mit meiner Cuda-Software die 1152 GPUs meiner GeForce GTX 1060 3GB beschäftige. Bei meinen Versuchen glaube ich festgestellt zu haben, daß ich so einen Faktor 35 in der Ausführungsgeschwindigkeit gegenüber einem Single-Threaded C++ Programm erziele. Mit der Mex-Funktion von Matlab könnte ich diese gesteigerte Rechenpower noch mit Matlab verbinden.

Ich frage mich dann: Wo möchte ich hin? Lohnt sich der Aufwand? Es ist ja schön, um bestimmte Techniken Bescheid zu wissen. Interessiere ich mich mehr für Mathematik oder für Computertechnik?

Ich schwärme lieber von Rechenverfahren, auf die noch nie ein Mensch gekommen ist. Der Rechner ist nur ein Kontrollwerkzeug, das mir sagt, wo ich recht habe und wo ich falsch liege.

Mich interessiert z.B. ob man das Runge-Kutta-Verfahren genauso verbessern kann wie die Gauß-Integration die Simpsonregel verbessert.
Oder mich interessiert, ob man nichtlineare Optimierungen durch globale Linearisierungsverfahren auf lineare Probleme zurückführen kann.

Der Computer ist mein Rechenknecht, nicht umgekehrt ! Teufel

Teufel

22.12.2020, 16:19

ChRed

Auf diesen Beitrag antworten »

Hi
Gesucht war x=R*sqr(rand).
Dass die Punkte am Kreisrand häufiger vorkommen damit meinte ich dass die Dichtefunktion ansteigen muss.
was bei x=rand ja nicht so ist.
Besten Dank und viele Grüße

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »