SitePoint Sponsor

User Tag List

Results 1 to 22 of 22
  1. #1
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Question How to quickly find nth root of x??

    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

  2. #2
    Prolific Blogger silver trophy Technosailor's Avatar
    Join Date
    Jun 2001
    Location
    Before These Crowded Streets
    Posts
    9,446
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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 Code:
    <?php
    echo sqrt(4);
    //Returns 2
    ?>
    Aaron Brazell
    Technosailor



  3. #3
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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...

  4. #4
    SitePoint Wizard Mincer's Avatar
    Join Date
    Mar 2001
    Location
    London | UK
    Posts
    1,140
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Sketch
    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 Code:
    <?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*
    Last edited by Mincer; Apr 3, 2003 at 06:46.

  5. #5
    SitePoint Member panda's Avatar
    Join Date
    Mar 2003
    Location
    Melbourne, Australia
    Posts
    19
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Using pow() to find the nth root of x

    Quote Originally Posted by Sketch
    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)

    Quote Originally Posted by Sketch
    Sounds like you need sqrt()
    sqrt() won't help if you want to find, for example, the cube root of x

  6. #6
    SitePoint Member panda's Avatar
    Join Date
    Mar 2003
    Location
    Melbourne, Australia
    Posts
    19
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Newton-Raphson root finding

    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?

  7. #7
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  8. #8
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    does anyone know why bcpow($number, (1/2)); returns 1?

  9. #9
    SitePoint Wizard silver trophy redemption's Avatar
    Join Date
    Sep 2001
    Location
    Singapore
    Posts
    5,269
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  10. #10
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    hmm... is there a way to bypass it? possibly make a my own function that does it? =/

  11. #11
    SitePoint Wizard silver trophy redemption's Avatar
    Join Date
    Sep 2001
    Location
    Singapore
    Posts
    5,269
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  12. #12
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    ok, thanks for your help!

  13. #13
    SitePoint Wizard silver trophy redemption's Avatar
    Join Date
    Sep 2001
    Location
    Singapore
    Posts
    5,269
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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).

  14. #14
    No. Phil.Roberts's Avatar
    Join Date
    May 2001
    Location
    Nottingham, UK
    Posts
    1,142
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)




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

  15. #15
    chown linux:users\ /world Hartmann's Avatar
    Join Date
    Aug 2000
    Location
    Houston, TX, USA
    Posts
    6,455
    Mentioned
    11 Post(s)
    Tagged
    0 Thread(s)
    Couldn't you just see what root they wanted to find and take the pow() of "1/the root they want"??

  16. #16
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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...

  17. #17
    chown linux:users\ /world Hartmann's Avatar
    Join Date
    Aug 2000
    Location
    Houston, TX, USA
    Posts
    6,455
    Mentioned
    11 Post(s)
    Tagged
    0 Thread(s)
    What about declaring the variable and doing something like:

    PHP Code:
    <?
    $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.

  18. #18
    SitePoint Wizard Mincer's Avatar
    Join Date
    Mar 2001
    Location
    London | UK
    Posts
    1,140
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Hartmann
    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.

  19. #19
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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!

  20. #20
    chown linux:users\ /world Hartmann's Avatar
    Join Date
    Aug 2000
    Location
    Houston, TX, USA
    Posts
    6,455
    Mentioned
    11 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Mincer
    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

  21. #21
    SitePoint Wizard silver trophy redemption's Avatar
    Join Date
    Sep 2001
    Location
    Singapore
    Posts
    5,269
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by 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.
    Heh at least in the process we learnt that bcpow() has problems.

  22. #22
    SitePoint Zealot
    Join Date
    Nov 2002
    Posts
    194
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •