Tau Funktion (+Ressourcensparend; +Erweiterter Sieb von Eratosthenes)

[gammatester]

Zitat:

Zitat von Aphton (Beitrag 1086929)

... die Tau Funktion geht Blockweise bis zu N/2 durch ...

Statt N/2 ist nimmt man doch normalerweise die Wurzel aus N (oder übersehe ich hier etwas Offensichtliches?). Dies spielt bei zusammengesetzten Zahlen oft keine Rolle (wenn dynamisch abgebrochen wird), aber sehr wohl, wenn N einen sehr großen Primfaktor hat.

[Aphton]

Ne, denn die kleineste Primzahl ist ja bekanntlicherweise 2!

Edit: Mir ist übrigens eingefallen, wie man das noch verbessern könnte.
Ich erhöhe beim Primfraktorzerlegen den Int64 i immer um 1. Ich werd es so umprogrammieren, dass beim ersten Durchgang, also wenn i = 2, es wie gewohnt abläuft, aber dann, immer in zweier Schritten inkrementiere, da ja alle anderen geraden Zahlen ein vielfaches von 2 sind.
Ich werd einen weiteren Inkrementor implementieren, der, sobald i = 2, von 1 auf 2 inkrementiert wird und letztendlich am Schluss, wo inc( i ) steht, der Inkrementor drin stehen wird.

Die Werte die I bei dieser Schleife annimmt, sehen so aus (bei Primes.Min = 2)
{2, 3, 5, 7, 9, 11, 13, 15, 17, ...}

Update (Edit):
Habs nun ausgebessert. Hab die Variable "PrimIncIncrementor" eingeführt. Nun dürfte es doppelt so schnell die Primfaktorzerlegung durchführen!
Siehe Beitrag #1

[gammatester]

Zitat:

Zitat von Aphton (Beitrag 1087007)

Ne, denn die kleineste Primzahl ist ja bekanntlicherweise 2!

Versteh ich trotzdem nicht ganz. Für die Primfaktorzerlegung mußt Du doch nur alle Primzahlen bis sqrt(N) prüfen. Warum erstellst Du also (zumindest theoretisch) ein Siebfenster in der Nähe von N/2.

Mal anders: Was liefert Dein Programm für Tau(8937393460516237311) und wie lange braucht es?

Mein mit einem Primzahlgenerator kurz zusammengehacktes liefert das (von Wolfram Alpha bestätigte) Ergebnis in 1.1 s.

[Aphton]

Hmm. Es gibt, so wie es aussieht, ein paar große Probleme. Ich arbeite gerade dran.
Der Code ist so nicht funktionstüchtig! (Also nur teilweise).
Edit: So, nun dürfte er so richtig funktionieren.

Edit: @gammatester
Wow, das wird sowas von in die Knie gezwungen.

Ok, das Problem ist, dass er ewig lang iterieren muss, bis er beim entsprechenden Werten für den Sieb in CreatePrimes angelangt ist =\ Irgendwelche Ideen?

Edit: Nun, das habe ich schon vor Ewigkeiten ausgebessert. Es sind nun unzählige Fehler weggekommen; trotzdem ists momentan noch so, dass es bei sehr großen Zahlen etwas länger dauert, WENN bei der Primfaktorzerlegung der Quotient dann eine weitere Primzahl ist!
Oder einfacher ausgedrückt:
Je größer die Zahl und je kleiner der Tau() Wert dieser Zahl, desto länger braucht es.

90 ms für divisorTau( 26113434792554522 ) = 128
Wie schon gesagt, bei großen Werten, deren Tau klein ist, dauerts sehr lange.

Hilfe

[gammatester]

Zitat:

Zitat von Aphton (Beitrag 1087036)

Je größer die Zahl und je kleiner der Tau() Wert dieser Zahl, desto länger braucht es.

90 ms für divisorTau( 26113434792554522 ) = 128
Wie schon gesagt, bei großen Werten, deren Tau klein ist, dauerts sehr lange.

Hilfe

Leider habe ich keinen Schimmer, was Dein Code genau macht. Ich habe ihn laufen lassen und selbst mit sqrt(N) statt N/2 endet er nie für große N. Ich weiß nur, daß auf meinem Uralt-1.7GHz-Pentium 4 zu Hause die Zeiten für meinen Code wie folgt sind

Code:

Mit Prime-Generator:
tau(8937393460516237311) = 30
Start: 19:41:37.38     Stop: 19:41:40.07     Diff: 2.69 sec

Mit simple nextprime32
tau(8937393460516237311) = 30
Start: 19:43:07.79     Stop: 19:43:32.34     Diff: 24.55 sec

Wenn Interesse besteht, kann ich ihn auch posten.

[Aphton]

Ja mach das bitte.

[gammatester]

Das Testprogramm benutzt die Unit mp_prime aus meiner MPArith-Sammlung, bzw als Direktlink: http://home.netsurf.de/wolfgang.ehrh...2011-01-04.zip

Delphi-Quellcode:

{Testprogram zu DP-Praxis 2010-03-09: Tau Funktion von Aphton}
program t_tau;

{$i STD.INC}

{$ifdef APPCONS}
  {$apptype console}
{$endif}

uses
  mp_prime;

{$ifndef HAS_INT64}
type
  int64 = longint;
{$endif}


type
  TPrimeFac = record
                p: int64;
                e: integer;
              end;

  TFactList = array[1..64] of TPrimeFac;


{---------------------------------------------------------------------------}
procedure factor(n: int64; var pcn: integer; var FLN: TFactList);
  {-Primfaktorzerlegung von n mit Primgenerator}
var
  sieve: TSieve;
  cp: int64;
begin
  prime_sieve_init(sieve,2);
  pcn := 0;
  repeat
    cp := prime_sieve_next(sieve);
    if cp=1 then break;
    if n mod cp = 0 then begin
      {Potenzen von cp anspalten}
      inc(pcn);
      with FLN[pcn] do begin
        p := cp;
        e := 1;
        n := n div cp;
        while (n<>1) and (n mod cp = 0) do begin
          inc(e);
          n := n div cp;
        end;
      end;
    end;
  until cp*cp > n;
  if cp<=1 then begin
    writeln('Überlauf prime_sieve_next');
    halt;
  end
  else if n<>1 then begin
    {Rest n ist prim}
    inc(pcn);
    with FLN[pcn] do begin
      p := n;
      e := 1;
    end;
  end;
  prime_sieve_clear(sieve);
end;


{---------------------------------------------------------------------------}
procedure factor2(n: int64; var pcn: integer; var FLN: TFactList);
  {-Primfaktorzerlegung von n mit nextprime32}
var
  cp: int64;
begin
  pcn := 0;
  cp  := 1;
  repeat
    cp := nextprime32(cp+1);
    if cp<=1 then break;
    if n mod cp = 0 then begin
      {Potenzen von cp anspalten}
      inc(pcn);
      with FLN[pcn] do begin
        p := cp;
        e := 1;
        n := n div cp;
        while (n<>1) and (n mod cp = 0) do begin
          inc(e);
          n := n div cp;
        end;
      end;
    end;
  until cp*cp > n;
  if cp<=1 then begin
    writeln('Überlauf prime_sieve_next');
    halt;
  end
  else if n<>1 then begin
    {Rest n ist prim}
    inc(pcn);
    with FLN[pcn] do begin
      p := n;
      e := 1;
    end;
  end;
end;


{---------------------------------------------------------------------------}
function tau(n: int64): longint;
  {-Tau-Funktion = sigma0(n)}
var
  i,pcn: integer;
  fln: TFactList;
  t: longint;
begin
  factor2(n,pcn,fln);
  t := 1;
  for i:=1 to pcn do t := t*(1+fln[i].e);
  tau := t;
end;


var
  n: int64;
  t: longint;
begin
{$ifdef HAS_INT64}
  n := 8937393460516237311;
{$else}
  n := 2080899072;
{$endif}
  t := tau(n);
  writeln('tau(',n,') = ',t);
end.