Primfaktorzerlegung optimieren

Allesquarks · Beiträge: 510 Win XP Prof Delphi 7 E

Dann haben wir doch die Vorteile beider Methoden verbunden. Ich werd jetzt wohl aufhören. Ansonsten gabs noch einen x-Seiten langen Thread zur Primzahlfunktion. Da gibt es vielleicht noch weitergehende Anregungen.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

Allesquarks hat folgendes geschrieben:

Dann haben wir doch die Vorteile beider Methoden verbunden. Ich werd jetzt wohl aufhören. Ansonsten gabs noch einen x-Seiten langen Thread zur Primzahlfunktion. Da gibt es vielleicht noch weitergehende Anregungen.

Ja beide Vorteile verbunden :beer:

Den Thread hab ich mir schon Teils angesehen, kann ich vielleicht noch die IsPrimzahl-Funktion optimieren.

Danke nochmal!!

greetz

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

BenBE · Verfasst: So 20.11.05 23:52

Da geht sicherlich noch was:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

function PrimFaktorZerlegung (Zahl: Int64): String;    
var
    Root: Integer;
begin    
    Result := '';    

    While Zahl and 1 = 0 do
    Begin
       Result := Result + IntToStr(2) + ' * ';    
       Zahl := Zahl shr 1;    
    end;    

    if zahl >= 2 then 
    Begin
        Root := Trunc(SQRT(Zahl));
        Teiler := 3;

        while Teiler <= Root do 
        begin    
            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
            end;
            Root := Trunc(SQRT(Zahl));
            Inc(Teiler, 2);    
        end;
    end;

    //dann jetzt aber doch 
    if zahl <> 1 then
    begin
        Raise Exception.Create('Kann nicht sein!!!');
    end;
    Delete(Result, Length(Result) - 2, 3);    
end;

Ungetestet, ob er wirklich schneller ist ... Müsste aber ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

BenBE hat folgendes geschrieben:

Da geht sicherlich noch was:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

function PrimFaktorZerlegung (Zahl: Int64): String;    
var
    Root: Integer;
begin    
    Result := '';    

    While Zahl and 1 = 0 do
    Begin
       Result := Result + IntToStr(2) + ' * ';    
       Zahl := Zahl shr 1;    
    end;    

    if zahl >= 2 then 
    Begin
        Root := Trunc(SQRT(Zahl));
        Teiler := 3;

        while Teiler <= Root do 
        begin    
            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
            end;
            Root := Trunc(SQRT(Zahl));
            Inc(Teiler, 2);    
        end;
    end;

    //dann jetzt aber doch 
    if zahl <> 1 then
    begin
        Raise Exception.Create('Kann nicht sein!!!');
    end;
    Delete(Result, Length(Result) - 2, 3);    
end;

Ungetestet, ob er wirklich schneller ist ... Müsste aber ...

Also Root darf nicht Integer sein, sondern Int64.
Aber der Code ist auch nicht schneller.. ca 300 Sekunden und dann die Meldung: Kann nicht sein!! bei der Zahl 9223372036854775806 :lol:

Dann noch was: Ich könnte doch auch die Überprüfung auf Primzahl nach dem durch 2 teilen weglassen.. manchmal sinnvoll, manchmal auch nicht.

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

Allesquarks · Beiträge: 510 Win XP Prof Delphi 7 E

Zitat:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

//dann jetzt aber doch   
    if zahl <> 1 then  
    begin  
        Raise Exception.Create('Kann nicht sein!!!');  
    end;

Das geht glaube ich gerade schon. Primzahlen werden dadurch erkannt, dass ein Teiler größer als SQRT(Zahl) nicht möglich ist. Dann wird die While Schleife aber abgebrochen und nicht div ausgeführt, weshalb der letzte Primfaktor in Zahl stehen kann.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

Außer

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

While Zahl and 1 = 0 do
    Begin
       Result := Result + IntToStr(2) + ' * ';    
       Zahl := Zahl shr 1;    
    end;

sehe ich dort keinen unterschied (ausgenommen Raise Exceprion das aber falsch war

)

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

BenBE · Verfasst: Mo 21.11.05 01:51

Jup. Stimmt, hab's auch noch gesehen ... Hab aber nochmal ein wenig optimiert:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:

function PrimFaktorZerlegung (Zahl: Int64): String;    
var
    Root: DWORD;
    Teiler : Int64;
begin    
    Result := '';    

    While Zahl and 1 = 0 do
    Begin
       Result := Result + IntToStr(2) + ' * ';    
       Zahl := Zahl shr 1;    
    end;    

    if zahl >= 2 then 
    Begin
        Teiler := 3;

        Root := Trunc(SQRT(1.0 * Zahl));
        
        while Zahl mod Teiler = 0 do 
        begin    
            Result := Result + IntToStr(Teiler) + ' * ';
            Zahl := Zahl div Teiler;
        end;
        Root := Trunc(SQRT(1.0 * Zahl));
        Inc(Teiler, 2);    

        while Teiler <= Root do 
        begin    
            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
            end;
            Root := Trunc(SQRT(1.0 * Zahl));
            Inc(Teiler, 2);    

            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
            end;
            Root := Trunc(SQRT(1.0 * Zahl));
            Inc(Teiler, 4);    
        end;
    end;

    //dann jetzt aber doch 
    if zahl <> 1 then
        Result := Result + IntToStr(Zahl) + ' * ';

    Delete(Result, Length(Result) - 2, 3);    
end;

Liefert bei Mir Ergebnisse in ~163 Sekunden. Was dann damit schneller wäre.

@Root: Maximal DWord, da Sqrt(2^63) = 2^31 * Sqrt(2) < 2^32 --> DWORD. Aber stimmt, müsste man eigentlich.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

alzaimar · Verfasst: Mo 21.11.05 09:14

Hab mir nicht Alles durchgelesen, aber wäre ein Primzahlentest des Teilers mit negaH's IsPrime-Kanone nicht noch schneller? Der Code ist hier irgendwo im Forum.

_________________
Na denn, dann. Bis dann, denn.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

BenBE hat folgendes geschrieben:

Jup. Stimmt, hab's auch noch gesehen ... Hab aber nochmal ein wenig optimiert:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:

function PrimFaktorZerlegung (Zahl: Int64): String;    
var
    Root: DWORD;
    Teiler : Int64;
begin    
    Result := '';    

    While Zahl and 1 = 0 do
    Begin
       Result := Result + IntToStr(2) + ' * ';    
       Zahl := Zahl shr 1;    
    end;    

    if zahl >= 2 then 
    Begin
        Teiler := 3;

        Root := Trunc(SQRT(1.0 * Zahl));
        
        while Zahl mod Teiler = 0 do 
        begin    
            Result := Result + IntToStr(Teiler) + ' * ';
            Zahl := Zahl div Teiler;
        end;
        Root := Trunc(SQRT(1.0 * Zahl));
        Inc(Teiler, 2);   

        while Teiler <= Root do 
        begin    
            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
            end;
            Root := Trunc(SQRT(1.0 * Zahl));
            Inc(Teiler, 2);    

            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
            end;
            Root := Trunc(SQRT(1.0 * Zahl));
            Inc(Teiler, 4);    
        end;
    end;

    //dann jetzt aber doch 
    if zahl <> 1 then
        Result := Result + IntToStr(Zahl) + ' * ';

    Delete(Result, Length(Result) - 2, 3);    
end;

Liefert bei Mir Ergebnisse in ~163 Sekunden. Was dann damit schneller wäre.

@Root: Maximal DWord, da Sqrt(2^63) = 2^31 * Sqrt(2) < 2^32 --> DWORD. Aber stimmt, müsste man eigentlich.

Ok damit brauch ich jetzt nur noch 140Sekunden.. Noch ein paar fragen dazu:
Warum nicht gleich while Teiler <= Trunc(Sqrt(1.0 Zahl))?
Warum shr und While Zahl and 1 = 0?
Warum reicht es, die Zahl immer im 2 und dann um 4 zu erhöhen?

greetz

EDIT: Ich hab da mal was gehighlighted wovon ich glaube das es doppelt ist..
EDIT2: Ok hab den Sinn erkannt :oops:

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

alzaimar · Verfasst: Mo 21.11.05 12:15

Born-to-Frag hat folgendes geschrieben:

Warum reicht es, die Zahl immer im 2 und dann um 4 zu erhöhen?

Weil alle Primzahlen P > 3 von der Form P = 6n+/-1 (n = natürliche Zahl) sind. Warum weiss ich nicht. Ist aber so. Damit reicht es, auf diese Zahlenreihe zu testen: 2,3, 5,7, 11,13, 17,19 ...

_________________
Na denn, dann. Bis dann, denn.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

Ok ich hatte das irgendwo schon mal gelesen ( hatte ich oben ja auch schon mal erwähnt

) aber war mir nicht ganz sicher.

EDIT: Ich hab mal etwas anderes an BenBes version gehighlighted, was wirklich Doppelt ist

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

alzaimar hat folgendes geschrieben:

Hab mir nicht Alles durchgelesen, aber wäre ein Primzahlentest des Teilers mit negaH's IsPrime-Kanone nicht noch schneller? Der Code ist hier irgendwo im Forum.

Könntest du mir mal den Link geben?

EDIT: @Alzaimar: Ich habe hier grad einen Lustigen Post von dir in der Delphi-Praxis gelesen: www.delphipraxis.net...c63109,0,asc,15.html, in dem du behauptest, dass 4294967294000017 eine Primzahl ist, was sie aber garnicht ist: 657413 * 6533134109 .. Da stimmt irgendetwas mit deinem Algo net

. Und bei mir hat der Test 200ms gedauert oO

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

Horst_H · Verfasst: Mo 21.11.05 13:34

Hallo,

warum weiss ich aber ;-)

.
Das ist wheel sieving.
Man kann eine Abfolge von Zahlendifferenzen bestimmen, sodass die entstehenden Zahlen immer Teilerfremd zu bestimmten Zahlen sind, am besten aufsteigende Primzahlen.
Die Anzahl der Elemente bis sich alles wiederholt (Perioden Laenge) ist Produkt(p(i)-1)
Zahlengerade:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

                       1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 
             2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
          1 +1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
mod 2     1   +2| +2  +2  +2  +2  +2  +2  +2  +2  +2  +2  +2  +2  +2  +2  +2            : Anzahl 1(2-1)
mod 3     1       +4  +2|     +4  +2      +4  +2      +4  +2      +4  +2      +4        : Anzahl 2(2-1)*(3-1)
mod 5     1           +6  +2  +4  +2      +4  +2      +4          +6  +2|           +6  : Anzahl 8(2-1)*(3-1)*(5-1)

Das laesst sich beliebig steigern. So hat jemand, der die Differenzen aufeinanderfolgender Primzahlen untersuchte zum Abspeichern das Rad bis 23 genommen, das verdichtet die Primzahlen als Bitfeld um
Produkt (pi-1)/pi (i=1..9,pi = (2,3,5,7,11,13,17,19,23)) aber lohnt nicht so recht.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:

const
  BIS           = 5;
  MAXIMUM       =100000000;
  Prim          :array [0..9] of byte = (2,3,5,7,11,13,17,19,23,29);
  {MAXANZAHL     =  2*3*5*7*11*13*17*19;*PRIM}
  MAXANZAHL     :array [0..8] of Longint =(2,6,30,210,2310,30030,
                                         510510,9699690,223092870);
  {WIFEMAXLAENGE =  1*2*4*6*10*12*16*18;*PRIM-1}
  WIFEMAXLAENGE :array [0..8] of longint =(1,2,8,48,480,5760,
                                         92160,1658880,36495360);
 {Anzahl der wirklichen PrimZahlen im Wiederholungsfeld}
  PRIMANZAHL    :array[0..8] of longint  =(1,3,12,48,345,3250,
                                         42333, 646029,12283531);
{ Die maximale Differenz die im Wiederholungsfeld  vorkommt}
  MAXMULLAENGE  = 22; {array [0..9] of byte= (2,4,6,10,14,22,26,34,40,50); 40,50 geraten}
                   {Auf  Mod 32 = 0 bringen}
  MAXSUCHE      = (((MAXIMUM div 231)*48-1)shr 5+1)shl 5; {MAXIMUM*WFEMAXLAENGE[BIS]/MAXANZAHl[BIS]}
                  {div2, div3,*4div15,*24div105,*48div231,*3072div17017...}
type
  toffset       = record
                     Sum,
                     Offs :longint;
                  end;
  tMulFeld    = array [2..MAXMULLAENGE] of tOffset;
  tZahlenFeld = array [0..{MAXANZAHL[BIS]-1}30030] of LongWOrd  ;
  tDiffFeld   = array [0..{WIFEMAXLAENGE[BIS]}5760-1] of byte;

  (* Zahlen feld als Bit array *)
  tSuchFeld   = array [0..MAXSUCHE shr 5+1] of set of 0..31;
var 
  ...
Begin
   WiFeLaenge := 1;
   MaxZahl := 2;
   DiffFeld[0] := 2;
   {Das Rad aufbauen}

for loop := 1 to bis do
   begin

   Diff := DiffFeld[0];
   Suchprim := Diff+1;

{   PrimFeld[Anzahl] := Suchprim;}
   inc(Anzahl);
   Write('>',MaxZahl:10,SuchPrim:10,'<');

   MaxZahl := MaxZahl*SuchPrim;
   WiFeLng_1 := WiFeLaenge-1;

  {Hintereinander Schreiben des neuen WiederholungsFeldes}
  {Dabei wird das WiederholungsFeld insgesamt SuchPrim div 2}
  {hintereinander geschrieben }
   offset := WiFeLAenge;
   for  i := 1 to Suchprim shr 1 do
   Begin
      move(DiffFeld[0],DiffFeld[Offset],WiFeLaenge*SizeOf(DiffFeld[0]));
      inc(offset,WiFeLaenge);
   end;{For i}

   {Vielfache heraustrennen}

   {Berechnen der Vielfachen}

   Summe := 1;
   j := WiFeLaenge shr 1;
   {Aber mindestens einer, der ist aber immer 1*Suchprim}
   If j <> 0 then dec(j);
   {Die Berechnung der Vielfachen}
   {Diese werden in dem DiffFeld von ober nach unten abgespeichert,}
   {da dieser Platz momentan nicht genutzt wird}
   For i := 0 to j do
   begin
      Zahlen[i] := Summe*SuchPrim;
      inc(Summe,DiffFeld[i]);
   end;
   Zahlen[j+1] := 0;

   {Die Vielfachen jetzt finden}
   Summe := 1;
   MulPos := 0;
   I := 0;
   J := 0;
  {Diff wird als Platzhalter der Vielfachen von Suchprim benutzt}
   Diff := Suchprim;
   {Bis zu welcher Summe gesucht werden muss}
   k := MaxZahl shr 1;
   while Summe < k do
   Begin
      inc(Summe,DiffFeld[i]);
      DiffFeld[j]:= DiffFeld[i];
      If Summe=Diff then
      Begin
         {Den naechsten Vielfachen hervorkramen}
         inc(MulPos);
         Diff := Zahlen[MulPos];
         {Den Vielfachen jetzt heraustrennen}
         inc(i);
         {Die neue Differenz eintrageen}
         inc(DiffFeld[j],DiffFeld[i]);
         {Die Summe korrigeren}
         inc(Summe,DiffFeld[i])
      end; {If}
      inc(i);
      inc(j);
   end; {WHILE}
   {Die neue Wiederholungsfeldlaenge}
   WiFelaenge := WiFeLaenge*(Suchprim-1);
   {Spiegeln}
   k :=  WiFelaenge shr 1-1;
   WiFeLng_1 := WiFeLaenge-2;
   For i := 0 to k do
      DiffFeld[WiFeLng_1-i] := DiffFeld[i];
   {Das letzte Feld ist immer 2}
   DiffFeld[WiFeLaenge-1] := 2;
end; {For Loop}

Damit koennte man sich zum Beispiel das Differenzenfeld aufbauen und zyklisch abarbeiten.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

TestZahl := EingabeZahl;
n=1;
Index := 0;
Grenze := trunc(Sqrt(TestZahl));
repeat
n := n+ diffFeld[Index];
IF TestZahl Mod n = 0 then
  begin
  Exp := 1;
  TestZahl := TestZahl div n; 
  while TestZahl mod n = 0 do
    begin
    inc(Exp);
    TestZahl := TestZahl div n; 
    end;
  write('*',n);
  If exp >1 then
    write('^',Exp);
  end;
inc(index);
If Index >=WIFEMAXLAENGE[BIS] then
   Index :=0;
until n > Grenze;

Alles Kokolores.
Zur schnellen Bestimmung mittels einfacher Division nehme man ein Primzahlsiebprogramm und dort wo gezaehlt wird einfach den Test auf teilbarkeit ohne Rest ausfuehren.

Es ist Unsinn vorher jeden Teiler auf prim zu testen, da das immer laenger als eine Division dauert.

Gruss Horst

Moderiert von Christian S.: Delphi-Tag repariert

BenBE · Verfasst: Mo 21.11.05 14:47

Noch ein paar Optimierungen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:

function PrimFaktorZerlegung (Zahl: Int64): String;    
var
    Root: Integer;
    Teiler : Int64;
begin    
    Result := '';    

    While Zahl and 1 = 0 do
    Begin
       Result := Result + '2 * ';    
       Zahl := Zahl shr 1;    
    end;    

    if zahl >= 2 then 
    Begin
        while Zahl mod 3 = 0 do 
        begin    
            Result := Result + '3 * ';
            Zahl := Zahl div 3;
        end;

        Root := Trunc(SQRT(1.0 * Zahl));
        Teiler := 5;

        while Teiler <= Root do 
        begin    
            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
                Root := Trunc(SQRT(1.0 * Zahl));
            end;
            Inc(Teiler, 2);    

            while Zahl mod Teiler = 0 do 
            begin    
                Result := Result + IntToStr(Teiler) + ' * ';
                Zahl := Zahl div Teiler;
                Root := Trunc(SQRT(1.0 * Zahl));
            end;
            Inc(Teiler, 4);    
        end;
    end;

    //dann jetzt aber doch 
    if zahl <> 1 then
        Result := Result + IntToStr(Zahl) + ' * ';

    Delete(Result, Length(Result) - 2, 3);    
end;

Bringt nochmal ~7 Sekunden.

Born-to-Frag hat folgendes geschrieben:

Ok damit brauch ich jetzt nur noch 140Sekunden..

Bei solchen Messungen sind immer CPU-Geschwindigkeit und CPU-Typ interessant. Bei mir AMD XP 1600+ bei 1,4GHz...
Womit misst Du deine Zeiten?

Born-to-Frag hat folgendes geschrieben:

Noch ein paar fragen dazu:
Warum nicht gleich while Teiler <= Trunc(Sqrt(1.0 Zahl))?

Hab ich daher ausgelagert, da sich dieser Wert (Bei mir Root) nur selten Ändert, aber lange zum Berechnen brauch.

Born-to-Frag hat folgendes geschrieben:

Warum shr und While Zahl and 1 = 0?

Bitoperationen können schneller als reguläre Divisionen ausgeführt werden.

Born-to-Frag hat folgendes geschrieben:

Warum reicht es, die Zahl immer im 2 und dann um 4 zu erhöhen?

Steht im Thread Optimieren einer Primzahlfunktion hier in der Sparte genauer drin.
Geht im wesentlichen darum, dass Du das Sieb des Erastosteles unter der Annahme, dass Dir mehr als eine Primzahl (z.B. 2und 3) gegeben sind, periodische Folgen ermitteln kannst, die keine Primzahlen sein können.
D.h. bei 2 und 3 hast Du Periodenlänge 6 und folgende Zahlen, die Du ausschließen kannst: 6x, 6x+2, 6x+4 (weil durch 2 teilbar, sowie 6x und 6x+3 (weil durch 3 teilbar).

Born-to-Frag hat folgendes geschrieben:

greetz

EDIT: Ich hab da mal was gehighlighted wovon ich glaube das es doppelt ist..

Jup. War echt doppelt ;-)

Hab's in der neuen Version optimiert ;-)

@Horst: Ich bezweifel, dass für meinen Algo ein Loop-Unwinding für WheelSieving (2,3,5) großartige Vorteile bringt ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

Also ich messe mit einem P4 3.0GHz mit HT.. 137703ms.

Warum while Zahl and 1 = 0? shr versteh ich auch immer noch nicht ganz. Ich werd in der Zeit mal in der Delphi Hilfe nachsehen

greetz

EDIT: ganz vergessen :oops:

Zahl ist 9223372036854775806
Shr ist jetzt klar

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

BenBE · Verfasst: Mo 21.11.05 15:02

Born-to-Frag hat folgendes geschrieben:

Warum while Zahl and 1 = 0? shr versteh ich auch immer noch nicht ganz. Ich werd in der Zeit mal in der Delphi Hilfe nachsehen

Das wirst Du in der DOH nicht finden ;-)

Hängt mit der bionären Darstellung von Zahlen zusammen:

Mit X and 1 maskierst Du das letzte bit einer zahl und erhälst damit den Rest der Division durch 2. AND ist eine Bitoperation, die von der CPU in einem Zyklus ausgeführt werden kann. Eine Division benötigt IIRC 10++ Zyklen für's gleiche ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

Mit dem optimiertem Algo brauch ich jetzt noch ~131Sekunden

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

Horst_H · Verfasst: Mo 21.11.05 15:32

Hallo,

es geht doch garnicht um Loop unwinding.
Bei mir dauert ein Durchlauf hierfuer:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

var
  time : TdateTime;
  Test1,Test2,Test3: int64;
begin
  t := time;
  Test1 := cardinal(65537)*Cardinal(65531);
  Test1 := Test1*65517*32019;
  Test3 := 0;
 
  repeat
    inc(Test3);
    Test2 := Test1 mod Test3;
  until Test3 >= 10000000;
  t := time-t;
 
  writeln(Test3);
  writeln(Test2);
  writeln(Test1);
  writeln(FOrmatDateTime('hh:mm:ss.zzz ',t));
  writeln(Format('%e',[Test3/(t*86400)]));
end;

4.016 Sekunden fuer 1e7 Rechnungen bei 1.953e9 Hz
umgerechnet 784 Cpu Takte.

Also rechnet sich das mit DiffFeld.
Dein DiffFeld ist das Bis=1
DiffFeld Mod 2,3 rechnet 2/6=0.3333 aller Zahlen
Bis = 1..5 -> relAnzahl 0.333333;0.266666;0.22857;0.20779;0.19181
Das bedeutet ein Diffeld mit 5760 Feldern ergibt eine Berechnug fuer 0.1981 aller Zahlen bis root.
root ~4e9 /3 = 1.33 e9 Berechnungen
bei Bis =5 sind es 0.792e9 mod Berechnungen
also rund 60% wobei die Additionen ja sehr schnell sind.

Bei mir bestimmt das Primzahlesieb die Zahlen aber wesentlich schneller. 295 Takte mit dem alten TP Programm und mit alzaimar's unter 100 Takte pro Zahl.
Bis zu 1e9 sind es ja nur 50.8 Mio Primzahlen, also liegt dort ein Gewinn, statt mit 333 Mio Zahlen zu teilen.

Gruss Horst

Horst_H · Verfasst: Mo 21.11.05 16:00

Hallo,
ist das Ergebnis:
9223372036854775805 = 5*23 * 53301701 * 1504703107?
Dass dauert 9.5 Sekunden.(Mit DiffFeld Mod 2,3,5,7,11,13 nur 3.7 Sekunden)

Gute Guete wer rechnet denn da staendig eine Wurzel ausserhalb der while Schleife, dass ist mir beim lesen nicht aufgefallen.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:

function PrimFaktorZerlegung (Zahl: Int64): String;
var
  Teiler,
  Root: Cardinal;
  Index : integer;
  begin
  Result := '';
  While Zahl and 1 = 0 do
    Begin
    Result := Result + IntToStr(2) + ' * ';
    Zahl := Zahl shr 1;
    end;
  {
   For Index := 0 to BIS do
     While Zahl Mod and Prim[Index] = 0 do
       Begin
       Result := Result + IntToStr(Prim[Index]) + ' * '; 
       Zahl := Zahl DIV Prim[index];
       end;
   }
  if zahl >= 2 then
    Begin
    Root := Trunc(SQRT(Zahl));
    Teiler := 1;
    Index := 0;
    repeat
      inc(Teiler,2);
      //inc(Teiler,DiffFeld[index]);
      IF Zahl mod Teiler = 0 then
        begin
        repeat
          Zahl := Zahl div Teiler;
          Result := Result + IntToStr(Teiler) + ' * ';
        until Zahl mod Teiler <> 0; 
        Root := Trunc(SQRT(Zahl));//Nur dann wenn sich wirklich was aendert
        end;
//      inc(index);
//      If index > High(DiffFeld) then  
//         index := 0;
    until Teiler > Root;
    end;
    //dann jetzt aber doch
    if zahl <> 1 then
      begin
      Result := Result + IntToStr(Zahl) + ' * ';;
      end;
    Delete(Result, Length(Result) - 2, 3);
end;

Gruss Horst

Born-to-Frag · Beiträge: 1094 Win XP SP2, Win 2000 SP4 Delphi 7, 2k5

Hallo,

erm.. wir reden ja auch nicht von 9223372036854775805, sondern von 9223372036854775806

Also bei deiner Variante dauert 9223372036854775806 = 205938ms! Bei dem davor nur ~131 Sekunden!

9223372036854775805 dauert bei dem verbesserten von BenBe nur ~10Sekunden

Keiner rechnet hier Wurzeln außerhalb von while schleifen. Das ist doch schon längst verbessert das die Wurzel nur ausgerechnet wird wenn sich wirklich was ändert.

Also ist deiner langsamer

greetz

Edit: 9223372036854775805 hat bei mir bei deiner Variante auch 13Sekunden gedauert!

Es ist ja auch klar warum dein Algo 200sek braucht: Weil du immer nur im 2 erhöhst...

_________________
Theorie ist wenn man alles weiß, aber nichts funktioniert. Praxis ist wenn alles funktioniert, aber niemand weiß warum.
Microsoft vereint Theorie und Praxis: Nichts funktioniert und niemand weiß warum.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme