Modulo -Algorithmus: übersetzng von pseudocode

[Sequitar]

Auf der suche nach schnelleren Modulo Berechnungen bin ich auf Folgendes gestoßen:
"Computing Mod Without Mod" (Will, Mark A & Ko,, Ryan)
Die Autoren schlagen beigefügten pseudo-code vor (section 2.4,algorithmus 3), den ich versucht habe in delphi zu übersetzen, leider nur mäßig erfolgreich, wie meine tests belegen

wäre mal einer so nett und könnte das mal checken?

Anbei mein code,
! ich habe für die "einfachen" mathe optionen eine bestehende library, die funktionalität der eingesetzten teile wurde nach bestem wissen erfolgreich getestet

(hierzu lade ich noch ein basis package und die entsprechende dll hoch)

Ansonsten bin ich natürlich auch dankbar für Vorschläge bzgl integer division / modulo verbesserungen

Vielen Dank

[Michael II]

Wieso baust du Algo3 aus 2.4 nach? Die Autoren schlagen doch Algo4 aus 3.1 vor. (This [Algo3] is the main reduction, but some further can be required hence the last two
while loops.)

Baust du den Algo für den Schulunterricht nach? Oder willst du die vorgeschlagene mod Funktion in Delphi Programmen verwenden? Wenn Letzteres: Der Algo ist für den Einbau in Prozessoren gedacht und nicht für die Schicht in welcher Delphi werkelt.

Welchen Teil von Algo3 aus 2.4 kannst du nicht umsetzen/verstehst du nicht?

[Andreas13]

Hallo Sequitar,
wenn Du den Modulo-Algorithmus nicht als „programmiertechnische Herausforderung“ suchst, sondern in Deinen Delphi-Programmen z. B. für kryptographische Zwecke etc. eine Modulo-Funktion mit hoher Genauigkeit (z. B. 2048 Bits und meeeeeeehr) brauchst, dann könntest Du die Multipräzisions-Bibliotheken von unserem leider viel zu früh verstorbenen Gammatester (Wolfgang Ehrhardt) benutzen. Zu finden sind sie auf dem Web-Archiv unter:
http://web.archive.org/web/*/wolfgang-ehrhardt.de
Gruß, Andreas

[himitsu]

Oder mal ins DEC (Delphi Encryption Compendium) schauen, das ist ja sauschnell, also enthält es auch ein schnelles Modulo. :stupid:

Und natürlich auch nochmal im DECMath.

[Sequitar]

Hallo und vielen Dank für eure tips (! insb, wenn der vorgeschlagene Algorithmus nur in prozessoren werkeln soll, ist das definitiv ein falscher ansatz von mir)

Derzeit würde ich das dingen für größenordnungen um die 500bt (aufgrund der aktuellen hardware nicht die standardmäßigen 2048bt) anwenden wollen, insb für hash checks, angedacht war ursprunglich auch mal ein key-austausch, aber das projekt hab ich auf eis gelegt, und werde da wohl auf eine standard lib umsteigen,falls mein aktueller prozessor das zulässt (i5-u mobile version)

ich glaub' von Dir, himitsu, hatte ich vor langer, langer zeit mal eine math unit erhalten, auf deren basis ich seitdem immer mal wieder erweitert hab'. Merci dafür noch mal, hat mir seinerzeit gute Dienste erwiesen und ist auch gut nachvollziehbar. Derzeit stelle ich das für die - noch limitierten Anwendungsbereiche (s.o, und derzeit im rahmen diverser Präsentationsszwecke für schüler, @Michael II) auf byte-arrays um, von daher war der gedanke, bei der division vielleicht nebenbei etwas effizienteres einzubauen

Habt Ihr evtl passende alternativ-algortithmen (also jetzt nur für die division) in peto? Als referenz würde wohl reichen, nachbauen würde ich dann ggf selber.

Merci
schönen abend!

[himitsu]

Wobei meine paar MathLibs und der Taschenrechner mehr Proof-of-Concept waren.
Schauen was möglich ist, von den Schnittstellen her, aber nicht wirklich auf Effizienz ausgelegt. :oops:

DECMath war/ist praktisch eine der schnellsten Libs im kostenlosen Bereich (Ein-Mann-Projekt).
Problem dort war, dass der Quellcode nicht öffentlich ist/war und demnach es mit neuen Delphi-Versionen Probleme gibt, so lange nicht jemand dafür das Compilat (DCU's) bereitstellt.
Aber es gibt mehrere BigMathLibs, wovon welche auch auf Cryptographie spezialisiert sind.

[TurboMagic]

Hagen, der ursprüngliche Entwickler der DEC hat von dem Teil leider nie den Quellcode rausgegeben. Die DCUs in DEC 5.2 sind für D7 also steinalt. Habe es daher im 6.0 Entwicklungszweig rausgenommen.

Wie sieht die Lizenzsituation bei W. Regards Code aus? Könnte das jemand problemfrei bei GitHub oder so einstellen?

[himitsu]

Regards?


Part I gibt es als Pascal, glaub ich, aber Part II ........
Joar, dann wäre für DEC-Math wohl die einzige Möglichkeit das mit Delphi 7 / C++Builder 7 zu versuchen in eine .OBJ zu kompilieren und das dann wie ZLib/Jpeg/PNG/RegEx ins Delphi zu ziehen.
(ich glaub hab seit 4 Jahren nichts mehr von ihm gehört)

[TurboMagic]

Verflixte Autokorrektur auf'm Tablet.
Meinte W. Erhardt.

Ich fänd's gut wenn man das in irgend ein Open SOurce Repository
(oder mehrere falls es unterschiedliche Themen sind) überführen könnte.
Würde die Sichtbarkeit erhöhen, die Nützlichkeit steigern und evtl.
käme dann auch noch die eine oder andere kleine Verbesserung dazu.

[himitsu]

Er ist ja letzten Jahres verstorben.
https://www.delphipraxis.net/200202-...mmatester.html

Ich denke mal es wäre OK, wenn man es dort hin transferiert, dazumal die Webseite ja von 'nem Spammer/Grabber übernommen und misshandelt wurde.

Zitat:

Wolfgang hat seinen Code mit einer sehr freigiebigen Lizenz ausgestattet, so dass niemand Probleme haben sollte, den Code in seinen Projekten zu verwenden.

So als Idee, vielleicht könnte man es ins DEC integrieren, bzw. daneben legen.
Hagen Reddmann wird wohl noch leben, aber er hat seine Verschlüsselungs-Bibliothek abgegeben.