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 1 von 2  1 2   
Benutzerbild von Aphton
Aphton

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

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

  Alt 8. Mär 2011, 23:23
Gute Nacht, liebe Programmierfreunde

Hiermit möchte die Tau(N) Funktion näher bringen.

Tau(N) berechnet die Anzahl der ganzzahligen Divisoren von N - bsp. Tau(20) = 6, denn 20 ist teilbar durch {1, 2, 4, 5, 10, 20}.
Diese Funktion dürfte den Derive Benutzern auch unter dem Namen "divisorTau()" bekannt sein; so habe ich sie auch genannt.

Mathemathischer Hintergrund:
- wenn p = Primzahl ^ k = Positiver Integer, dann gilt:
tau(p^k) = k+1
- wenn ggT(a, b) = 1 dh. wenn a und b = Primzahlen teilfremd (danke BUG), dann gilt:
tau(ab) = tau(a) * tau(b)
Quelle

Da bei der Tau Funktion Primzahlen bzw. Primfaktorzerlegung benötigt wird, habe ich weiters noch den Sieb des Eratosthenes implementiert und das so gemacht, dass er im Wertebereich von {_From .. _Till} die Primzahlen bestimmen kann!

Delphi-Quellcode:
type
  TBoolArray = Array of Boolean;
  TPoint64 = record
    X, Y: Int64;
  end;

  TNumberState = (nsIsPrime, nsIsNotPrime, nsOutOfRange);
  TPrimeTable = record
  private
    FTable: TBoolArray;
    FMin, FMax: Int64;
    function GetNumberState(const Number: Int64): TNumberState;
  public
    procedure CreateTable(const AMin, AMax: Int64);
    property Min: Int64 read FMin write FMin;
    property Max: Int64 read FMax write FMax;
    property NumberState[const Prime: Int64]: TNumberState read GetNumberState; default;
  end;

{TPrimeTable}

function CreatePrimeTable(const Min, Max: Int64): TBoolArray;
var
  Size : Int64;
  i, j : Int64;
begin
  Size := Max - Min + 1;
  SetLength( Result, Size );
  FillChar( Result[0], Length(Result), True );
  i := 1;
  while i <= Max div 2 do
  begin
    inc( i );
    if (i >= Min) and (not Result[i-Min]) then
      continue;
    if (Min = Max) and (not Result[0]) then
      Exit;
    if i < Min then
      j := i * Trunc(Min / i)
    else
      j := i * 2;
    while j < Min do
      inc( j, i );
    while j <= Max do
    begin
      Result[j-Min] := False;
      inc( j, i );
    end;
  end;
end;

procedure TPrimeTable.CreateTable(const AMin, AMax: Int64);
begin
  FMin := Math.Min( AMin, AMax );
  FMax := Math.Max( AMin, AMax );
  FTable := CreatePrimeTable( FMin, FMax );
end;

function TPrimeTable.GetNumberState(const Number: Int64): TNumberState;
var
  i: Int64;
begin
  Result := nsOutOfRange;
  i := Number - Min;
  if (i >= 0) and (i <= Max-Min) then
    if FTable[i] then
      Result := nsIsPrime
    else
      Result := nsIsNotPrime;
end;

function divisorTau(N: Int64): Int64;
var
  Primes : TPrimeTable;
  exp : Array of TPoint64;
  i, Index : Int64;
  BlockStart: Int64;
  HalfN : Int64;
  NoPrimeDividerFound: Boolean;
  primIndexIncrementor: Integer;
const
  BlockSize = 1000; // for the table
  function _GetExponent(const E: Int64): Integer;
  var
    i: Integer;
  begin
    Result := -1;
    for i := 0 to High(exp) do
      if exp[i].X = E then
      begin
        Result := i;
        Exit;
      end;
  end;
  procedure NewExp(const E: Int64; const F: Int64 = 0);
  begin
    SetLength( exp, Length(exp) + 1 );
    Index := High(exp);
    exp[Index].X := E;
    exp[Index].Y := F;
  end;
  function IsPrime(const P: Int64): Boolean;
  var
    SmallTtbl: TPrimeTable;
  begin
    if (P >= Primes.Min) and (P <= Primes.Max) then
      Result := Primes.NumberState[P] = nsIsPrime
    else
    begin
      SmallTtbl.CreateTable( P, P );
      Result := SmallTtbl.NumberState[P] = nsIsPrime;
    end;
  end;
  procedure PF();
  begin
    Primes.Min := 0;
    halfN := Trunc( SQRT( N ) );
    SetLength( exp, 0 );
    repeat
      BlockStart := 2;
      NoPrimeDividerFound := True;
      repeat
        if Primes.Min <> BlockStart then
          Primes.CreateTable( BlockStart, BlockStart + Min( BlockSize, HalfN ) );
        i := Primes.Min;
        if i = 2 then
          primIndexIncrementor := 1
        else
        begin
          if i and 1 = 0 then
            inc( i );
          primIndexIncrementor := 2;
        end;
        while i <= Primes.Max do
        begin
          if Primes.NumberState[i] = nsIsPrime then
            if N mod i = 0 then
            begin
              NoPrimeDividerFound := False;
              Index := _GetExponent( i );
              if Index = -1 then
                NewExp( i );
              repeat
                inc( exp[Index].Y );
                N := N div i;
              until N mod i > 0;
              // die folgende notwendige Zeile bringt alles zum Stocken
              if (N > 1) and IsPrime( N ) then
              begin
                NewExp( N, 1 );
                N := 1;
                Exit;
              end;
              if i > 2 then
                break;
            end;
          inc( i, primIndexIncrementor );
          primIndexIncrementor := 2;
        end;
        if not NoPrimeDividerFound then
          break;
        inc( BlockStart, BlockSize );
      until (N <= 1) or (BlockStart + BlockSize > halfN);
    until NoPrimeDividerFound or (N <= 1);
  end;
begin
  PF;
  if N > 1 then
    Result := 0
  else
  begin
    Result := 1;
    i := 0;
    while i < Length(exp) do
    begin
      Result := Result * ( exp[i].Y + 1 );
      Inc( i );
    end;
  end;
end;
Ich habe diesen Code für die Projekt Euler Aufgabe #12 programmiert und dachte mir, dass jemand anderer auch noch Nutzen daraus ziehen könnte.

Ich garantiere keine 100%'ige Richtigkeit; eines kann ich aber sagen - die Aufgabe habe ich innerhalb von 5 Sekunden gelöst =)

Bin für Verbesserungsvorschläge und konstruktive Kritik offen.

Edit:
Mir fällt gerade ein, das man da eventuelle etwas verbessern könnte.
Die erste (äußerste) (repeat) Schleife könnte man eventuell wegbringen, wenn mir einer bestätigen könnte, dass die Primzahlen, die beim Primfaktorzerlegen zum Dividieren verwendet werden, in aufsteigender Reihenfolge drankommen und keine davon sich wiederholt.
Konkret: wenn soetwas z.B.: nicht geschehen kann:
2*2*2 * 3*3*3 * 5*5*5 * 2*2*2
Also hier wiederholt sich die Primzahlenpotenz (2^3). Wenn das nie eintritt, kann man die repeat Schleife sparen, denn sie sorgt dafür, dass die Anfangsprimzahlen wieder zum Dividieren verwendet werden. Und weiter müsste ich dann auch kein Array of TPoint64 verwenden und könnte mir auch noch die _GetExponent Funktion (ermittelt den Index) sparen.

Gute Nacht
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 9. Mär 2011 um 17:20 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 15. Feb 2008
Ort: Baden-Württemberg
2.260 Beiträge
 
Delphi 2007 Professional
 
#2

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

  Alt 9. Mär 2011, 00:10
Sollte man folgenden Codeabschnitt nicht mit einer For-Schleife anstelle des While-Ersatzkonstrukts programmieren?
Delphi-Quellcode:
i := Primes.Min;
while i <= Primes.Max do
begin
  if Primes.PrimeState[i] = psIsPrime then
    ....

  inc( i );
end;

// also vereinfacht so
for i:=Primes.Min to Primes.Max do
begin
  if Primes.PrimeState[i] = psIsPrime then
    ....
end;
Ich sehe da noch weitere While-Schleifen, die sich mit einer For-Schleife ersetzen lassen.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

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

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

  Alt 9. Mär 2011, 00:14
Das sind Int64 Werte (Min & Max)!
Edit: Int64 Variablen können in Turbo Delphi Explorer (2006) bei der For Schleife nicht verwendet werden.
Danke für die Aufmerksamkeit!
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 15. Feb 2008
Ort: Baden-Württemberg
2.260 Beiträge
 
Delphi 2007 Professional
 
#4

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

  Alt 9. Mär 2011, 00:22
Das sind Int64 Werte (Min & Max)!
Edit: Int64 Variablen können in Turbo Delphi Explorer (2006) bei der For Schleife nicht verwendet werden.
Danke für die Aufmerksamkeit!
Schade. Der Code wird so schwerer zu lesen als nötig.
Wenn der Bereich von Min & Max grössere Dimensionen annimmt, dann müssste man
vielleicht noch TBoolArray als packed array deklarieren.
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

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

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

  Alt 9. Mär 2011, 00:24
Hmmm, wenn du mir bestätigen könntest, dass packed Array die Performance nicht verschlechtert?
Imho gibts bei packed Arrays kein Aligning, was zu nem kleineren Speicherverbrauch führt, jedoch leidet das Zugreifen auf die Werte darunter!
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
1.545 Beiträge
 
FreePascal / Lazarus
 
#6

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

  Alt 9. Mär 2011, 00:32
... wenn ggT(a, b) = 1 dh. wenn a und b = Primzahlen, ...
4 ist keine Primzahl (2*2)
13 ist eine Primzahl (13)
ggT(4, 13) = 1

ggT(a, b) = 1 <=> a und b teilerfremd
Robert

Geändert von BUG ( 9. Mär 2011 um 00:38 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 15. Feb 2008
Ort: Baden-Württemberg
2.260 Beiträge
 
Delphi 2007 Professional
 
#7

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

  Alt 9. Mär 2011, 00:39
Natürlich wird der Zugriff etwas langsamer.
Ich kann jetzt nur grob schätzen, dass der Zugriff vielleicht 30% länger dauert und der gesamte Algorithmus ~10% langsamer. wird
Das müsste man testen und ich hab keinen Compiler auf'm Rechner, der Funktionen in Records mag.
Aber wenn die Werte Min & Max schon auf Werte > 2^31 ausgelegt sind, dann muss man Kompromisse eingehen.
  Mit Zitat antworten Zitat
Benutzerbild von BUG
BUG

Registriert seit: 4. Dez 2003
Ort: Cottbus
1.545 Beiträge
 
FreePascal / Lazarus
 
#8

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

  Alt 9. Mär 2011, 00:51
Andererseits muss diese Menge an Speicher ja auch verwaltet werden.
Bei einer Array-Größe von 2^32 sind das selbst bei einem packed Array schon 4GB, da stößt du mit Delphi im Moment auf die Grenzen.
Wenn du auf Bitebene arbeiten würdest, könntest du da mit 512MB auskommen.
Robert
  Mit Zitat antworten Zitat
Benutzerbild von Aphton
Aphton

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

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

  Alt 9. Mär 2011, 00:55
@BUG
Danke, du hast recht. a und b sind teilfremd und müssen nicht zwingend Primzahlen sein.
Weiters - die Indices des Arrays werden getestet, ob es sich um eine Primzahl handelt. Deswegen auch Int64. Dabei muss das Array nicht > 2^32 sein.
Man kann ja Min und Max so wählen, dass die Differenz < 2^32 bzw Max Arbeitsspeicher ist.

Deshalb auch Ressourcensparend: die Tau Funktion geht Blockweise bis zu N/2 durch und belegt nie einen Speicher > 1000 Bytes (PrimeTable - Array of Boolean)
das Erkennen beginnt, wenn der Erkennende vom zu Erkennenden Abstand nimmt
MfG

Geändert von Aphton ( 9. Mär 2011 um 01:03 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu
Online

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
27.296 Beiträge
 
Delphi XE3 Professional
 
#10

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

  Alt 9. Mär 2011, 11:24
Hmmm, wenn du mir bestätigen könntest, dass packed Array die Performance nicht verschlechtert?
Zitat:
Delphi-Quellcode:
TBoolArray = Array of Boolean;
TPoint64 = record
  X, Y: Int64;
end;

exp : Array of TPoint64;
Bei diesen beiden Records macht packed absolut keinen Unterschied.
Also, da sich absolut nix an der Ausrichtung ändert, kann sich auch nichts verbesser/verschlechtern.

Ein Array ist immer packed (es sei denn ein enthaltener Record ist packed und eine Ausrichtung könnte das Array optimieren).
Und bei einem Record greift eine Ausrichtung nur, wenn unterschiedlich große Basistypen im Record verbaut wurden ... also bei gleich großen Basistypen kann packed nichts verändern.

PS: Array of Boolean/Byte/.../ShortInt ist ein Sonderfall, denn hier ist ein Arrayfeld jeweils 1 Byte und es ist somit immer packed, da packed die Ausrichtung temporär auf 1 heruntersetzt.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2013
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

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 00:59 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