Ersatz für pow()?

Jester schrieb:

Das ist doch dann gerade Wurzelziehen

a^(1/b) = b. Wurzel von a. für ganzzahliges b und a>=0.

also das a^(1/b) = b musst Du mir genauer erklären?

ah ok jetzt verstanden ate wurzel von b aber das haben wir schon weiter oben festgestellt

Walli

Yogib43r schrieb:

Jester schrieb:

Das ist doch dann gerade Wurzelziehen

a^(1/b) = b. Wurzel von a. für ganzzahliges b und a>=0.

also das a^(1/b) = b musst Du mir genauer erklären?

Nein, es ist die b-te Wurzel von a usw.

Richie_Gecco

Hi!

Nur mal aus neugier, was für ein Datentyp willst Du eigentlich verwenden? Das sieht mir sehr stark danach aus, dass Du floats benötigst. Oder einen solchen Datentyp emulieren musst.

Grüße
Richie

Wie gesagt: float ist nicht drin, ich kann also allenfalls mit um den Faktor 1000 größeren Zahlen rechnen, wenn Genauigkeit gefragt ist.

TGGC

Übrigens kann man auch Wurzel "periodisch" berechnen. Wenn du also z.b. einen Tabelle von 64 - 256 hast, dann kannst du z.v. auch sqrt( 62 ) = sqrt( 62 * 4 ) / 2, oder sqrt( 270 )= sqrt( 270 / 4 ) * 2 berechnen.

Bye, TGGC

@walli ja hatte mich vertippt
@TGGC für 2. und 3. Wurzel ist es einfach für den Rest wird es schwieriger

Prinzipiell kannst Du Dir selbst den Datentyp float erstellen. Und auch entsprechende Rechenoperationen selbst schreiben aber das ist für einen pow() ziemlich viel Aufwand. Ich bin mir sicher, dass Du den pow() nicht unbedingt brauchst und Dein Problem auch ohne einen pow() lösen kannst greetz...

dooya

Mmmh, könnte man das nicht mit "brute force" lösen?

Mal in MatLab-Code:

function [x] = root(a,b) 
%%% oder auch: a^(1/b)
x = 1;
erg = 1;
while (erg < a)
   x= x+1;
   erg = x;
   for i=1:b-1 
      erg = erg * x;
   end
end

Für ganzzahlige a und b, jeweils größer null, ergibt dieser Algorithmus ceil(a^(1/b)), also die auf die nächstgrößere ganze Zahl aufgerundete b-te Wurzel aus a.

Mit zunehmender Größe von a dürfte es allerdings, in Abhängigkeit von der Leistungsfähigkeit des Prozessors, notwendig sein, eine angemessene Heuristik für geeignete Startwerte von x zu finden.

volkard

dooya schrieb:

Mmmh, könnte man das nicht mit "brute force" lösen?

exakt.
zuerstmal nehmen wir festpunktarithmetik. also um den faktor 1000 vegrößerte werte und gewinnen dadurch genau drei nachkommastellen. naja, leiber ist mir natürlich der faktor 4096.

dann nehmen wir den trick von tggc und berechnen sqrt(x/4096):=sqrt(x)/64 und pow(x/4096,1/3):=pow(x,1/3)/16 und natürlich pow(x/4096,1/4):=sqrt(sqrt(x))/8.
pow(x/4096,1/5) ist noch unklar, vielleicht bruteforcen.
pow(x/4096,1/6):=sqrt(pow(x,1/3))/4.

und nu überlegen, wie das so mit den zahlen ist und ob man den rest nicht einfach bruteforcen kann. startwerte? vielleicht position des ersten gesetzen bits finden, also p=log2(x) und das durch b teilen und die wirzel liegt schonmal zwischen 1<<p und 1<<(p+1). (kann mich auch überall um kleinigkeiten vertun). bei den vielen möglichen exponenten, bieten sich tabellengucker nicht gerade an, um den startwert noch zu verbessern. was machen wir mit zwei startwerten und dem wissen, daß die gesuchte zahl irgendwo dazwischen liegt?

es bieten sich an: intervallschachtelung (natürlich mit fastexp). regula falsi. newton.

mal angenommen, wir reden über nen unsigned int mit 32 bits. dann ist der maximal sinnville exponent b gleich 31. für jedes b>31 ist pow(x,1/b) gleich 1 oder 0, und ob 1 oder 0 läßt sich bestimmt fix herausfinden).
außerdem sind 0 und 1 als b uninteressant.
also haben wir als b noch 2 3 4 5 ... 29 30 31
wenn wir annehmen, daß zweite und dritte wurzeln fein schnell gehen, und wir die auch benutzen wollen, um dicke wurzeln dünn zu machen, haben wir nur noch als problemfälle 5 7 11 13 17 19 23 25 29 31.
mal schauen, wie sich die 13. wurzel so anfühlt.
1^13=1
2^13=8192
3^13=1594323
4^13=67108864
4^13=1220703125
6^13=13060694016
also ist das ergebnis von pow(x,1/13) zwischen 0 und 5 und mit wenigen ifs ruck-zuck berechnet.
tabelle, tabelle, tabelle!
machen wir auch für b=5 ne tabelle?
85^5=4437053125
naja, die 85 wetr in der tabelle tun einem schon recht weh.
24^7=4586471424
8^11=8589934592

also erstmal feststellen, was wir bereits annehmen können.
ab exponent 11 wird tabellenguckerchen gemacht. ob mit linearer suche oder mit binary search, muß man noch rausfinden, hängt von auch der verteilung der eingangsdaten ab.
der exponent 2 bekommt natürlich die fertige lösung, wie man sie überall im netz findet.

// Integer square root by Halleck's method, with Legalize's speedup
	// Taken from http://www.cc.utah.edu/~nahaj/factoring/isqrt.c.html
	// C++-ified by Henkel

	// Load the binary constant 01 00 00 ... 00, where the number of
	// zero bits to the right of the single one bit is even,
	// and the one bit is as far left as is consistant with that condition.
	T squaredbit= (T(~0)>>1) & ~(T(~0)>>2);
	// This portable load replaces the loop that used to be here,
	// and was donated by legalize@xmission.com

	// Form bits of the answer.
	T remainder=x;
	T root=0;
	while (squaredbit > 0) {
		if(remainder>=(squaredbit|root)){
			remainder-=(squaredbit|root);
			root>>=1;
			root|=squaredbit;
		} 
		else{
			root>>=1;
		}
		squaredbit>>=2;
	}
	return root;

kannst du sowas auch aufbohren für die exponenten 3 und 5?

falls nicht, müßte man hier bruteforcen oder intervallschachten oder fixpunktiterieren, was mir alles nicht extrem behagt.

MamboKurt

ja also ich würde da so ran gehen und, wie schon des öfteren gesagt, meine eigene float-klasse schreiben und für diese klasse dann die funktionen exp (da a^b = exp(b*ln(a)) bereitstellen. da a ja immer ganzahlig ist kannst du ja irgendeine ln-funktion aus einer mathe-lib nehmen.
hab jetzt keine ahnung, wie das zu implementieren ist oder wie schwer das sein wird, aber ich glaube exp sollte nicht so kompliziert sein.

.MamboKurt