AGB  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Code-Bibliothek Neuen Beitrag zur Code-Library hinzufügen Delphi Tau Funktion (+Ressourcensparend; +Erweiterter Sieb von Eratosthenes)

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

Ein Thema von Aphton · begonnen am 8. Mär 2011 · letzter Beitrag vom 9. Mär 2011
Antwort Antwort
Seite 2 von 2     12
gammatester

Registriert seit: 6. Dez 2005
744 Beiträge
 
#11

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

  Alt 9. Mär 2011, 11:56
... 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.

Geändert von gammatester ( 9. Mär 2011 um 13:02 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.141 Beiträge
 
Turbo Delphi für Win32
 
#12

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

  Alt 9. Mär 2011, 13:32
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
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 9. Mär 2011 um 13:46 Uhr)
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
744 Beiträge
 
#13

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

  Alt 9. Mär 2011, 14:42
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.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.141 Beiträge
 
Turbo Delphi für Win32
 
#14

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

  Alt 9. Mär 2011, 15:15
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
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 9. Mär 2011 um 17:41 Uhr)
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
744 Beiträge
 
#15

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

  Alt 9. Mär 2011, 18:57
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.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

Registriert seit: 31. Mai 2009
1.141 Beiträge
 
Turbo Delphi für Win32
 
#16

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

  Alt 9. Mär 2011, 19:09
Ja mach das bitte.
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
744 Beiträge
 
#17

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

  Alt 9. Mär 2011, 19:47
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.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 04:20 Uhr.
Powered by vBulletin® Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2014 by Daniel R. Wolf