Faktorisierung

[Antigo]

Hi,
Ich habe ein kleines Programm zu Faktorisierung von beliebigen Zahlen geschrieben.

Faktorisierung bedeutet, dass man eine Zahl als ein Produkt von Primzahlen darstellt. Diese Primzahlfaktoren werden aufsteigend asugegeben. Dadurch ist diese Darstellung für jede Zahl eindeutig.

Beispiel:
Zahl 6 ist 2 * 3. DIe Zahlen 2 und 3 sind hier die Primzahlen aus denen sich die Zahl 6 zusammensetzt.

oder
Die Zahl 2145 ist 3 * 5 * 11 * 13.

Kommt ein Faktor zweimal vor, wird er als Exponent dargestellt. 8 ist beispielsweise 2 * 2 * 2. Es wird jedoch als 2^3 ausgegeben.


Alles weitere ist angehangen



edit:
~~~~~~~~~~~~~~~~~~~~~~Update~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~
Dank der Hilfe von vielen DP Mitgliedern, konnte ich das Programm um einiges schneller machen. Zum direkten Vergleich lasse ich das alte Programm auch angehangen.

Was jetzt noch fehlt:
Zum einen ein Statusbalken, der anzeigt, wieweit man in der Berechnung berets fortgeschritten ist. Das hat auf Anhieb nicht hingehauen so wie ich das wollte. Also muss ich mir nochmal Gedanken machen.
Zum anderen gibt es noch zwei drei Bugs die ich noch beheben muss. Die Zahlen 6,9,15,21 werden fälschlicherweise als Primzahl angegeben. Jensseits der 20er Marke scheint jedoch alles zu funktionieren. Notfall werde ich diese Zahlen als Sonderfälle behandeln.

[Antigo]

ok ich bräuchte dann nochmal eure Hilfe.
Und zwar beim Statusbalken.

Ich hab mir folgendes überlegt:
Ich habe zwei Werte:
i -> Variable die alle Werte bis zur Wurzel der zu faktorisierenden Zah durchgeht
a -> Wurzel der zu faktorisierenden Zahl.

Wenn ich jetzt wissen will wieviel Prozent i von a ist. Rechne Ich i/a*100. Da ich mit Integer Werten arbeite rechne ich aber erst i*100 und das Ergebnis davon durch a, was aufs selbe rauskommt.

Mein Code sieht jetzt so aus:

Delphi-Quellcode:

    Nmul(z,i,100);
    Ndiv(z,a);
    Progressbar1.Position:= Nint32(z);
    Application.Processmessages;

Das funktioniert soweit auch sehr gut. Es wird alles richtig angezeigt, nur wenn ich folgende Primzahl teste:
2813418473392999
dann dauert das auf meinem System über 2 Minuten bis das Programm mir anzeigt das es eine Primzahl ist. Während dessen wächst der Statusbalken brav.
Nehme ich jetzt aber den oben geposteten COde raus, braucht das Programm nur noch 4 Sekunden(!).
Das heisst der Code bremst das Programm immens ab. ALso müsste ich ihn seltener ausführen lassen. HAt jemand eine Idee wie ich das bewerkstellige, bzw. am besten bewerkstellige. Ich könnte natürlich alle Variablen global definieren, also aus der eigentlichen Faktorisierungsprozedur rausholen und mit einem Timer alle paar Sekunden den Status abfragen, aber vielleicht gibts da noch eine bessere methode?!


danke schonmal


edit: wobei sich dieser Balken eigentlich sowieso nur bei Primzahlen lohnt, da bei allen anderen Zahlen sowieso vor der Wurzel der Zahl abgebrochen wird, wenn die faktorisierung abgeschlossen ist. Von daher würde der Balken irgendwo bei einem drittel oder so abbrechen, was auch wieder blöd wäre....

[negaH]

rechne

Delphi-Quellcode:

var
  Root,Steps,Counter:
begin
  Root := N^0.5;
  Steps := N / Root / 2 / 100; 
  Counter := Steps;
  repeat
    if Counter <= 0 then 
    begin
      ProgressBar.Position := Root / Prime * 100;
      Counter := Steps;
    end;
    Counter := Counter -1;
  until ....
end;

oder so

Delphi-Quellcode:

var
  Tick: Cardinal;
begin
  Tick := GetTickCount + 250;
  repeat
    if GetTickCount >= Tick then
    begin
      Tick := GetTickCount + 250;
      ProgressBar.Position := Prime / Root * 100;
      ProgressBar.Update;
    end;
  until ...
end;

Im letzten Fall wird die ProgressBar nur 4 mal pro Sekunde = 250ms aktualisiert. Ich würde diese Methode vorziehen da sie die ProgressBar unabhängig vom eigentlichen Programmcode in einem exakten zeitlichen Interval aktualisert.

Ansonsten solltest du mit NIsProbablePrime(N) VOR jeder Trial Divison auf Prim überprüfen (aber nur bei großem N -> NSize(N) > 32).
NIsProbablePrime() soll laut Pomerance (anerkannter Mathematiker) erst bei Zahlen größer 10^1000 eine Falschantwort liefern. Pomerance hat ein Preisgeld ausgesetzt für denjenigen der als erster eine Zahl findet bei dem sein Primzahltest diese Zahl als Primzahl ausweist obwohl es keine ist. Das ist bei Pseudo-Primzahl-Tests immer eine Wahrscheinlichkeit, weshalb es eben nur ein Pseudo-Primzahl-Test ist. Bisher hat noch kein Mensch eine solche Zahl gefunden, Pomerance sitzt also noch auf seinem Preisgeld.


Gruß Hagen

[Antigo]

Deine zweite Methode gefällt mir. Ich werd das mal einbauen, danke

Zitat:

Ansonsten solltest du mit NIsProbablePrime(N) VOR jeder Trial Divison auf Prim überprüfen

Jo das hatte ich auch schon überlegt, aber ich denke mal das lasse ich. Oder ich baue eine Checkbox ein, und nur wenn diese aktiviert ist, wird die Zahl vor dem faktorisieren auf Prim geprüft.

[negaH]

Zitat:

jo das hatte ich auch schon überlegt, aber ich denke mal das lasse ich. Oder ich baue eine Checkbox ein, und nur wenn diese aktiviert ist, wird die Zahl vor dem faktorisieren auf Prim geprüft.

Das ist ansich auch eine gute Idee, da NIsProbablePrime() intern ja selber eine Trial Division bis 2^32 ausführt. Am besten wäre es NIsProbablePrime(N) nur dann aufzurufen wenn N mehr als 64 Bits groß ist -> NSize(N) > 64.

Allerdings wenn du NSPP(N, [1,2]) statt NIsProbablePrime(N) benutzt dann wird intern keine Trial Division mehr durchgeführt, das wäre dann schneller.

In meiner DEMO zum DECMath solltest du dir mal die Unit TestUnit.pas genauer anschauen. Darin dürftest du 3 Funktion finden

Delphi-Quellcode:

function NPollardRho(var D: IInteger; const N: IInteger): Boolean;
function NPollardPM1(var D: IInteger; const N: IInteger; Bound: Cardinal = 0): Boolean;
function NWilliamsPP1(var D: IInteger; const N: IInteger): Boolean;

Das sind alles Faktorizations-Verfahren.

Gruß Hagen

[negaH]

Probiere mal die Zahl 18303891083514198529 == 1919369 * 9536410707641 mit Methode 3 aus.

Gruß Hagen

[Antigo]

Vielen Dank für den Hinweis. Hat etwas gedauert bis ich mich rangesetzt hab, weil ich irgendwie keine Lust hatte den Fehler zu suchen, wenn er bei einer einzigen Zahl vorkommt. Es war aber nur ein Ausgabe Fehler. Das heisst er hat die 2 Faktoren gefunden, aber an einer bestimmten Stelle im Code wurde der Wert prim trotzdem auf true gesetzt, so dass die Meldung ** ist Prim ausgegeben wurde. Ich lade die neue Version gleich hoch.


edit: direkt das nächste Problem: Ich kann den Vorgang bei Methode 3 nicht abbrechen lassen. Ich sage bei jedem Schleifendurchlauf: Application.Processsmessages; genau wie bei Methode 1 und da funktioniert es. Bei Methode 3 kann ich aber nichtmal aufden Button der den Vorgang abbrechen soll klicken, die Anwendung hängt sich einfach auf. Gibts da noch einen Trick für?

[negaH]

Zitat:

Gibts da noch einen Trick für?

Keine Ahnung, ohne die Sourcen zu kennen kann man keine Aussage treffen.

Gruß Hagen

[Antigo]

naja mein Code sieht grob so aus

Delphi-Quellcode:

while (true) {Abfragen} and (not abbruch) do begin

  ...

  ...
  Application.Processmessages;
end;

Mit einem Klick auf Button 2 kann man die Variable abbruch auf true setzen und damit die Schleife abbrechen. Wie gesagt funktioniert das bei Methode 1, bei Methode 2 aus irgendeinem Grund jedoch nicht.

Daher meine Frage: Gibt es noch eine andere Methode die Applikation vor dem "aufhängen" zu bewahren?

[negaH]

ich mache solche dinge immer so

Delphi-Quellcode:

procedure TForm1ButtonClick(Sender: TObject);
var
  Tick: Cardinal;
begin
  if FInAction = 0 then
  try
    Inc(FInAction);
    Button.Caption := 'Abbruch'; 
    Tick := GetTickCount + 100;
    while FInAction = 1 do
    begin
      ...
      if Tick >= GetTickCount then
      begin
        Inc(Tick, 100);
        Application.ProcessMessages;
      end;
    end;
  finally
    FinAction := 0;
    Button.Caption := 'Start';
  end else
  begin
    Inc(FInAction); // ist >= 1, wir setzte FInAction auf > 1, bedeutet Abbrechen
    Button.Caption := 'beende';
  end;
end;

1.) FInAction: Integer wird als Field in deinem TForm deklariert. FInAction kann 3 Staties annehmen
FInAction == 0, bedeutet nichts wird aktuell berechnet und zb. Button hat die Caption == "Start"
FInAction == 1, bedeutet unsere Berechnung läuft, Button.Caption = "Abbrechen"
FinAction >= 2, bedeutet unsere Berechnung soll auf Benutzerwusch hin beendet werden

2.) FInAction macht also die Methode .ButtonClick() vor Rekursionen sicher das diese Methode nicht reentrant sein kann -> weil wir ja Application.ProcessMessages aufrufen

3.) Application.ProcessMessage wird in einem festen Intervall aufgerufen, hier alle 100 Millisekunden. Das macht deine Berechnung weitaus schneller

In deiner TForm1.OnCloseQuery() Methode solltest du nun Abfragen ob FInAction == 0 ist. Wenn ja, dann kannst du das Form schließen lassen, wenn nein dann wird FInAction inkrementiert und OnCloseQuery verhindert das Form zu schließen.

Gruß Hagen
Gruß Hagen

[Hawkeye219]

Ein kleiner Dreher ist drin: beim Vergleich der 'Ticks' müssen die beiden Seiten vertauscht werden:

if GetTickCount >= Tick then Gruß Hawkeye