Potenzieren mit sehr großen Zahlen ohne modulus?????

[Dr.Hackstable]

Hallo

Ich möchte eine 512-bit zahl mit einer 512-bit Zahl potenzieren ohne modulus operation! Mathematisch ist das natürlich eine so verdammt große Zahl, dass kein Speicher dazu ausreichen würde!

die Formel sieht aber so aus
a,b,x,y seien 512-bit Zahlen die keinen ggt haben

Code:

ergebnis = a^x * b^y  // Wobei y negativ ist

d.h
es entpricht

Code:

ergebnis = a^x / b^y

Aus theoretischen Überlegungen weiß ich dass das Ergebnis ganz sicher kleiner ist als 512-bit!

Kann man das irgendwie berechnen, ohne jeweils extra b^y und a^y berechnen zu müssen??

Danke
Grüße
Dr.Hackstable

[bigg]

Mit welchem Datentyp rechnest du eigentlich?

[alzaimar]

(a^x)/(a^y) = a^(x-y)

[bigg]

Jetzt hast du die Gleichung umgestellt, und?
Aus der Informatik wissen wir, das sich alle Rechenoperationen aus der Addition zusammensetzen!

[alzaimar]

Mach es doch so:

Delphi-Quellcode:

Function MegaPotenzierer (a,b,x,y : Extended) : Extended;
Const
  ccZero = 1E-5; // Hab vergessen, wie man floats auf 0 prüft
  ccMin = 0.000001;   // kleinstes Zwischenergebnis
  ccMax  = 100000000; // höchstes Zwischenergebnis

Begin
  Result := a; x:=x-1;
  Repeat
    while (x>ccZero) do begin
      Result := result * a; 
      x:=x-1;
      if (Result > ccMax) Then Break; // jetzt nicht mehr weiterrechnen
      End;
 
    while (y>ccZero) do begin
      Result := result / b; 
      y := y - 1;
      If Result > ccMax Then Break;
      End;
  Until (x<ccZero) and (y<ccZero); // Heisst das nicht 'IsZero (x)'?
End;

Ungetestet, aber ich potenziere so lange mit a, bis ich nicht mehr darf, oder bis das Zwischenergebnis größer als ein bestimmter Wert ist. Dann wird so lange durch b geteilt, bis ich nicht mehr darf, oder das Zwischenergebnis wieder kleiner als ein Minimalwert ist. Das wird so lange wiederholt, bis nichts mehr zu tun ist.

[Dr.Hackstable]

a sollte ungleich b sein !
a <> b
also klappt das nicht mit (x-y)

was gehen würde wäre vielleicht:

Code:

ergebnis = exp ( x*lna - y*lnb)

Hilft mir aber auch nicht viel! Ich rechne mit IInteger Zahlen von Decmath!
Man kann damit beim Exponent bis max_integer rechnen, mehr würde auch keinen Sinn machen!

Aber trotzdem müsste es doch eine Lösung für mein Problem geben, da das Ergebnis kleiner ist als 512-bit!??

[Flocke]

Um dein Problem einmal umzuformulieren:

Du möchtest z.B. 4^9 / 5^7 = 3 ausrechnen, ohne vorher 4^9 (262144) bzw. 5^7 (78125) vollständig ausrechnen zu müssen (ich hab' jetzt mal deine 512 Binärstellen auf 1 Dezimalstelle reduziert, das Ergebnis passt auch in eine Dezimalstelle).

Da es sich nach deiner Aussage um teilerfremde Zahlen handelt, wüßte ich dafür keinen Ansatz.

Einfacher wäre es natürlich, wenn du mit a*(2^x) und b*(2^y) rechnen würdest - aber das wird wohl nicht gehen.

[negaH]

Es gäbe da einen Weg:

Berechne die Primfaktorzerlegung von a^x und b^y. Dann kannst du beide Tabellen der Primzahlexponenten jeweils bei gleicher Basis die Exponenten subtrahieren. Das was übrig ist ist die Tabelle der Primzahlexponenten von a^x/b^y und wird einfach ausmultipliziert.

In Unit NCombi.pas findest du die Funktionen NPowerTable() und NPrd() die das mit den Faktultäten demonstrieren. Das wäre der einzigste Weg der mir einfällt im Moment um wirklich das Ergebnis aufs letzte Bit exakt ausrechnen zu können.

Gruß Hagen

[Dr.Hackstable]

hey thx, stimmt:-D wann man das machen kann:-)
NPowerTable() und NPrd()
Die zwei Funktionen habe ich nicht ganz kapiert :oops: , könntest du mir ein kleines Beispiel geben wie ich eine Primfaktorzerlegung mit einem IInteger zahl machen kann.

Zitat:

Dann kannst du beide Tabellen der Primzahlexponenten jeweils bei gleicher Basis die Exponenten subtrahieren.

"Bei gleicher Basis" tritt der Fall überhaupt auf???, a und b haben keinen gemeinsamen teiler?

[Flocke]

Zitat:

Zitat von Dr.Hackstable

a,b,x,y seien 512-bit Zahlen die keinen ggt haben

Zitat:

Zitat von negaH

Berechne die Primfaktorzerlegung von a^x und b^y. Dann kannst du beide Tabellen der Primzahlexponenten jeweils bei gleicher Basis die Exponenten subtrahieren. Das was übrig ist ist die Tabelle der Primzahlexponenten von a^x/b^y und wird einfach ausmultipliziert.

Welche gleiche Basis ? :gruebel: