Fiete hat folgendes geschrieben :

Moin ub60, da die Primfaktoren bekannt sind könnte die Eingangszahl erst mal durch das Produkt aller Faktoren geteilt werden, so ist die Zahl erst mal kleiner. Andere Variante: teile durch Primfaktor^100, wobei 100 eine Abschätzung sei muss. Die Größe der Exponenten musst Du einschätzen, vielleicht gehts auch mit ^1000 Das Ganze sieht nach einer Gödelisierung aus.

Aus dem bisher gesagten, entnehme ich, daß die Exponenten der Primzahlen gesucht werden sollen, diese aber durchaus =0 sein können. Wenn dies der Fall, führt Dein erster Vorschlag i.d.R. zu nix.

Für einen schnellen Überblick, welche Primfaktoren überhaupt vorkommen, kann man mit der gegebenen Zahl N und dem euklidischen Algorithmus sehr schnell x=gcd(N, 997#) ausrechnen (wobei 997# = primorial(997) das Produkt der Primzahlen bis 997 ist) und dann sehen welche Faktoren x enthält (x hat nur maximal 416 Stellen).

So, mein Problem wäre gelöst und ich will nur noch für Interessenten einen kleinen "Abschlussbericht" schreiben.

1. DEC
Ich habe letztendlich das DEC (DECMath) verwendet, da es wahnsinnig schnell ist. Mit DECMath konnte ich eine Zahl mit mehr als 10 Millionen Stellen gut verarbeiten. Mit naiver Division habe ich erst einmal ermittelt, welche Primfaktoren überhaupt vorkommen. Mit naiver Division habe ich außerdem die Exponenten der Primzahlen ermittelt, die nur mit kleineren Exponenten (<100000) vorkamen. An 6 Rechnern parallel war das in einigen Stunden gelöst.

Fiete hat folgendes geschrieben :

Andere Variante: teile durch Primfaktor^100, wobei 100 eine Abschätzung sei muss. Die Größe der Exponenten musst Du einschätzen, vielleicht gehts auch mit ^1000

Natürlich habe ich dann auch durch die gefundenen Potenzen geteilt. Das macht aber größenmäßig wirklich erst bei hohen Exponenten Sinn.
Die restlichen (großen) Exponenten habe ich so ähnlich gelöst, wie Fiete vorgeschlagen hat. Ich habe dabei allerdings so eine Art (manuelle) Intervallschachtelung durchgeführt, so dass es dann doch recht schnell ging. Beim nächsten Mal würde ich diese Intervallschachtelung sicherlich programmieren, das sollte dann höllenschnell sein.
Eine äquivalente Funktion zu mp_val habe ich in DEC leider nicht gefunden, eventuell habe ich es aber auch übersehen.

2. MPArith
MPArith funktionierte auch ganz gut, war aber aus meiner Sicht etwas langsamer als DEC.

3. GMP
Das einzige "Pascalinterface", das ich gefunden hatte, war "GMP for Delphi.zip", das mit irgendeiner höheren Delphi-Version compiliert war. Den Quelltext habe ich leider mit meinem Delphi 7 nicht zum Laufen bekommen. Im Quelltext steht:

Zitat:

This wrapper only supports Delphi versions with operator overloading. For earlier versions please use header file gmp_lib.pas directly.

Das habe ich allerdings noch nicht probiert. Wenn hier jemand einen Quelltextschnipsel hätte, der ohne Änderung mit "kleineren " Delphi-Versionen läuft, wäre ich für einen Tipp sehr dankbar. Ansonsten werde ich wohl mal alleine probieren.

Fiete hat folgendes geschrieben :

Das Ganze sieht nach einer Gödelisierung aus.

Jetzt hat das Kind einen Namen. So etwas war es. Da muss ich wohl im Mathe-Studium gerade krank gewesen sein .


Besten Dank noch mal an alle Ideengeber!

ub60

Die Antworten haben sich gerade überschnitten, deshalb ein Doppelpost.

Gammatester hat folgendes geschrieben :

Für einen schnellen Überblick, welche Primfaktoren überhaupt vorkommen, kann man mit der gegebenen Zahl N und dem euklidischen Algorithmus sehr schnell x=gcd(N, 997#) ausrechnen (wobei 997# = primorial(997) das Produkt der Primzahlen bis 997 ist) und dann sehen welche Faktoren x enthält (x hat nur maximal 416 Stellen).

Auch eine Super-Idee! Leider (oder zum Glück ) habe ich die Zahl mittlerweile faktorisiert.
Trotzdem Klasse, wie viel tolle Ideen hier im Forum gekommen sind!

ub60

ub60 hat folgendes geschrieben :

3. GMP Das einzige "Pascalinterface", das ich gefunden hatte, war "GMP for Delphi.zip", das mit irgendeiner höheren Delphi-Version compiliert war. Den Quelltext habe ich leider mit meinem Delphi 7 nicht zum Laufen bekommen. Im Quelltext steht: Zitat: This wrapper only supports Delphi versions with operator overloading. For earlier versions please use header file gmp_lib.pas directly. Das habe ich allerdings noch nicht probiert. Wenn hier jemand einen Quelltextschnipsel hätte, der ohne Änderung mit "kleineren " Delphi-Versionen läuft, wäre ich für einen Tipp sehr dankbar. Ansonsten werde ich wohl mal alleine probieren.

Also, das ließ mir keine Ruhe, bin ich doch weiterhin auf der Suche nach Pascal-Langzahlenunits für meinen Langzahlentaschenrechner (zu dem ich derzeit nicht komme, mein Sortierkino spannt mich derzeit voll ein....).

Mein erster Fund war: storage.googleapis.c...P%20for%20Delphi.zip

Ist das das Archiv, was Du benutztest, oder ein anderes?

Die dort enthaltene Exe-Datei hat zunächst einmal einen Fehler: Beendet man das Programm, kommt die Fehlermeldung: "An unexpected memory leak has occured. [...]".

Diese Exe hat als Symbol das mir von Turbo-Delphi bekannte (keine Ahnung, ob das in höheren Versionen auch noch benutzt wurde, Delphi 3 und 4 erzeugten ja auch das gleiche), dennoch läßt es sich nicht mit Turbo-Delphi übersetzen. In der Datei gmp_lib.pas die beiden Typen "UInt32" durch "Cardinal" ersetzt, denn etwas anderes kann UInt32 kaum sein, in der Projektdatei die Zeile "Application.MainFormOnTaskbar := True;" entfernt bzw. auskommentiert, und schon läßt sich das auch mit Turbo-Delphi ohne Warnung und nur 5 Hinweisen bezüglich nicht benutzter Variablen (oder Variabeln?) übersetzen. Die erhaltene Exe-Datei ist deutlich kleiner als das beigelegte Original und hat diesen elenden Memory-Leak-Fehler nicht, jedenfalls nicht beim Beeenden.

Ergänzung: Delphi 7 scheitert allerdings mit dem Kompilieren....

2. Ergänzung: UInt32 ist eigentlich ein Longword, aber mit Cardinal klappt es ja auch.

3. Ergänzung: Entferne ich alles, was die Hinweise verursacht, bekomme ich auch mit dem Turbo-Delphi-Compilat diese elenden Memory-Leak-Fehlermeldungen.

4. Ergänzung: Zwei nicht verwendete private Fill-Variablen müssen bleiben, und mit diesen die Hinweise, sonst kommt die besagte elende Fehlermeldung zur Laufzeit. Angehängtes Archiv ist ansonsten für Turbo-Delphi vorbereitet, hat auch das Compilat inneliegend.

Delphi-Laie hat folgendes geschrieben :

Mein erster Fund war: storage.googleapis.c...P%20for%20Delphi.zip Ist das das Archiv, was Du benutztest, oder ein anderes?

Genau das war das einzig Sinnvolle, das ich gefunden habe. Ich hatte auch zuerst die UInt32 mit Cardinal ersetzt, aber dann kamen Unmengen andere Fehler ...

Bei mir funktioniert die beiliegende Exe übrigens ohne Fehlermeldung beim Abschluss. Leider wird (zumindest in der Exe) nur mit gebrochenen Zahlen gerechnet, so dass die Genauigkeit auf der Strecke bleibt (100^20=999999999999999999999999999999999997167). Außerdem wird nach ca. 40 Stellen dicht gemacht (abgeschnitten), und das ohne Hinweis oder Fehlermeldung.

ub60