Laufzeitoptimierung eines Consolen-Programms

[Andreas13]

Rust kenne ich zwar auch nicht, aber aus dem Quellcode geht hervor, daß es für die Berechnung einen "eingebauten" Datentype U256 verwendet, also einen vorzeichenlosen 256-Bit-Integer, der für die Hardware optimiert zu sein scheint.

Wolfgang Ehrhardt's mp_int hat dagegen eine variable Länge und daher einen größeren Overhead.

Ich habe versucht lebenswichtige Überprüfungen wie mp_not_init(..), mp_error<>MP_OKAY und MPC_ArgCheck zu deaktivieren: Es hat bei 64-Bit lediglich 0,3 Sekunden gebracht.

[Andreas13]

Ich finde, daß die Aufgabenstellung & der Geschwindigkeitswettbewerb von https://matheplanet.de/index.php etwas unfair ist, denn der Wertebereich von U256 umfaßt genau 77 Stellen. Und der Sollwert mp_read_decimal_astr(soll,'57896044618658097711785492504343953926634992332820282019728792003956564819968'); hat genau 77 Ziffern.

Würde man die Zahlen lediglich um einige Stellen verlängern, wären solche Programmiersprachen, die maximal U256 bieten, von vornherein aus dem Rennen. Hingegen kann Wolfgang Ehrhardt's mp_int bis mehrere Millionen Stellen & mehr mithalten.

[himitsu]

Die MatheLib von Hagen war hochoptimiert, zwar in mehr Bezug auf Kryptographie.
Für das Projekt eines Einzelnen, waren seine Funktionen in vielen Belangen auf einem hohen Niveau, verglichen mit anderen Produkten großer Anbieter weltweit.
Und da dort auch mit festen Größen gerechnet wird ....



Ich glaube mich zu erinnern, dass entweder DEC-Math und/oder eine andere Mathe-Lib, die mal hier in der DP genannt wurde, auch einen festen Integer-Typen dieser Größe hatte, neben dem dynamischen Typen.

In dem Rust, sind die Constanten sub und damit auch ten doch auch irgendwie nutzlos?



Wisst ihr, was pervers total bescheuert wäre?
Diese Aufgabe auf die wohl unoptimierteste MatheLib loszulassen.
https://www.delphipraxis.net/135569-...athelib-_.html

Erstmal hatte sich SmartScreen bei der Demo geweigert, aber dann
2 ^ 255 = 57.896.044.618.658.097.711.785.492.504.343.953.926 .634.992.332.820.282.019.728.792.003.956.564.819.9 68
die ersten 77 Stellen nach nur 4,5 Millisekunden





Es gibt/gab doch auch Sprachen, welche speziell für mathematische Berechnungen optimiert wurden?
Die müssten hier doch enorm im Vorteil sein.

Delphi TurboPascal Pascal wurde ja ursprünglich mehr als Lehrsprache entwickelt und seit Delphi/Borland mehr in Richtung Datenbanken und GUI.

[freimatz]

Zitat von himitsu:

Es gibt/gab doch auch Sprachen, welche speziell für mathematische Berechnungen optimiert wurden?

FORTRAN

Zitat von himitsu:

Delphi TurboPascal wurde ja ursprünglich mehr als Leersprache entwickelt und seit Delphi/Borland mehr in Richtung Datenbanken und GUI.

Delphi TurboPascal

[himitsu]

Zum Glück hattest'e das doppelte ee nicht auch noch entdeckt.


Also irgendwie rechnet das Rust doch was total Anderes?

Code:

while &c < &soll {
  c += &#8834;

Delphi-Quellcode:

while c < soll do begin
  c := c + sub;  // c := c + Power(ten, 77) div 9;

[Uwe Raabe]

Zitat von Andreas13:

Wolfgang Ehrhardt's mp_int hat dagegen eine variable Länge und daher einen größeren Overhead.

Dazu sagt Wikipedia:

Zitat:

Arbitrary precision is used in applications where the speed of arithmetic is not a limiting factor, or where precise results with very large numbers are required.

Zitat von Andreas13:

Würde man die Zahlen lediglich um einige Stellen verlängern, wären solche Programmiersprachen, die maximal U256 bieten, von vornherein aus dem Rennen. Hingegen kann Wolfgang Ehrhardt's mp_int bis mehrere Millionen Stellen & mehr mithalten.

Bei Benchmarks ist es aber allgemein so, dass Performance vor Flexibilität geht - ansonsten bräuchte man keinen Benchmark. Da geht es insbesondere auch nicht um schönen oder wartbaren Code, wobei ich persönlich den Code in einer Lösung mit Rudy's BigNumbers auch schöner finde - ist halt auch wieder langsamer.

Delphi-Quellcode:

program matheplanet_projekt3;
{$APPTYPE CONSOLE}
uses
  System.SysUtils,
  Velthuis.BigIntegers;

var
  a, b, soll, sub, produkt, filter: BigInteger;
  Time1: TDateTime;
  nn, nad, nsu: integer;

begin
  Writeln('hyperG-Problem');
  Writeln;
  nad:=0;
  nsu:=0;
  a := BigInteger.Parse('170141183460469231731687303715884105757');
  b := BigInteger.Parse('170141183460469231731687303715884105703');
  soll := BigInteger.Parse('57896044618658097711785492504343953926634992332820282019728792003956564819968');
  sub := BigInteger.Parse('11111111111111111111111111111111111111111111111111111111111111111111111111111');
  filter := BigInteger.Parse('340282366920938463463374607431768211455');
  time1 := now;
  for nn:=1 to 25000000 do begin
    produkt := a*b;
    while produkt < soll do begin
      produkt := produkt + sub;
      inc(nad);
    end;
    repeat
      produkt := produkt - sub;
      inc(nsu);
    until produkt < soll;
    a := produkt shr 128;
    b := produkt and filter;
  end;
  Writeln(FormatDateTime('SS:ZZZ', now - Time1));
  Writeln(produkt.ToString);
  Writeln(nad);
  Writeln(nsu);
  Writeln;
  Writeln('Programmende mit ENTER');
  readln;
end.

[himitsu]

Hier geht es auch ausschließlich um + , - , shr , and und Größer-/Kleinervergleiche, also um das Einfachste, was geht und wo man praktisch algorithmisch nichts optimieren kann.

Leider kann meine Lib kein binäres AND und SHR, bzw. nicht direkt, da sie durchweg dezimal arbeitet, hat sie Probleme mit 2er-Potenzen, die in ein 10er System nicht rein passen.
Es wäre alles besser, hätten wir 4 Finger, inkl. Daumen.

SHR kann ich ja noch durch eine extrem unoptimale Division ersetzen, aber beim AND müsste ich dann auch in jedem Durchlauf das dreifach umrechnen.

Delphi-Quellcode:

uses
  System.SysUtils, Winapi.Windows, System.Diagnostics,
  StringMatheLib in 'stringmathelib_131\StringMatheLib.pas',
  StringMatheRec in 'stringmathelib_131\StringMatheRec.pas';

begin
  try
    {const}var ten: MatheString := 10;
    {const}var two: MatheString := 2;

    var soll := Power(two, 255);
    var z := Power(two, 128) - 1;
    var sub := Power(ten, 77) div 9;

    var a := Power(two, 127) + 29;
    var b := Power(two, 127) - 25;
    var c := MatheString(0);

    var nad := 64;
    var nsu := 64;

    var watch := TStopwatch.StartNew;

    for var nn := 0 to 25000000 do begin
      c := a * b;
      while c < soll do begin
        c := c + sub;
        Inc(nad);
      end;
      while c > soll do begin
        c := c - sub;
        Inc(nsu);
      end;
      a := c div '340282366920938463463374607431768211456'; //a := c shr 128;
      b := c and z;
    end;
    var duration := watch.Elapsed.TotalSeconds;
    WriteLn('c0', string(c));
    WriteLn('ad=', nad, ' su=', nsu, ' in ', duration:1:8, ' sec');
  except
    on E: Exception do
      WriteLn(E.ClassName, ': ', E.Message);
  end;
end.

[Andreas13]

Zitat von Uwe Raabe:

Zitat von Andreas13:

Wolfgang Ehrhardt's mp_int hat dagegen eine variable Länge und daher einen größeren Overhead.

Dazu sagt Wikipedia:

Zitat:

Arbitrary precision is used in applications where the speed of arithmetic is not a limiting factor, or where precise results with very large numbers are required.

Bei Benchmarks ist es aber allgemein so, dass Performance vor Flexibilität geht - ansonsten bräuchte man keinen Benchmark.[/DELPHI]

Ja, das ist korrekt, Uwe. Die Ausschreibung auf https://matheplanet.de/index.php habe ich erst jetzt gelesen:

Zitat:

...Mich interessierte nun, wie sich der 256 Bit Bereich schlägt.(YMP Code?)
...
Randbedingungen
...
b) Nutzung des gesamten 256 Bit Bereiches bei mul, add & sub, damit nicht abgekürzt werden kann (wenn Zwischenergebnis in den 128 oder 64 Bit Bereich sinkt)...
...

Damit hätte man mit einer MPA-Lösung erst gar nicht antreten sollen: Der Wettbewerb war für Motorräder und nicht für Fahrradfahrer vorgesehen.

[stpolster]

Zitat von Andreas13:

Damit hätte man mit einer MPA-Lösung erst gar nicht antreten sollen: Der Wettbewerb war für Motorräder und nicht für Fahrradfahrer vorgesehen.

Aber das Fahrrad ist ein High-Tech-Rad mit einem sehr leistungsstarken Zusatzmotor.
Delphi + Wolfgang Erhardts Routinen schlagen sich so schlecht nicht.

Da ich nur wenig Ahnung habe, habe ich die Anfangsbedingungen natürlich nicht richtig verstanden. Ist nun mal so.

[Andreas13]

Nein, ganz im Gegenteil: Wolfgang Erhardts Routinen schlagen sich sehr gut!
Wir haben eine erneute Bestätigung, daß die MPA-Routinen & Delphi korrekt rechnen (wir sind im "Ziel angekommen" und wurden "nicht disqualifiziert"). Aber wir sind nicht in unserer Gewichtsklasse, sondern weit darüber angetreten, und haben trotzdem gut abgeschnitten: Das erzielte Ergebnis läßt sich also sehen!