Binäre Exponentiation

Status
Nicht offen für weitere Antworten.
Hallo,

Wir sollen im Informatik Unterricht eine Binäre Exponentiation in Java (BlueJ) implementieren.
Es soll die Methode modPow() der Klasse BigInteger nachgestellt werden.

genaue Aufgabe:

Berechnung von k^e mod n

als Ansatz wurde gegeben
Code:
public BigInteger power_mod(BigInteger k, BigInteger e, BigInteger n)


vielen dank für eure Antworten
:meld:
 

Murray

Top Contributor
Und wo steckt jetzt euer konkretes Problem? Überhaupt keinen Plan, was jetzt zu tun ist? Oder einfach keinen Bock, sich selbst Gedanken zu machen?
 
Wir haben keine Ahnung, wie wir die Potenz realisieren, da wir keine vorgefertigten Java-Methoden benutzen dürfen.
Das Modulo sollte kein Problem darstellen.

mfg
 

Kaladial

Bekanntes Mitglied
k^e:

2^4 = 2*2*2*2 ...

wo ist also nun das problem?

macht doch einfach in die funktion power_mod ne for-schleife...

nach dem motto:

Code:
int erg=0;
for(int i=0; i<e; i++){
  if(erg==0){
    erg=k;
  }else{
    erg=erg*k;
  }
}

fertig
 

SnooP

Top Contributor
probiert mal auf Papier aus, was mit Binärzahlen passiert, wenn man sie potenziert, insb. guckt euch gerade und ungerade Zahlen an und versch. hohe Exponenten. Fällt was auf? Wenn ja, dann guckt euch die Java-Bitoperatoren an, insb. der << left-shift Operator ist da interessant.
Das Modulo sollte letztlich dann tatsächlich kein Problem sein - wobei die Idee ja ist, dass man mit power_mod Berechnungen innerhalb einer Restklasse machen kann... sollt ihr denn BigInteger als Parameter benutzen? Oder quasi Strings oder normale primitive Typen mit halt der Einschränkung der maximalen Größe solcher Zahlen?

P.S. der Tip von Kaledial ist vermutlich nicht das, was der Proff haben wollte...
 

VuuRWerK

Aktives Mitglied
Sollte doch noch schneller mit einer Bitoperation zu lösen sein, oder?

Code:
int erg = k << e;

Gut Schuß
VuuRWerK ;)

Edit: Zu langsam, ok :)
 
So wir haben jetzt mit ein wenig Hilfe des Internets diesen Quellcode geschrieben.
Leider verstehen wir ihn nicht und darum bitten wir um Hilfe bei der erläuterung.
Danke im vorraus.

Code:
    public int powMod(int k, int e, int n)
    {
    int erg=1;
    while (e>0)
    {
        if (e%2==1) //prueft ob die Zahl e ungerade ist
        {
            erg=erg*k%n;
        }
        k=k*k%n;
        e=e/2;
    }
    return erg;
    }
 

Marco13

Top Contributor
Vielleicht hilft ein Beispiel?
2^10 ist 2*2*2*2*2*2*2*2*2*2
Wenn man das "per Hand" ausrechnet, muss man 9 mal multiplizieren. Ist ja aber blöd: Man multipliziert ja immer das gleiche. Man könnte ja auch sagen
2^10 ist (2*2)*(2*2)*(2*2)*(2*2)*(2*2)
Und dann schon berechnete Werte wiederverwenden
x = (2*2)
2^10 = x^5 = x * x * x * x * x = (2^2)^5
Damit braucht man nur 5 Multiplikationen.

Und wenn man sich jetzt die Zahl 10 in binärdarstellung ansieht:
10 (dec) = 1010 (bin) = 1 * 8 + 0 * 4 + 1 * 2 + 0 * 1
Sieht man vielleicht mit ein bißchen Überlegen ein, warum man 2^10 auch als 2^8 * 2^2 interpretieren kann, und wo der Vorteil dabei ist...
Denkt dabei auch mal an die Regeln
x^n * x^m = x^(n+m)
(x^n)^m = x^(n*m)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
pkelod Binäre Darstellung Bitwise-Operator Java Basics - Anfänger-Themen 10
M binäre Suche im Intervall Java Basics - Anfänger-Themen 6
M binäre Suche Java Basics - Anfänger-Themen 4
amelie123456 Lineare Suche / Binäre Suche Java Basics - Anfänger-Themen 2
Cassy3 Binäre Bäume Rekursiv durchlaufen und bestimmte Elemente Zählen Java Basics - Anfänger-Themen 6
K Warum ist die binäre Suche bei der verketteten Liste nicht so effektiv? Java Basics - Anfänger-Themen 3
RudiRüssel Binäre Suche, unsortiert, lokales Maximum Java Basics - Anfänger-Themen 15
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
S Binäre-Suche bei unsortierten Daten Java Basics - Anfänger-Themen 7
S binäre semaphore Java Basics - Anfänger-Themen 4
L Binäre Suche mit Comparator Java Basics - Anfänger-Themen 5
Aprendiendo Gibt es in der JAVA-API eine Funktion, die eine Dezimalzahl in eine binäre Zahl umwandelt? Java Basics - Anfänger-Themen 8
H Erste Schritte Binäre Suche Java Basics - Anfänger-Themen 37
A Binäre Addition Java Basics - Anfänger-Themen 15
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
L Binäre Suche Java Basics - Anfänger-Themen 2
N Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen... Java Basics - Anfänger-Themen 6
B Binäre Suche - Junit Test Java Basics - Anfänger-Themen 6
J Binäre Suche eines Array Java Basics - Anfänger-Themen 5
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Binäre Suche in einem String Array Java Basics - Anfänger-Themen 10
V Binäre Suchbäume Java Basics - Anfänger-Themen 1
M Binäre Suche Fehler überall =( Java Basics - Anfänger-Themen 2
M Compiler-Fehler Binäre Zahlen in Dezimalzahlen umrechnen Java Basics - Anfänger-Themen 3
K binäre Suchbäume Java Basics - Anfänger-Themen 3
D Binäre Suche für Integerarray in rekursiver Funktion Java Basics - Anfänger-Themen 5
A Binäre Addition Java Basics - Anfänger-Themen 5
W Compiler-Fehler Binäre Suche Java Basics - Anfänger-Themen 2
S Multi-Threaded Binäre Suche Java Basics - Anfänger-Themen 29
A Binäre Suche Java Basics - Anfänger-Themen 2
W Binäre Suche Java Basics - Anfänger-Themen 8
E Binäre Bäume Java Basics - Anfänger-Themen 7
O String Binäre Suche Java Basics - Anfänger-Themen 6
M Binäre Suche, Elemente einfügen Java Basics - Anfänger-Themen 2
0x7F800000 wie pack ich komplette objekte in binäre dateien? Java Basics - Anfänger-Themen 4
A Binäre Suche; Java Basics - Anfänger-Themen 6
M binäre Daten als Double einlesen Java Basics - Anfänger-Themen 22
M binäre daten einlesen Java Basics - Anfänger-Themen 2
G Binäre Suchbaum + Erstellung des Programmes Java Basics - Anfänger-Themen 4
R Binäre logische Operatoren Java Basics - Anfänger-Themen 21

Ähnliche Java Themen

Neue Themen


Oben