Tröpfelalgorithmus

Vorstellungen von Programmen, welche mit Lazarus erstellt wurden.
heizkoerper
Beiträge: 24
Registriert: Mo 1. Aug 2011, 14:39
OS, Lazarus, FPC: Windows XP und 7, L 0.9.31, FPC 2.4.4
CPU-Target: 32 und 64 Bit
Wohnort: Hannover
Kontaktdaten:

Tröpfelalgorithmus

Beitrag von heizkoerper »

In Wikipedia ist ein guter Artikel über den sogenannten Tröpfelalgorithmus verfasst.

Für die Eulerzahl e könnte die Programmumsetzung wie folgt aussehen:

Code: Alles auswählen

e:='2.';m:=1;Fak:=1;c[1]:=2;
While Ln(Fak)/Ln(10)<Stellen-1 Do Begin Inc(m);Fak:=Fak*m End;
For i:=2 To m Do c[i]:=1;
For j:=1 To Stellen Do
 Begin
   u:=0;
   For i:=m DownTo 2 Do Begin z:=10*c[i]+u;c[i]:=z Mod i;u:=z Div i End;
   e:=e+Chr(48+u)
 End


Für die Kreiszahl Pi ist die Programmumsetzung etwas umfangreicher:

Code: Alles auswählen

r:='';p:='';m:=10*(Stellen+1) Div 3;
For i:=1 To m Do c[i]:=2;
For j:=0 To Stellen Do
 Begin
  u:=0;
  For i:=m DownTo 2 Do Begin z:=10*c[i]+u;c[i]:=z Mod (i*2-1);u:=z Div (i*2-1)*(i-1) End;
  z:=10*c[1]+u;c[1]:=z Mod 10;u:=z Div 10;
  If u<=8 Then Begin r:=r+p;p:=Chr(48+u) End;
  If u=9 Then p:=p+Chr(48+u);
  If u=10 Then
   Begin
     For i:=1 To Length(p) Do
       Begin
         Val(p[i],z,u);Inc(z);
         If z=10 Then z:=0;
         p[i]:=Chr(48+z)
       End;
     p:=p+'0'
   End
 End;
p:=r[1]+'.'+Copy(r,2,Length(r))+p


Viel Spaß beim Ausprobieren!

Gruß Heizkoerper

siro
Beiträge: 730
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Tröpfelalgorithmus

Beitrag von siro »

Ich hab mir mal den
Euler_01.jpg
Euler_01.jpg (7.6 KiB) 5422 mal betrachtet
angesehen und korrigiert, damit das auch funktioniert: :wink:

Code: Alles auswählen

const Stellen = 100;
 
procedure Test;
var e:string;
    c:Array[0..Stellen] of integer;
    Fak:Double;
    m,z,u,i,j:integer;
begin
  e:='2.';
  m:=1;
  Fak:=1;
  c[1]:=2;
  While Ln(Fak)/Ln(10)<Stellen-1 Do Begin
    Inc(m);
    Fak:=Fak*m;
  End;
  For i:=2 To m Do c[i]:=1;
  For j:=1 To Stellen Do Begin
    u:=0;
    For i:=m DownTo 2 Do Begin
      z:=10*c[i]+u;
      c[i]:=z Mod i;u:=z Div i;
    End;
    e:=e+Chr(48+u);
  end;
  Form1.caption:=e;
end;
 
{ TForm1 }
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  Test;
end;           


im Internet habe ich für e die erste Zahl gefunden, darunter habe ich die Lazarus Berechnung geschrieben:

2,71828 18284 59045 23536 02874 71352 66249 77572
2.71828 18284 59045 23536 02874 71352 66249 77572 47093 69995 95749 66967 62772 40766 30353 54759 45713 82178 52516 64274
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

siro
Beiträge: 730
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Tröpfelalgorithmus

Beitrag von siro »

Nun hat mich das Pi Berechnen auch mal interessiert
und so sieht dann der funktionsfähige Code in Lazarus aus:

Code: Alles auswählen

 
const stellen=100;
 
procedure Test;
var r,p:string;
    m,i,j,u,z:integer;
    c : Array[0..10*(Stellen+1) Div 3] of integer;
begin
  r:='';
  p:='';
  m:=10*(Stellen+1) Div 3;
  For i:=1 To m Do c[i]:=2;
  For j:=0 To Stellen Do Begin
    u:=0;
    For i:=m DownTo 2 Do Begin
      z:=10*c[i]+u;
      c[i]:=z Mod (i*2-1);
      u:=z Div (i*2-1)*(i-1)
    End;
    z:=10*c[1]+u;
    c[1]:=z Mod 10;
    u:=z Div 10;
    If u<=8 Then Begin
      r:=r+p;
      p:=Chr(48+u);
    End;
    If u=9 Then p:=p+Chr(48+u);
    If u=10 Then  Begin
      For i:=1 To Length(p) Do Begin
        Val(p[i],z,u);Inc(z);
        If z=10 Then z:=0;
        p[i]:=Chr(48+z)
      End;
      p:=p+'0';
    End
  End;
  p:=r[1]+'.'+Copy(r,2,Length(r))+p;
  Form1.caption:=p;
end;
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  Test;
end;       


Die erste Zahl gefunden im Internet, die zweite Zahl berechnet mit obigen Code in Lazarus:
3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679
3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

Marc
Lazarusforum e. V.
Beiträge: 208
Registriert: Fr 11. Nov 2016, 14:09
OS, Lazarus, FPC: Linux Mint 20 (WinXP VBox)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Marc »

Danke für die Inspiration.

Ich hab das mal etwas Anfängerfreundlich komplettiert.
Das berechnen von PI ist ja sehr nützlich.

Wenn man sich die Nummer einfach aus dem Internet kopiert verletzt man ja eventuell ein Copyright.
Die Nummer hat sich Apple (oder Google) bestimmt schon patentieren lassen!!

Ausserdem hat man dann was Eigenes. Da weiss man was man hat!
Dateianhänge
PI.tar.gz
(333.79 KiB) 206-mal heruntergeladen
Good code comes from experience, experience comes from bad code.

Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Mathias »

Ich hatte gestern auch noch optimiert. Wieso die Stellen Statisch machen ?
Ich habe eine dynamische Array genommen.

Code: Alles auswählen

var
  stellen: integer;
 
  procedure CalcPi;
  var
    r, p: string;
    m, i, j, u, z: integer;
    c: array of integer;
  begin
    SetLength(c, 10 * (Stellen + 1) div 3 + 1);
......
    p := r[1] + '.' + Copy(r, 2, Length(r)) + p;
    WriteLn(p);
    SetLength(c, 0);
  end;
 
begin
  ClrScr;
  Writeln('Bitte Stellen eingeben: ');
  readln(stellen);
  CalcPi;
end.   

Ich habe es für die Konsole gemacht, aber man könnte dies in Marc Project integrieren. :wink:
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Marc
Lazarusforum e. V.
Beiträge: 208
Registriert: Fr 11. Nov 2016, 14:09
OS, Lazarus, FPC: Linux Mint 20 (WinXP VBox)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Marc »

Hallo Mathias.

Die idee hatte ich auch, aber es mit einer statischen Array natürlich nicht hingekriegt.
Habe ich Deinen Vorschlag gleich mal eingebaut.
Finde es ein schönes kleines Beispiel zu lernen. Jetzt auch noch mit einer richtigen dynamischen Array.

Das als mein Projekt zu bezeichnen ist schon sehr sportlich.
Ich habe das nur etwas 'Noob' kompatibel mit 'klickibunti' versehen.
Was die Routine da macht erschliesst sich mir nicht mal im Ansatz. :-)
Dateianhänge
PI.tar.gz
(127.05 KiB) 204-mal heruntergeladen
Good code comes from experience, experience comes from bad code.

Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Mathias »

Was die Routine da macht erschliesst sich mir nicht mal im Ansatz. :-)

Das geht mir auch so, dies ist sehe hohe Mathematik.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Timm Thaler
Beiträge: 1224
Registriert: So 20. Mär 2016, 22:14
OS, Lazarus, FPC: Win7-64bit Laz1.9.0 FPC3.1.1 für Win, RPi, AVR embedded
CPU-Target: Raspberry Pi 3

Re: Tröpfelalgorithmus

Beitrag von Timm Thaler »

Mathias hat geschrieben:
Was die Routine da macht erschliesst sich mir nicht mal im Ansatz. :-)

Das geht mir auch so, dies ist sehe hohe Mathematik.


Naja nee, ist es eigentlich nicht. Der Wikipedia-Artikel beschreibt es schön. Es wird ausgenutzt, dass sich Pi und e durch Reihenentwicklung darstellen lassen. Das geht für einige Zahlen, für andere wiederum nicht.

Allerdings dürfte der Algo gegenüber anderen Verfahren zur Berechnung von Pi reichlich ineffizient sein. Insofern hat er eher akademischen Wert, denn man wird damit auf dem Heimcomputer nicht annähernd die bisher bekannten Stellen von Pi nachrechnen können. Der einzige Vorteil ist, dass er ohne große Zahlen auskommt, weil er die berechneten Stellen wieder vergißt.

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Tröpfelalgorithmus

Beitrag von wp_xyz »

Hier ein Beispiel für eine höchst ineffektive, aber dafür sehr anschauliche Berechnung von Pi mit Hilfe des Monte-Carlo-Verfahrens: Ein Kreis mit Radius r hat die Fläche r^2 pi, das den Kreis umschreibende Quadrat hat die Fläche 4 r^2. Damit erhält man pi aus dem Verhältnis von Quadrat und Kreis zu pi = 4 * (Kreisfläche/Quadratfläche). Um die Flächen zu ermitteln, werden jeweils zwei gleichverteilte Zufallszahlen bezogen, die einen zufälligen Punkt im Quadrat beschreiben. Der Anteil der Punkte, die auch den Kreis treffen, gibt das Flächenverhältnis an.

Das beigefügte Programm spielt das durch und man kann verfolgen, wie sich allmählich (SEHR langsam) der Wert von pi aufbaut.
Dateianhänge
pi-mc.png
pi-mc.png (14.42 KiB) 5355 mal betrachtet
PI.zip
(5.66 KiB) 210-mal heruntergeladen

Marc
Lazarusforum e. V.
Beiträge: 208
Registriert: Fr 11. Nov 2016, 14:09
OS, Lazarus, FPC: Linux Mint 20 (WinXP VBox)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Marc »

Also für mich als bekennender 'Noob,' und jemanden der intellektuell eher zu Fuss unterwegs ist, ist das höhere Mathematik.
Zusammengefasst, wir Schweizer finden das schwierig. Dem Euler zu Ehren gabs hier sogar mal eine Banknote.
Wir sind wohl leicht zu beeindrucken. :lol:

Code: Alles auswählen

https://en.wikipedia.org/wiki/File:Euler-10_Swiss_Franc_banknote_(front).jpg
Zuletzt geändert von Marc am Do 9. Nov 2017, 23:15, insgesamt 1-mal geändert.
Good code comes from experience, experience comes from bad code.

Mathias
Beiträge: 6162
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Mathias »

Hier ein Beispiel für eine höchst ineffektive, aber dafür sehr anschauliche Berechnung von Pi mit Hilfe des Monte-Carlo-Verfahrens:

Dies habe ich auch gesehen. Mit diesem Verfahren kann man auch anderes berechnen, ausser der Kreisfläche.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Marc
Lazarusforum e. V.
Beiträge: 208
Registriert: Fr 11. Nov 2016, 14:09
OS, Lazarus, FPC: Linux Mint 20 (WinXP VBox)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Tröpfelalgorithmus

Beitrag von Marc »

Das Monte Carlo Verfahren ist Klasse. :-)
Habe ich noch nie gesehen.
Und bereits 'Noob' Kompatibel.
Good code comes from experience, experience comes from bad code.

relocate
Beiträge: 61
Registriert: Di 24. Jan 2012, 11:47
OS, Lazarus, FPC: Win (L- FPC 2.4.4 + 2.6.4)
CPU-Target: 32Bit

Re: Tröpfelalgorithmus

Beitrag von relocate »

Marc hat geschrieben:Also für mich als bekennender 'Noob,' und jemanden der intellektuell eher zu Fuss unterwegs ist, ist das höhere Mathematik.
Zusammengefasst, wir Schweizer finden das schwierig. Dem Euler zu Ehren gabs hier sogar mal eine Banknote.
Wir sind wohl leicht zu beeindrucken. :lol:

Code: Alles auswählen

https://en.wikipedia.org/wiki/File:Euler-10_Swiss_Franc_banknote_(front).jpg


Na ja, die eulersche Zahl ist ja wichtig bei der Zinseszins Berechnung:
https://de.wikipedia.org/wiki/Eulersche ... nsrechnung
Wenn das nicht wichtig für die Schweizer ist, was dann? :D
Würde ich die Dinge so wie alle anderen machen, hätte ich so manche Probleme nicht.

Aber das wäre langweilig.

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Tröpfelalgorithmus

Beitrag von wp_xyz »

Naja, eigentlich braucht man für die Zinseszinsrechnung in der Praxis die e-Funktion gar nicht: Bei einem Zinssatz z% und einem Einlagekapital K hat man nach n Jahren den Betrag K*(1+z/100)^n auf dem Konto.

relocate
Beiträge: 61
Registriert: Di 24. Jan 2012, 11:47
OS, Lazarus, FPC: Win (L- FPC 2.4.4 + 2.6.4)
CPU-Target: 32Bit

Re: Tröpfelalgorithmus

Beitrag von relocate »

wp_xyz hat geschrieben:Naja, eigentlich braucht man für die Zinseszinsrechnung in der Praxis die e-Funktion gar nicht: Bei einem Zinssatz z% und einem Einlagekapital K hat man nach n Jahren den Betrag K*(1+z/100)^n auf dem Konto.


Herrje, nicht mal ein Witz kann man machen, ohne dass er voll des Ernsts kommentiert wird.
Nichtsdestotrotz steht im Wikipedia Artikel der ernsthafte Hintergrund dazu. :?
Würde ich die Dinge so wie alle anderen machen, hätte ich so manche Probleme nicht.

Aber das wäre langweilig.

Antworten