Quick n-th Square of BigInteger

Discussion in 'Java' started by Jan Burse, Jun 8, 2012.

  1. Jan Burse

    Jan Burse Guest

    Dear All,

    What is your favorite algorithm to compute the n-th Square of
    a BigInteger, i.e.

    Given: x, n
    Compute: y = max { z | z^n =< x }

    Bye
    Jan Burse, Jun 8, 2012
    #1
    1. Advertising

  2. On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <>
    wrote:

    >Dear All,
    >
    >What is your favorite algorithm to compute the n-th Square of
    >a BigInteger, i.e.
    >
    > Given: x, n
    > Compute: y = max { z | z^n =< x }


    Do you mean the integer part of the nth *root* of z given integer
    x and n?

    I do not have a favourite or even an algorithm. If I had to come
    up with something, I would probably try a first approximation with
    logarithms.

    Sincerely,

    Gene Wirchenko
    Gene Wirchenko, Jun 8, 2012
    #2
    1. Advertising

  3. Jan Burse

    Jan Burse Guest

    Quick n-th Root of BigInteger

    Gene Wirchenko schrieb:
    > On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <>
    > wrote:
    >
    >> Dear All,
    >>
    >> What is your favorite algorithm to compute the n-th Square of
    >> a BigInteger, i.e.
    >>
    >> Given: x, n
    >> Compute: y = max { z | z^n =< x }

    >
    > Do you mean the integer part of the nth *root* of z given integer
    > x and n?
    >
    > I do not have a favourite or even an algorithm. If I had to come
    > up with something, I would probably try a first approximation with
    > logarithms.
    >
    > Sincerely,
    >
    > Gene Wirchenko
    >


    Sorry, yes root, and z integer.
    Jan Burse, Jun 8, 2012
    #3
  4. Jan Burse

    markspace Guest

    Re: Quick n-th Root of BigInteger

    On 6/8/2012 1:36 PM, Jan Burse wrote:
    > Gene Wirchenko schrieb:
    >> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <>
    >> wrote:
    >>
    >>> Dear All,
    >>>
    >>> What is your favorite algorithm to compute the n-th Square of
    >>> a BigInteger, i.e.
    >>>
    >>> Given: x, n
    >>> Compute: y = max { z | z^n =< x }

    >>
    >> Do you mean the integer part of the nth *root* of z given integer
    >> x and n?


    > Sorry, yes root, and z integer.



    Positive integers? Do you want the complex roots too? ;-) You ask big
    questions Jan, but I think you need to ask them a little more thoughtfully.

    I'm confused about the max, the z |, and the =< x. Care to explain
    what those signify in your question? If you want something besides the
    real, positive nth root of A=z^n, what do you want? I think "nth root
    of A" is the correct phrasing, which leads to the wonder what the other
    mathematical verbiage signifies.
    markspace, Jun 8, 2012
    #4
  5. Jan Burse

    Jan Burse Guest

    Jan Burse schrieb:
    > Dear All,
    >
    > What is your favorite algorithm to compute the n-th Square of
    > a BigInteger, i.e.
    >
    > Given: x, n
    > Compute: y = max { z | z^n =< x }
    >
    > Bye


    Clarification:

    Given: x BigInteger positive non-zero, n int positive non-zero

    Compute: y BigInteger = max { z BigInteger | z^n =< x }

    (In words: y is the biggest BigInteger z such that
    z raised to the power of n is less or equal x)

    (Mathematically this is would be floor(root(x,n)))

    Bye
    Jan Burse, Jun 8, 2012
    #5
  6. Jan Burse

    Eric Sosman Guest

    On 6/8/2012 3:03 PM, Jan Burse wrote:
    > Dear All,
    >
    > What is your favorite algorithm to compute the n-th Square of
    > a BigInteger, i.e.
    >
    > Given: x, n
    > Compute: y = max { z | z^n =< x }


    (I'm assuming you mean n'th root, which is what your final
    line seems to imply.)

    It's not something I've found a need to do, so I have no
    "favorite" algorithm. For positive `x' I think I'd start
    by observing that

    x.bitCount()-1 <= lg(x) < x.bitCount()

    hence the lg() of the desired root is between

    floor((x.bitCount()-1)/n) <= lg(root) < ceil(x.bitCount()/n)

    From this you can get lower and upper bounds on the root itself,
    something like (just typed in free-hand)

    BigInteger lo = BigInteger.ONE.shiftLeft(
    Math.floor((x.bitCount()-1)/n));
    BitInteger hi = BigInteger.ONE.shiftLeft(
    Math.ceil(x.bitCount()/n));

    .... and then do a binary search between those extrema. (Looks like
    they'd differ by a factor of two usually, maybe a factor of four
    occasionally -- but I might be wrong about that.)

    Simplifications might be possible if `n' is known to be an
    integer.

    For negative `x' and odd integer `n' you could find the bounds
    for -x, negate and interchange them, and then do the same binary
    search.

    For negative `x' and `n' even or non-integer, I think you're
    out of luck.

    --
    Eric Sosman
    d
    Eric Sosman, Jun 8, 2012
    #6
  7. Re: Quick n-th Root of BigInteger

    markspace <-@.> wrote:
    (snip)
    >>> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <>


    >>>> What is your favorite algorithm to compute the n-th Square of
    >>>> a BigInteger, i.e.


    >>>> Given: x, n
    >>>> Compute: y = max { z | z^n =< x }


    (snip)
    >> Sorry, yes root, and z integer.


    > Positive integers? Do you want the complex roots too? ;-)
    > You ask big questions Jan, but I think you need to ask them
    > a little more thoughtfully.


    I will guess that the OP isn't a native English speaker, and
    is not translating so well.

    I had to look it up as I didn't know, .fm seems to be Micronesia.

    It looks like he wants the nth root rounded down to the next
    integer value.

    I do remember when first learning Fortran wondering why no
    ISQRT function.

    One possibility is to do exactly as written, binary search
    for the largest z such that z**n <= x. (No exclusive or operators
    are needed here.)

    -- glen
    glen herrmannsfeldt, Jun 8, 2012
    #7
  8. Jan Burse

    Jan Burse Guest

    Eric Sosman schrieb:
    > ... and then do a binary search between those extrema. (Looks like
    > they'd differ by a factor of two usually, maybe a factor of four
    > occasionally -- but I might be wrong about that.)


    Binary search would use (x.bitCount()-1)/n steps in the
    extrem, and in each step calculating pow(). Is this
    effective?
    Jan Burse, Jun 8, 2012
    #8
  9. Jan Burse

    Jan Burse Guest

    Re: Quick n-th Root of BigInteger

    glen herrmannsfeldt schrieb:
    > I will guess that the OP isn't a native English speaker, and
    > is not translating so well. I had to look it up as I didn't know,
    > .fm seems to be Micronesia.


    Ha Ha

    fastmail.fm = messagingengine.com
    Jan Burse, Jun 8, 2012
    #9
  10. Jan Burse

    Jan Burse Guest

    Re: Quick n-th Root of BigInteger

    markspace schrieb:
    > I'm confused about the max, the z |, and the =< x.


    For those who don't know, there exists a set builder notation:

    http://en.wikipedia.org/wiki/Set-builder_notation#Z_notation

    max is then a higher order function from a set to an element.

    Forgot where this is taught, in elementary school?

    Bye
    Jan Burse, Jun 8, 2012
    #10
  11. Jan Burse

    Eric Sosman Guest

    On 6/8/2012 5:19 PM, Jan Burse wrote:
    > Eric Sosman schrieb:
    >> ... and then do a binary search between those extrema. (Looks like
    >> they'd differ by a factor of two usually, maybe a factor of four
    >> occasionally -- but I might be wrong about that.)

    >
    > Binary search would use (x.bitCount()-1)/n steps in the
    > extrem, and in each step calculating pow(). Is this
    > effective?


    In light of your abusiveness in responding to other people who've
    tried to help, I decline to assist you any further. Have a nice life.

    --
    Eric Sosman
    d
    Eric Sosman, Jun 8, 2012
    #11
  12. Jan Burse

    Jan Burse Guest

    Eric Sosman schrieb:
    > In light of your abusiveness in responding to other people who've
    > tried to help, I decline to assist you any further. Have a nice life.


    Problem is I scribbled the exact same solution on
    a back of an envelope, but I have doubt that it is
    a good solution for small n, like n=2.

    Bye
    Jan Burse, Jun 8, 2012
    #12
  13. Jan Burse

    Lew Guest

    Re: Quick n-th Root of BigInteger

    On Friday, June 8, 2012 2:34:40 PM UTC-7, Jan Burse wrote:
    > markspace schrieb:
    > > I'm confused about the max, the z |, and the =< x.

    >
    > For those who don't know, there exists a set builder notation:
    >
    > http://en.wikipedia.org/wiki/Set-builder_notation#Z_notation
    >
    > max is then a higher order function from a set to an element.
    >
    > Forgot where this is taught, in elementary school?


    Riiiight. As nations and smaller school districts remove evolution from
    their textbooks, they're going to teach mathematical logic and set
    theory in elementary school?

    In any event, this being a Java forum, the notation '=<' (shown nowhere
    in your reference link, BTW) is rather odd, as we are used to '<='. Given
    that '=<' apparently is not part of the "Set Builder" notation, how about
    we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
    Python, shell, ...) idiom?

    --
    Lew
    Lew, Jun 8, 2012
    #13
  14. Jan Burse

    Jan Burse Guest

    Re: Quick n-th Root of BigInteger

    Lew schrieb:
    > In any event, this being a Java forum, the notation '=<' (shown nowhere
    > in your reference link, BTW) is rather odd, as we are used to '<='. Given
    > that '=<' apparently is not part of the "Set Builder" notation, how about
    > we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
    > Python, shell, ...) idiom?


    It was not Java, it was a math spec. When one writes:

    Given: xxx
    Compute: yyy

    Then xxx and yyy are not necessarely needed to follow
    the Java language specification.

    Do you want me to start counting the trolls that will
    now make their appearance in this thread? You are
    number 3 so far. I guess there will follow some more...

    Bye
    Jan Burse, Jun 8, 2012
    #14
  15. Jan Burse

    Jan Burse Guest

    Re: Quick n-th Root of BigInteger

    Jan Burse schrieb:
    > Do you want me to start counting the trolls that will
    > now make their appearance in this thread? You are
    > number 3 so far. I guess there will follow some more...


    But still comp.lang.java.programmer is too small
    I guess so that a shitstorm will rise. And there are
    still some that want to profit.

    Bye
    Jan Burse, Jun 8, 2012
    #15
  16. Jan Burse

    Lew Guest

    On Friday, June 8, 2012 2:43:37 PM UTC-7, Jan Burse wrote:
    > Eric Sosman schrieb:
    > > In light of your abusiveness in responding to other people who've
    > > tried to help, I decline to assist you any further. Have a nice life.

    >
    > Problem is I scribbled the exact same solution on
    > a back of an envelope, but I have doubt that it is
    > a good solution for small n, like n=2.


    For n == 2, just use any of the standard algorithms for square root, like
    <http://stackoverflow.com/questions/3432412/calculate-square-root-of-a-biginteger-system-numerics-biginteger?rq=1>
    found in about 10 minutes of online searching.

    --
    Lew
    Lew, Jun 8, 2012
    #16
  17. Jan Burse

    Lew Guest

    Re: Quick n-th Root of BigInteger

    On Friday, June 8, 2012 2:47:05 PM UTC-7, Jan Burse wrote:
    > Lew schrieb:
    > > In any event, this being a Java forum, the notation '=<' (shown nowhere
    > > in your reference link, BTW) is rather odd, as we are used to '<='. Given
    > > that '=<' apparently is not part of the "Set Builder" notation, how about
    > > we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
    > > Python, shell, ...) idiom?

    >
    > It was not Java, it was a math spec. When one writes:
    >
    > Given: xxx
    > Compute: yyy
    >
    > Then xxx and yyy are not necessarely needed to follow
    > the Java language specification.
    >
    > Do you want me to start counting the trolls that will
    > now make their appearance in this thread? You are
    > number 3 so far. I guess there will follow some more...


    A troll is not someone who suggests that you be clear in
    your communication, but someone who gets personally
    abusive as you did when given such a suggestion.

    Oh, darn, I forgot. You're the same person who suggests
    that one perform a sex act on you when they try to engage
    in any technical discussion with you. How do you feel you have
    the moral authority to accuse anyone else of being a troll?

    Because you don't.

    Matthew 7:5.

    --
    Lew
    Lew, Jun 8, 2012
    #17
  18. Jan Burse

    Jan Burse Guest

    Re: Quick n-th Root of BigInteger

    Lew schrieb:
    > A troll is not someone who suggests that you be clear in
    > your communication, but someone who gets personally
    > abusive as you did when given such a suggestion.


    =< should be cristal clear, = = equal and < = less.
    And if it is not cristal clear on first sight, it will
    become clear from reading the context. In the present
    case a troll is somebody who pretends not understand
    a post, when he does.

    Bye
    Jan Burse, Jun 8, 2012
    #18
  19. Jan Burse

    Lew Guest

    Re: Quick n-th Root of BigInteger

    On Friday, June 8, 2012 3:00:36 PM UTC-7, Jan Burse wrote:
    > Lew schrieb:
    > > A troll is not someone who suggests that you be clear in
    > > your communication, but someone who gets personally
    > > abusive as you did when given such a suggestion.

    >
    > =< should be cristal clear, = = equal and < = less.
    > And if it is not cristal clear on first sight, it will
    > become clear from reading the context. In the present
    > case a troll is somebody who pretends not understand
    > a post, when he does.


    I don't know whom you mean. No one here pretended not
    to understand it, only suggested that you follow the conventions
    appropriate to the forum.

    Stop being so nasty and confrontational, Jan. If you can't play
    nice, stay off the playground. You're being mean without any
    need.

    --
    Lew
    Lew, Jun 8, 2012
    #19
  20. Jan Burse

    Jan Burse Guest

    Re: Quick n-th Root of BigInteger

    Lew schrieb:
    > Stop being so nasty and confrontational, Jan. If you can't play
    > nice, stay off the playground. You're being mean without any
    > need.


    Stop your peer pressure. I told you already once:

    Suck my dick, shut up and **** off.
    Jan Burse, Jun 8, 2012
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,201
  2. nick
    Replies:
    0
    Views:
    883
  3. nick
    Replies:
    1
    Views:
    31,699
    Eric Sosman
    Oct 26, 2004
  4. JKop
    Replies:
    11
    Views:
    853
  5. j1mb0jay
    Replies:
    25
    Views:
    23,555
    Arne Vajhøj
    May 25, 2008
Loading...

Share This Page