algorithmus von potenzen

anfaenger890

ich muss einen algorithmus entwerfen, sodass man die potenz x^n ausrechnen kann. dabei ist x eine gleitkommazahl und n eine natürliche zahl

ICH DARF NICHT DIE POW-FUNKTION VERWENDEN!

bitte helft mir! ich komme bei diesem pap nicht weiter...

SeppJ

Wie würdest du es denn mit einem Taschenrechner machen, der nur /,*,- und + kennt?

edit: Und ein paar Speichertasten darfst du auch annehmen bei dem Taschenrechner.

edit2: Offtopic: Kennt man solche Taschenrechner heute eigentlich noch oder ist es unvorstellbar, dass das mal der normale Funktionsumfang war?

anfaenger890

also das hier ist mein bisheriger algorithmus:

start

ausgabe: gleitkommazahl x und natürliche zahl n eingeben

x einlesen, n einlesen

i = 0

5. y = x

x = y * x

i < n?, falls ja i++, weiter bei 5.
falls nein, gebe x aus.

stop

stimmt das soweit? ich komme immer mit der rechnung durcheinander

Swordfish

@ot edit2: Speichertasten, wtf!? Ich habe ihn geliebt: TI 92

Topic, Rekursiv: x[h]n[/h] = x * x[h]n-1[/h] | x[h]0[/h] = 1

SeppJ

anfaenger890 schrieb:

also das hier ist mein bisheriger algorithmus:

start

ausgabe: gleitkommazahl x und natürliche zahl n eingeben

x einlesen, n einlesen

i = 0

5. y = x

x = y * x

i < n?, falls ja i++, weiter bei 5.
falls nein, gebe x aus.

stop

stimmt das soweit? ich komme immer mit der rechnung durcheinander

Probier's doch mal aus. Entweder auf einem Blatt Papier oder gleich als Computerprogramm.

dimiKL

Hier 2 Lösungen: für nicht-negative n
Komplexität O(n)

int i=0;
double y = 1;
while(i < n) {
  y *= x;
  i++;
}

Oder noch schneller: O(1), genauer O(31)

double y=1;
double y1=x;
while(n != 0) {
  if( (n&0x1) !=0 ) {
    y *= y1;
  }
  y1 *= y1;
  n >>= 1;  //rechtes Bit loeschen
}

Bashar

dimiKL schrieb:

Oder noch schneller: O(1), genauer O(31)

O(log n) meinst du wohl. Ansonsten ist dein erstes Beispiel auch "O(1), genauer O(2147483647)".

Letzteres ist O(log(n)), nicht O(1). Trotzdem besser.

dimiKL

Stimmt. O(log n).