Einzelnen Beitrag anzeigen

Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#22

Re: Eine BigInt Klasse + RSA-Beispiel

  Alt 10. Aug 2007, 14:07
Ja das stimmt.

Nun baue mal das

A := B^C mod D

Das wirst du nicht effizient bewerkstelligen könne das das Operatoren Überladen keine Funktionen mit 2 Parametern zulässt.
Man kann zwar

A := B^C;
A := A mod D;

berechnen aber nur theoretisch nicht praktisch. Da B^C beides Zahlen jenseits 2^1024 sein können entstehen durch die Exponenation gigantische Zahlen. Diese sind so groß das sie nie in einen Rechner berechnet werden können.

Die Operation B^C mod D wird also überlicherweise so gelöst das man in jedem Zwischenschritt der Berechnung von C^B modular mit D reduziert. Die nun größten Zahlen die auftreten können sind maximal 2^Ln2(D)*2 Bits groß, also doppelte Anzahl von Bits als D hat.

Nun es gibt noch viele solcher Beispiele die mit dem Operatoren Überladen nicht sauber umgesetzt werden können. Das hat zur Konsequenz das mit deinem Ansatz wir einen Misch Masch aus Funktionen/Objekten und überladenen Operatoren haben. Also keine sinnvolle und homogene Schnittstelle mehr.

Den Ansatz mit Operatoren Überladung eine gute math. Bibliothek bauen zu wollen erachte ich für zu kurzsichtig gedacht.
Es ist dann besser die Operatoren +,- usw. wirklich als Funktionen oder Mehtoden eines Objektes zu bauen.

Aber auch den OOP Ansatz halte ich für schlecht. Stellen wir uns mal ein Object TInteger vor und bauen darin alle wesentlichesten math. Methode rein. Schwups entsteht eine Monsterklasse mit mehr als 100 Methoden. Nun wollen wir diese Schnittstelle in Zukunft durch weitere Mathematische Funktionen erweitern. Also müssen wir diese Monster-Klasse erneut verändern und fügen weitere Methoden hinzu. Das ist dann keine auf's wesentliche abstrajierte OOP Schnittstelle mehr sondern eher eine Sammlung wichtiger Funktionen gruppiert in einem Objekt das bei nachträglichen Veränderungen alle darauf aufsetzten Quellcodes neu complieren lässt.

Nein ich sehe es so: unser Typ TInteger ist nur ein Datentyp wie Integer, LongString usw. Dieser Datentyp wird in normalen prozeduralen Funktionen verwendet die selber die Mathematik für diesen Datentyp implelemtieren. Das ist erweiterbar, wiederverwendbar, einfach zu verstehen und effizient (es vermeidet den mittlerweile gigantischen Overhead der OOP).

OOP gut und schön, aber in diesem Falle kontroproduktiv. Und ich weiß wovon ich rede. Meine DECMath Library ist nun das 4. Konzept in der Schnittselle. Alle 3 Versionen davor waren OOP konform und vom Handling längst nicht so sauber wie die jetzige 4. Version. Diese arbeitet rein Prozedural, benutzt aber Interface-Records als Datentypen der IInteger.

Gruß Hagen

PS: hier mal ein Beispiel wie eine Berechnung der Zahl Pi per AGM aussieht

Delphi-Quellcode:
  procedure NPi_AGM(var R: IInteger; Decimals: Cardinal);
{AGM start with:
  a = 1, b = 1/Sqrt(2), t = 1/2, k = 1

iteration:

  s = (a + b) / 2
  d = a - s
  d = d^2
  a = s
  s = s^2
  t = t - d * 2^k
  b = Sqrt(s - d)
  k = k +1

final:
   pi ~ (a + b)^2 / 2t }

  var
    A,B,D,T: IInteger;
    W: Integer;
  begin
    Inc(Decimals, 3); // +3 digits reserve
    NPow(R, 5, Decimals); // R = 5^Decimals
    NShl(A, R, Decimals); // A = 10^Decimals
    NShl(D, R, Decimals -1); // D = 10^(Decimals -1)^2
    NSqr(D);
    NSqr(B, A); // B = (10^Decimals^2 * 2)^0.5 div 2
    NShl(B, 1);
    NSqrt(B);
    NShr(B, 1);
    W := 0;
    repeat
      NAdd(T, A, B); // T = (A + B) div 2, new A
      NShr(T, 1);
      NMul(B, A); // B = (B * A)^0.5
      NSqrt(B);
      NSub(A, T); // A = (A - T)^2 * 2^W
      NSqr(A);
      NShl(A, W);
      Inc(W);
      NSub(D, A); // D = D - A
      NSwp(A, T);
    until NCmp(B, A) = 0;
    NShr(D, Decimals);
    NDiv(D, R);
    NMul(D, 1000);
    NSqr(R, A);
    NDiv(R, D);
  end;
Wenn man sich an die Schreibweise gewöhnt hat ist alles strikt und konsistent auch wenn man später noch weitere mathematische Funktonen in anderen Units der Bibliothek hinzufügt.
Wollte man das per Operatoren Überladung erreichen das müsste der Compiler viel weitreichendere Features in diesem Bereich zur Verfügung stellen. Der Compiler müsste eben

B^C mod D

erkennen und einen Operator der Form Result = Var1 op1 var2 op3 var3 umsetzen können.
  Mit Zitat antworten Zitat