How to quickly find nth root of x??

[LeeTaxx0r]

ok, I've got a problem I can't seem to figure out...

I need to find the nth root of x quickly. At the moment I'm stuck with going through all the combonations and usig trial and error, which obviously is extremely ineffecient.

I tried $root = pow($number,1/$power); and it works, but the numbers I'm using are too large and it causes some really bad innaccuracy.

I also tried the same thing using bcpow(); but for some reason it just returns 1 every time.

I would really appreciate your help if you know how to get it to work, I've been racking my brain all night now...lol

[Technosailor]

well if what you said is what you're looking for, then what you were trying to do with pow() is wrong because that will return an exponent.

Sounds like you need sqrt()

<?php
echo sqrt(4);
//Returns 2
?>

[LeeTaxx0r]

x^(1/2) is the square root of x.
I would use sqrt except I need to do this with cube roots, 4th, 5th 6th and so on...

[Mincer]

well if what you said is what you're looking for, then what you were trying to do with pow() is wrong because that will return an exponent.

Sounds like you need sqrt()

<?php
echo sqrt(4);
//Returns 2
?>

sqrt() isn't going to be much use if you want the cubed root of something though. [img]images/smilies/wink.gif[/img]

EDIT: beaten to it. [img]images/smilies/smile.gif[/img]

EDIT2: I'm not sure why you would have problems, your logic is good. Perhaps the reason that it doesn't work for the binary calculations is that the 'power' number is going to be a decimal and it can't be seen as a string. *shrug*

[panda]

well if what you said is what you're looking for, then what you were trying to do with pow() is wrong because that will return an exponent.

Using pow() IS a valid method, since the nth root of x can be expressed as x to the power of 1/n eg. sqrt(2) === 2^(1/2)

Sounds like you need sqrt()

sqrt() won't help if you want to find, for example, the cube root of x

[panda]

If j is an approximation to the nth root of x, then (j+x/j)/n is a better approximation.

You could use this rule to develop an iterative approach to approximating the nth root of x to a given degree of accuracy.

Psuedo-code:

j = x/n; /* Doesn't have to be this, could be j = 1, j = x etc */

while ( absolute_value(j^n - x) > ACCURACY_CONST) {
j = (j + x/j)/n;
}

You may still have problems with rounding though...how large are the numbers you're using?

[LeeTaxx0r]

I'm going to be using numbers with prolly at least a few hundred digits. Idealy the more digits the better for what I have in mind but it's all going to be limited by my CPU power in the end.

[LeeTaxx0r]

does anyone know why bcpow($number, (1/2)); returns 1?

[redemption]

Apparently, bcpow() rounds it's 2nd argument (the power to raise the number to) to the nearest integer. anything less than 1 seems to have been rounded off to 0.

Trying it with something bcpow(x, 2.2, 10) also returns the x to the power of 2.

[LeeTaxx0r]

hmm... is there a way to bypass it? possibly make a my own function that does it? =/

[redemption]

I don't know really. I just submitted a "user-contributed note" at php.net for that.

Your best bet would be to look at the Newton-Raphson method that panda suggested in post #6.

[LeeTaxx0r]

ok, thanks for your help!

[redemption]

Not a problem

I found a site with a clearer explanation of the Newton-Raphson algorithm as well as a possibly helpful implementation (in Java) at the bottom of the page (do a find for Putting it All Together).

[Phil.Roberts]

This brings back all my college math nightmares.....

[Hartmann]

Couldn't you just see what root they wanted to find and take the pow() of "1/the root they want"??

[LeeTaxx0r]

That's what I was planning to do but using pow($number, 1/$root); creates innaruacies when you're using number that are over 100 digits long.

bcpow(); is supposed to be the same(or at least very similar) except it uses arbitrary precision, so that using huge numbers doesn't cause innacuracy. However because it rounds the second argument you can't do that.

I'm going to try and find a workaround or something, any ideas would be great cuz I'm still pretty stumped on this...

[Hartmann]

What about declaring the variable and doing something like:

<?
$var = 3;

$newVar = (float) 1/$var;
echo $newVar;

$num = 2;
$newNum = pow($num, $newVar);
echo "<P>".$newNum;
?>

That code above returned 1.2599210498949 as the final answer, which according to my graphing calculator is correct.

[Mincer]

That code above returned 1.2599210498949 as the final answer, which according to my graphing calculator is correct.

But "2" isn't really a number over 100 digits long though.

[LeeTaxx0r]

hmm... either it's working or I just need some sleep...lol

I just tried using the normal pow() with a very large number and it seems to work fine. weird.... oh well, lol I'll reply again if I run into a problem.

and of course thanks!

[Hartmann]

But "2" isn't really a number over 100 digits long though.

It does work with a 100 digit number though, I just tried it

[redemption]

hmm... either it's working or I just need some sleep...lol

I just tried using the normal pow() with a very large number and it seems to work fine. weird.... oh well, lol I'll reply again if I run into a problem.

Heh at least in the process we learnt that bcpow() has problems.

[LeeTaxx0r]

and actually, I ran into a problem. I was able to make a fix but it kinda hurts performance.

Once the numbers get big enough the accuracy does indeed go down. As in, multiple numbers will claim to be products of the same exponentials.

I fixed this by as a last step in the process comparing them and checking to make sure that it's accurate. It's faster than my original plan but it would be better if they change that thing in bcpow() :P