potenzieren

Gucky

hallo leute,

ich wird gerne mal wissen warum (1 << 2) 2^2 entspricht und wie man mit dem shift-operator z.B, 14^37 schreiben kann.

gruß gucky

drakon

Das ganze funktioniert auf binärer Ebene, da der Shift Operator auf binärer Ebene arbeitet.

1 ist ja sowas wie: 000...0001. Wenn du das jetzt um eins nach links shiftest bekommst du: 000...0010. Also 2. Noch einmal und du hast: 000...0100.

Mit dem Shift Operator kannst du also nur mit 2 multiplizieren.

krümelkacker

Gucky schrieb:

ich wird gerne mal wissen warum (1 << 2) 2^2 entspricht

Aus demselben Grund, warum das anhängen einer Null in der Dezimaldarstellung einer Multiplikation mit Zehn entspricht. Im Binären ist eine Eins gleich 1 und eine Zwei gleich 10 und eine Vier gleich 100, u.s.w. "<<2" heißt quasi: "Binärdarstellung rechts mit 2 Nullen auffüllen".

Gucky schrieb:

und wie man mit dem shift-operator z.B, 14^37 schreiben kann.

Gar nicht. 14 ist keine Zweierpotenz.

Edit:
Aha. Nen Miller-Rabin Test soll das wohl werden. Dann baue Dir doch mit dem "Square-And-Multiply"-Algorithmus folgende Funktion:

long potenzmod(long basis, long exponent, long modulus)
{
  ...
}

Die Idee dabei ist, dass
x^2b mod n = (x² mod n)^b mod n
und
x^2b+1 mod n = x*((x² mod n)^b mod n) mod n
gilt (nach den Potenzgesetzen)....

SeppJ

Gucky schrieb:

ich wird gerne mal wissen warum (1 << 2) 2^2 entspricht

Denk dir eine 1.
Und nun denk dir eine binäre 1. Ich helf dir mal, es ist
1
Und nun denk sie dir um 1 nach links geshiftet (1<<1):
10
Das ist 2
Und nun denk dir dies um 1 geshiftet (1<<2)
100
Das ist 4
Wie du siehst sind das immer 1 gefolgt von ein paar Nullen. Und das kannst du dir ganz einfach ausrechnen, sind genua die Potenzen der 2.

und wie man mit dem shift-operator z.B, 14^37 schreiben kann.

Gar nicht. Du hast deine Antwort für diese mathematische Problem bereits in deinem anderen Thread bekommen. Frag bitte nicht mehrmals, bloß weil dir die Antwort nicht passt.

padreigh

Gucky schrieb:

ich wird gerne mal wissen wie man mit dem shift-operator 14^37 schreiben kann

GanzGrosseZahl = eigenePOWfunktFuerGanzGrosseZahlUndInt(( (1<<3)+(1<<2)+(1<<1),(1<<5)+(1<<2)+(1<<0) ));

Wenns dir spass macht schau mal in <limits> und guck ob 14^37 in ein long double reinpasst ... wenn ja, nimm einfach eine std::pow() dafür ...

SeppJ

padreigh schrieb:

Wenns dir spass macht schau mal in <limits> und guck ob 14^37 in ein long double reinpasst ... wenn ja, nimm einfach eine std::pow() dafür ...

Das passt zwar ganz locker (auch in double und float), aber für ihn ist das ein schlechter Rat (was du an dieser Stelle nicht wissen kannst), denn aus seinem anderen Thread geht hervor, dass er damit Ganzzahlarithmetik machen will.

Belli

krümelkacker schrieb:

Gucky schrieb:

und wie man mit dem shift-operator z.B, 14^37 schreiben kann.

Gar nicht. 14 ist keine Zweierpotenz.

Das macht nix. Entscheidend ist, daß 37 keine Zweierpotenz ist.

SeppJ

Belli schrieb:

krümelkacker schrieb:

Gucky schrieb:

und wie man mit dem shift-operator z.B, 14^37 schreiben kann.

Gar nicht. 14 ist keine Zweierpotenz.

Das macht nix. Entscheidend ist, daß 37 keine Zweierpotenz ist.

Jetzt bin ich aber neugierig, wie du 3^2 mittels shift-Operatoren darstellst.

Da man für 14³⁷ mindestens einen 141-Bit-Integer bräuchte, wirst du sowieso eine Big-Integer-Bibliothek benutzen müssen. Auch in einen long double kriegst du so was nicht mehr ohne Präzisionsverlust rein.

@SeppJ:

int x = 18 >> 1;

:p

Belli

SeppJ schrieb:

Belli schrieb:

krümelkacker schrieb:

Gucky schrieb:

und wie man mit dem shift-operator z.B, 14^37 schreiben kann.

Gar nicht. 14 ist keine Zweierpotenz.

Das macht nix. Entscheidend ist, daß 37 keine Zweierpotenz ist.

Jetzt bin ich aber neugierig, wie du 3^2 mittels shift-Operatoren darstellst.

Tja, jetzt, wo Du es so sagst ..., ich auch ...
Wahrscheinlich meinte ich sowas wie: x * 2^n

Gucky

so hier mein quelltext. das problem ist jetzt noch, dass immer 0 ausgegeben wird und ich kann char binear nicht in der eingabeauforderung anzeigen.

#include <iostream>
#include <cmath>

int main()
{
	int potenz, zahl, rest = 1, i = 8, j, ergebnis = 1;
	char binaer[8];

	std::cout << "Potenz: ";
	std::cin >> potenz;
	std::cout << "Exponent: ";
	std::cin >> zahl;

	while (zahl != 0)
	{
		rest = zahl % 2;
		zahl = (zahl - rest) / 2;

		binaer[--i] = rest;
	}

	for (j = 0; j <= 8; ++j)
	{
		if (binaer[j] == 0)
		{
			ergebnis = (ergebnis * ergebnis);
		}
		else
		{
			ergebnis = (ergebnis * ergebnis) * (potenz * binaer[j]);
		}

	}

	std::cout << ergebnis;

	return 0;
}

vielleicht könnte mir jemand sgen wo mein fehler ist

krümelkacker

Es ist nicht ganz klar, was das Programm machen soll. Du könntest das deutlicher machen, indem Du die Hauptfunktionalität aus main entfernst, in eine Funktion packst und dieser Funktion einen geeigneten Namen gibst. Es sieht ein bisschen nach einer square-and-multiply Implementierung aus. Aber so ein binaer-Array braucht man eigentlich nicht. Das schafft man auch in einer einzigen Schleife oder per Rekursion.

Folgende Probleme sehe ich:
Das Array mag zu kurz sein (wenn exponent>=256).
Das Array wurde nicht richtig initialisiert.
Du läufst in der Schleife mit j von 0 (einschließlich) bis 8 (einschließlich), obwohl das Array nur 8, nicht 9 Elemente hat und einige Elemente nicht initialisiert wurden.

Versuch es nochmal zu schreiben, ohne das binaer-Array. Probier's mal mit Rekursion. Das ist gar nicht so schwer per Rekursion, denn

/  1         falls exponent==0
mypow(base,exponent)  -->   |  base      falls exponent==1
                            \  x         sonst

wobei x = mypow(base*base,exponent/2) * mypow(base,exponent%2);

kk

Gucky

laut wikipedia braucht man aber die binärdarstellung des exponentens, wenn man den algorithmus nimmt:

// Berechnet x^c
// b ... binäre Darstellung von c
// res ... Resultat der Berechnung

function bin_exp(x,b)
res = 1
for i = n..0
res = res^2 * x^{b_i}
end-for
return res
end-function

volkard

Zwei mathematische Probleme:
- ergebnis = (ergebnis * ergebnis) * (potenz * binaer[j]);
haut Dich immer wieder runter auf 0, wenn mal binaer[j]==0 ist
- die Schleifendrehrichtungen waren nicht zueinander passend.
- ergebnis = (ergebnis * ergebnis) darf nur passieren, solange noch Bits da sind. Deswegen das trisckreiche j > i.

Ein programmierproblem:
- Indexgrenzenüberschreitung. Ich habe es nicht gelöst.

Meine minimalinvasive Lösung:

#include <iostream>
#include <cmath>

int main()
{
    int potenz, zahl, rest = 1, i = 8, j, ergebnis = 1;
    char binaer[8];

    std::cout << "Potenz: ";
    std::cin >> potenz;
    std::cout << "Exponent: ";
    std::cin >> zahl;

    while (zahl != 0)
    {
        rest = zahl % 2;
        zahl = (zahl - rest) / 2;

        binaer[--i] = rest;
    }

    for (j = 8; j > i; --j)
    {
        if (binaer[j] == 0)
        {
            ergebnis = (ergebnis * ergebnis);
        }
        else
        {
            ergebnis = (ergebnis * ergebnis) * (potenz);
        }

    }

    std::cout << ergebnis;

    return 0;
}

Gucky

ok danke

@ krümelkacker: du sgat das so leicht dass es mit rekursion so einfach ist. so richtig verstehen tuh ich das nicht und gehen tut es auch nicht. vielleicht könntest du es mir nich einmal genauer erklären

int mypow(int base, int exponent)
{
	int x;
	x = mypow(base * base, exponent / 2) * mypow(base, exponent % 2);

	return x;
}

krümelkacker

Gucky schrieb:

laut wikipedia braucht man aber die binärdarstellung des exponentens, wenn man den algorithmus nimmt

... man muss sie nur nicht vorher explizit ausrechnen. Beispiel:

long recursive_square_and_multiply(long base, int exponent)
{
  if (exponent<=0) return 1;
  if (exponent==1) return base;
  return recursive_square_and_multiply(base*base,exponent/2)
       * recursive_square_and_multiply(     base,exponent%2);
}

long iterative_square_and_multiply(long base, int exponent)
{
  long result = 1;
  while (exponent>0) {
    if (exponent % 2) result *= base;
    exponent /= 2;
    base = base*base;
  }
  return result;
}

volkard

@kk, das rekursive ist total klasse, aber mach es noch rund, so daß man sich in den code verlieben kann. irgendwie ruckelt es noch beim lesen.

volkard

@Gucky: Supi, daß du die rekursive Version magst und da einsteigen willst. Ganz ganz am Ende wird zwar eine iterative Version einen Mikrotick schneller sein, aber die kann kein Sterblicher basteln, ohne über die Rekursion voll viel dazuzulernen, fürchte ich.
Daumen hoch und viel Spaß