Pseudocode Exponentiation fehlerhaft

kutschke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 16. Apr 2009 10:39

Pseudocode Exponentiation fehlerhaft

Beitrag von kutschke »

Hi! Der Pseudocode zur schnellen Exponentiation ist fehlerhaft. Statt result in jedem Schritt zu quadrieren, muss tatsächlich x quadriert werden, und zwar nach der Zeile mit result = result * x, noch im for-Block aber ausserhalb des if-Blocks.
Sonst wird nämlich result elend oft quadriert und wächst deutlich mehr, als man das will. Bsp: 3^3 = 1 (NACH OVERFLOW!!)

Benutzeravatar
Michl
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 293
Registriert: 12. Apr 2009 08:53
Wohnort: Darmstadt

Re: Pseudocode Exponentiation fehlerhaft

Beitrag von Michl »

Bei mir hat der Pseudocode einwandfrei funktioniert.
Es wird ja am Anfang immer nur 1 quadriert, solange bis einmal mit x multipliziert wurde.

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Pseudocode Exponentiation fehlerhaft

Beitrag von ivoch »

Ja, der Pseudocode ist schon richtig. Liest euch den Wikipedia-Artikel zur Binären Exponentiation - dort ist das Verfahren sehr gut erklärt.

Übrigens, man kann den Algorithmus im Übungsblatt noch etwas mehr verfeinern, so dass die for-Schleife noch weniger als 32 mal wiederholt werden muss (und somit auch weniger als 64 Multiplikationen notwendig sind). Mit unserem 32-bit MIPS, wenn nur Integer potenziert werden müssen, kann man n=4 setzen (warum?) und dann werden höchstens 8 Multiplikationen ausgeführt.

Antworten

Zurück zu „Archiv“