Potenzieren mit 3/4?

[Marius S. (lupin)]

Ich suche nach einem Ansatz, wie man x^3/4 synthesefähig berechnen kann.
Diese Berechnung ist für MP3-Dekodierung notwendig (Requantisierung).

Ist erst mal rein akademisch und ich will nur sehen was es für Verfahren 
gibt. Eingangswerte sind Integers im Bereich -8206 bis 8206 aus dem 
Huffman-Dekoder (an dem ich gerade arbeite).

Ein allgemeiner Algorithmus welchen man auf beliebige Potenzen anpassen 
kann wäre natürlich auch interessant.

[Josef G. (bome)]

x^(3/4) = sqrt ( sqrt (x^3) )

[Josef G. (bome)]

Berechnung mittels Dualdarstellung des Exponenten:

x^(b3b2b1.a1a2a3) = B3*B2*B1*A1*A2*A3

falls b3=0: B3=1    falls b3=1: B3=x^4
falls b2=0: B2=1    falls b2=1: B2=x^2
falls b1=0: B1=1    falls b1=1: B1=x^1
falls a1=0: A1=1    falls a1=1: A1=sqrt(x)
falls a2=0: A2=1    falls a2=1: A2=sqrt(sqrt(x))
falls a3=0: A3=1    falls a3=1: A3=sqrt(sqrt(sqrt(x)))

[Josef G. (bome)]

Josef G. schrieb:
> x^(3/4) = sqrt ( sqrt (x^3) )
oder x^(3/4)=(sqrt(sqrt(x)))^3

Marius S. schrieb:
> Eingangswerte sind Integers im Bereich -8206 bis 8206
x^a mit nicht ganzzahligem a setzt positives x voraus.

[Marius S. (lupin)]

Ich habe mich vertan, man muss natuerlich mit 4/3 potenzieren fuer 
MP3...

Das man das ganze beliebig umschreiben kann ist klar.
Geht auch als
sqrt(x * sqrt(x))
oder
2^((4/3) * log2(x))

Nur bringt mich das fuer die Berechnung nicht viel weiter, oder?
Und zwei Wurzeloperationen zu verschachteln kann auch nicht der 
Weissheit letzter Schluss sein :)

Das die Eingangswerte positiv sein muessen ist auch klar. Deswegen 
werden die Ausgangsdaten des Huffman-Dekoders als Signed magnitude 
ausgegeben.

Ich denke mal es wuerde auf eine LookUP-Tabelle und Interpolation heraus 
laufen. Aber da gibt es sicherlich noch schlauere Ansaetze.

[joe (Gast)]

y = exp(4/3 * log(x)) oder y = exp(4 * log(x) / 3)

[Josef G. (bome)]

4/3 = 1.01010101 und dann mit dieser Methode:
Josef G. schrieb:
> Berechnung mittels Dualdarstellung des Exponenten

[Falk S. (falkschilling)]

Wenn du eh nen Dividierer hast, kannst du unter Umständen behelfen. 
Schau dir mal folgendes Skript an, dort werden einige Verfahren 
vorgestellt, die sich gut für FPGA-Implementierungen eignen.

http://users.minet.uni-jena.de/~nez/rechnerarithmetik_5/folien/Rechnerarithmetik.2008.18.handout.pdf

[Marius S. (lupin)]

Josef G. schrieb:
> 4/3 = 1.01010101 und dann mit dieser Methode:
> Josef G. schrieb:
>> Berechnung mittels Dualdarstellung des Exponenten

Wie man 4/3 als binaer darstellt verstehe ich. Das ist ja schoen und 
gut, aber wie soll ich das sqrt() realisieren? Und dann auch noch 
verschachtelt. Oder verstehe ich da was nicht?

[Jürgen S. (engineer)]

Wenn Du nur die dritte Wurzel brauchst, kannst Du das platzsparend über 
die heron'sche Schätz-Iterationsmethode machen. Wenn es genau und 
schnell gehen soll, dann ein statische Wurzelverfahren auf der Basis der 
Logarithmus. Das kann mit einer binären ln-Funktion oder etwas langsamer 
und platzsparender mit dem CORDIC gemacht werden. Ich würde den 
Logarithmus auf der Basis 2 bilden und dann durch ln(2) dividieren und 
dabei gleich das X4 mit ins Spiel bringen. Wäre einmal Cordic und eine 
anschliessende skalierte Multiplikation. Dies wäre insbesondere dann die 
für Dich passende Lösung wenn Du, wie Du ja andeutest, auch andere 
Operationsfaktoren benutzen willst.

Solange die beteiligten Operanden für die jeweilige Berechung statisch 
sind, lassen sie sich entweder in die ln-Operation oder die 
anschliessende Skalierung einrechnen.

[Josef G. (bome)]

Marius S. schrieb:
> wie soll ich das sqrt() realisieren?

So könnte es gehen:

Setze zunächst Ergebnis = 0.

Setze beim Ergebnis versuchsweise das höchste Bit auf 1.
Bilde das Quadrat. Teste ob dieses größer ist als x.
Wenn ja: lösche die 1 im Ergebnis wieder, wenn nein: lasse sie stehen.

Setze beim Ergebnis versuchsweise das nächste Bit auf 1.
Bilde das Quadrat. Teste ob dieses größer ist als x.
Wenn ja: lösche die 1 im Ergebnis wieder, wenn nein: lasse sie stehen.

Und so fort, bis alle Bits des Ergebnisses feststehen.

Beim Berechnen des Quadrats in jedem Schritt nütze man aus, dass
man das Quadrat im vorherigen Schritt bereits berechnet hat
und verwende (a+b)^2 = a^2 + 2*a*b + b^2

> Und dann auch noch verschachtelt.
sqrt(x) ausrechen. Vom Ergebnis wieder sqrt( ) ausrechnen,
und so fort. Wo ist das Problem?

Das Verfahren taugt für beliebige Exponenten. Wenn man
nur x^(4/3) braucht, mag es etwas besseres geben.

[Duke Scarring (Gast)]

Marius S. schrieb:
> wie soll ich das sqrt() realisieren?
http://www.lothar-miller.de/s9y/archives/73-Wurzel-in-VHDL.html

Duke