Hilfe bei bignum (Potenzproblem - ha ha !!)

skinny

Ich habe ein Problem mit sehr großen bzw. sehr kleinen Zahlen.

Ein kongretes Beispiel:
Ich habe eine Formel

x = y^31957 % 282035249
y sei 549824955

Wie kann ich x errechnen.
Da mir kein Datentyp bekannt ist der solche astronomischen Werte annehmen kann, stehe
ich etwas im Schatten.

Mir wurde schon bignum empfohlen, nur leider weiß ich gar nix drüber und bei der Suche
nach "bignum" kam hier auch nichts zum Vorschein.
Die zwei Beiträge mit der Suche "sehr große Zahlen" brachten mich auch nicht weiter.

Kann mir jemand was über BIGNUM sagen, oder viel besser mal 'n kleines Beispiel dazu
geben.

Weiterhin besteht ebenfalls noch das Problem, das wenn x bekannt ist, ich nach y
umstelle die 31957'te Wurzel gezogen werden müsste - was ja mit den bestehenden Datentypen
genauso unmöglich ist.

C++ Forumbot

Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Hallo,

das Zauberwort heißt Langzahlarithmetik. Wenn du dir die notwendigen Funktionen selbst schreiben möchtest, wirst du feststellen, dass das gar nicht so einfach ist, wenn die Berechnungen hinterher acuh noch einigermaßen schnell sein sollen. Die ganze Thematik ist jedenfalls sehr eng verwandt mit der Polynomrechnung; darüber findest du was in jedem guten Algorithmenbuch.

Ansonsten empfehle ich dir gnuMP oder hfloat:
http://www.jjj.de/hfloat/hfloatpage.html
http://www.swox.com/gmp/

Wenn dir das alles zu umständlich ist, kannst du dein Problem ja in einer Sprache lösen, die Rechnen mit großen Zahlen von "Haus aus" unterstützen, zB Lisp, SML oder auch Java.

Jester

Hallo,

Das Zauberwort in diesem Fall heißt modulo, oder auch Gruppentheorie...
Du kannst das Ergebnis berechnen, indem Du in jedem Rechenschritt nur den Rest berechnest.

a mod k + b mod k = (a+b) mod k
Für * gilt das analog.

Das heißt, zunächst kannst Du statt

y^31957 % 282035249 auch einfach (y % 282035249)^31957 % 282035249 berechnen. Damit werden die Zahlen schon bedeutend kleiner. Jetzt könnte man versuchen statt der kompletten Potenz immer nur einen Teil auszurechnen, also y^2 % 282035249 und dann das nächste aufmultiplizieren, zwischendrin immer wieder modulo. Leider sind Deine Zahlen schon zu groß, um in ein long reinzupassen (zumindest das Produkt zweier solcher Zahlen).
Wenn Du Dir aber Dein eigenes * schreibst, das in Additionen aufspaltet, dann sollte das mit dem modulo funktionieren.
Um a*b % k zuberechnen berechne b % k und (b+b) % k, anschließend b aufaddieren und wieder modulo, erhalte also (b+b+b) % k. Damit kannst Du in a Schritten a*b % k berechnen. Das kann man auch ein bißchen geschickter machen und dann in O(log a) wegkommen. Aber für's Prinzip mag das zunächst genügen.
Jedenfalls kommst Du in dieser Zahlengröße noch ohne beliebig große Zahlen aus.

MfG Jester

Hallo

Kleinigkeit vergessen:

Jester schrieb:

(a mod k + b mod k) mod k = (a+b) mod k

Jester

Jo, hast recht... liegt daran, daß ich bei modulo immer sofort auf den Restklassenring übergehe, da kümmert's mich dann nicht mehr.

skinny

habe mir gmp und auch miracl-Library (scheint auch die nötigen Funktionen zu haben) downgeloaded.
Bin aber trotzdem am Verzweifeln !!!!

Wie bindet man diese denn in ein Projekt ein ?
Bis jetzt hatte ich nur mit Komponenten, die ein Setup oder eine .bpk enthhielten (Borland C++ Builder) zu tun.