Laufzeitoptimierung eines Consolen-Programms

[stpolster]

Hallo,
auf dem Forum "Matheplanet" läuft gerade eine Art Wettbewerb, bei dem es um möglichst schnelle Berechnung von langen Zahlen geht. Die Berechnung hat eigentlich wenig Sinn, es geht nur um Geschwindigkeit.
25 Millionen mal werden zwei lange Zahlen multipliziert, dann unter eine Grenze reduziert und das Ergebnis mit 2^128 div und mod geteilt.
Nachdem ich mit Delphi 5 im Vergleich zu anderen Programmiersprachen nicht ganz so gut war, habe ich es jetzt auf Console umgestellt und es wurde etwas schneller. Es nutzt die Langzahlroutinen von Wolfgang Ehrhardt.

Delphi-Quellcode:

program matheplanet_projekt2;
{$APPTYPE CONSOLE}
uses SysUtils,
  mp_base, mp_types;

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

begin
  Writeln('hyperG-Problem');
  Writeln;
  mp_init6(a, b, soll, sub, produkt, filter);
  nad:=0;
  nsu:=0;
  mp_read_decimal_astr(a,'170141183460469231731687303715884105757');
  mp_read_decimal_astr(b,'170141183460469231731687303715884105703');
  mp_read_decimal_astr(soll,'57896044618658097711785492504343953926634992332820282019728792003956564819968');
  mp_read_decimal_astr(sub,'11111111111111111111111111111111111111111111111111111111111111111111111111111');
  mp_read_decimal_astr(filter,'340282366920938463463374607431768211455');
  time1 := now;
  for nn:=1 to 25000000 do begin
     mp_mul(a,b,produkt);
     while mp_cmp_mag(produkt,soll)<0 do begin
      mp_add(produkt,sub,produkt);
      inc(nad);
     end;
     repeat
      mp_sub(produkt,sub,produkt);
      inc(nsu);
     until mp_cmp_mag(soll,produkt)>0;
     mp_shr(produkt,128,a);
     mp_and(produkt,filter,b);
    end;
  Writeln(FormatDateTime('SS:ZZZ', now - Time1));
  Writeln(mp_adecimal(produkt));
  Writeln(nad);
  Writeln(nsu);
  Writeln;
  Writeln('Programmende mit ENTER');
  mp_clear6(a, b, soll, sub, produkt, filter);
  readln;
end.

Das Ergebnis ist

13:325
47306219819553867530681020915755484915944251665601 642944764215683054098939729
83884810
25000000

Da ich gern die "Ehre von Delphi" verteidigen würde, suche ich noch nach Ideen zur Beschleunigung. Bei mir läuft die Routine in etwa 13,3 Sekunden durch.
In der ZIP-Datei sind auch die nötigen Quelltexte von Wolfgang Erhardts Routinen.

Danke für evtl. Ideen
Steffen

[himitsu]

Schau auch mal nach dem DEC Math vom Delphi Encryption Compendium.

Im Forum und inzwischen auf GitHub sollte sich das finden lassen.


[ADD]
Ich glaub das war im Part II drin, oder einzeln.
Beim Michael lag nur Part I rum. http://backups.geheimniswelten.de/ww.../DEC/index.htm

[stpolster]

Danke.
Sehe ich mir an.

[Andreas13]

Hallo Steffen,
wenn ich Deinen Code mit XE5 kompiliere, dann brauche ich auf meinem PC knapp 7,4 Sekunden, während Dein Original matheplanet_projekt_console.exe von https://matheplanet.de/index.php etwa 9,4 Sekunden benötigt. Das ist leider nur ca. 21 % schneller.

Die Benutzung der neuesten (= letzten) Dateien von Wolfgang Ehrhardt vom November 2018 und das Hinzufügen der Zeile Winapi.MMSystem.timeBeginPeriod(1); bringen lediglich noch eine weitere 1/10 Sekunde. Mein bestes Ergebnis war 7,28 Sekunden. Weitere Optimierungsmöglichkeiten in Deinem Code habe ich noch nicht entdeckt.
In den extrem konzentrierten Code von Wolfgang Ehrhardt reinzupfuschen halte ich für ziemlich gefährlich...

Summa summarum: Ein noch neuerer Compiler könnte eventuell einen weiteren Geschwindigkeitsvorteil bringen.

[Andreas13]

Mit Lazarus (FreePascal 3.2.2) kompiliert braucht es knapp 16 Sekunden...

[stpolster]

Vielen Dank für den Test und die deutlich kleineren Zeiten.
Ich hatte es mit dem vor Jahren freien RAD Studio 10 versucht. Da kamen zumindest bei mir schlechtere Zeiten heraus.
In Wolfgang Ehrhardts Code etwas zu ändern, würde mir nicht in den Sinn kommen.

Ist es möglich, mir die EXE zu senden ?

Danke Steffen