Results 1 to 2 of 2
  1. #1
    adamkoe is offline Member
    Join Date
    Aug 2011
    Posts
    1
    Rep Power
    0

    Default BigInteger nth root

    Dear Anybody!

    Could someone help me! I need a function, which give back the nth root of a BigInteger. I use one, that makes the root with the newton method, but it is too slow for my algorithm. Some ideas?

    Thanks!

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,023
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by adamkoe View Post
    Dear Anybody!

    Could someone help me! I need a function, which give back the nth root of a BigInteger. I use one, that makes the root with the newton method, but it is too slow for my algorithm. Some ideas?

    Thanks!
    If you apply that naive Newton (Raphson) method you're using to many calculations per step; consider the following method:

    Let xl and xh be such that xl**n <= x <= xh**n (** is the power operator)
    A better estimation would be (xl+xh)>>1

    Continue the above steps until you have found the n-th root or xh-xl <= 1

    Calculating the n-th power can be done as follows (the example uses simple ints)

    Java Code:
    int pow(int x, int n) {
       if (n == 0) return 1;
       if (n == 1) return x;
       int r= pow(x, n>>1);
       int t= r;
       if ((n&1) == 1) r*= x;
       return t*r;
    }
    kind regards,

    Jos
    Last edited by JosAH; 08-29-2011 at 10:24 AM. Reason: typo ...
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. BigInteger value of
    By ccie007 in forum New To Java
    Replies: 2
    Last Post: 09-26-2010, 03:46 PM
  2. convert BigInteger
    By bobo67 in forum New To Java
    Replies: 1
    Last Post: 09-01-2010, 02:00 PM
  3. BigInteger
    By windows.login in forum New To Java
    Replies: 8
    Last Post: 07-13-2010, 01:10 PM
  4. very new... Biginteger problems
    By willemien in forum New To Java
    Replies: 6
    Last Post: 05-02-2010, 03:17 PM
  5. how to convert from BigInteger to Hex
    By nanaji in forum Advanced Java
    Replies: 10
    Last Post: 05-22-2008, 12:44 PM

Posting Permissions

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