Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #15143

Re: Quick n-th Square of BigInteger

From glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups comp.lang.java.programmer
Subject Re: Quick n-th Square of BigInteger
Date 2012-06-09 01:06 +0000
Organization Aioe.org NNTP Server
Message-ID <jqu7ht$hd7$1@speranza.aioe.org> (permalink)
References <jqtian$er7$1@news.albasani.net> <dlu4t7llbfgb1n8esgs5hbjhn7t2hb6ft8@4ax.com> <jqtuqh$9uo$1@news.albasani.net> <jqu25k$6f4$1@speranza.aioe.org> <jqu2oi$hd4$1@news.albasani.net>

Show all headers | View raw

Jan Burse <janburse@fastmail.fm> wrote:

(after I wrote)
>> Well, start the loop by squaring until you get a value larger
>> than y, then you have two powers that you know n is between,
>> saving the lower value each time. Now binary search over that
>> range, each time saving the highest known power such that the
>> result doesn't exceed y.

> Yes this would be an alternative to the bitCount() suggestion
> from Eric. Since BigInteger has bitCount(), I guess bitCount()
> is the more efficient solution.

> The bisection is probably slower than Newton. In Newton you
> have to compute x^n-1 and divide in each iteration, in
> bisection you have to compute x^n and compare in each iteration.
> So I take it that the effort for the iteration step itself
> is more or less the same for both methods.

I will guess that it depends much on the size of x and n.
I like the bisection because it avoided the divide, which
might be slow, but might not be. Also, since he wants floor(),
you have to be careful for the case where y is very close to
an integer power of n, and Newton might round the wrong way.

(It is interesting, the IBM 360/91 uses the Newton't method
divide algorithm for floating point divide, returning the
rounded quotient. The S/360 architecture specifies a truncated
quotient, so this has to be stated as a deviation from the
architecture.)

> So that in the end the number of iterations will be dominant.
> When Newton doubles the precision in each iteration, it will
> use log m/n steps (right?), whereas bisection probably also
> uses log m/n steps in the average (right?).

and x^n takes O(log n) multiplies. 

-- glen

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 21:03 +0200
  Re: Quick n-th Square of BigInteger Gene Wirchenko <genew@ocis.net> - 2012-06-08 13:34 -0700
    Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 22:36 +0200
      Re: Quick n-th Root of BigInteger markspace <-@.> - 2012-06-08 13:55 -0700
        Re: Quick n-th Root of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 21:06 +0000
          Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:21 +0200
        Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:34 +0200
          Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:43 -0700
            Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:47 +0200
              Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:47 +0200
              Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:55 -0700
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:00 +0200
                Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 15:10 -0700
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:12 +0200
                Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 15:18 -0700
            Re: Quick n-th Root of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 22:59 +0000
              Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:05 +0200
            Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:00 +0200
              Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 16:15 -0700
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:51 +0200
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 02:32 +0200
  Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:00 +0200
  Re: Quick n-th Square of BigInteger Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-08 17:04 -0400
    Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:19 +0200
      Re: Quick n-th Square of BigInteger Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-08 17:40 -0400
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:43 +0200
          Re: Quick n-th Square of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:52 -0700
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:30 +0200
              Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:05 +0000
    Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-11 14:53 +0200
  Re: Quick n-th Square of BigInteger Roedy Green <see_website@mindprod.com.invalid> - 2012-06-08 15:32 -0700
    Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:37 +0200
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:39 +0200
      Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:34 +0000
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:44 +0200
          Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-09 01:06 +0000
    Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:25 +0000
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:29 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:29 +0200
    Re: Quick n-th Square of BigInteger Wanja Gayk <brixomatic@yahoo.com> - 2012-06-17 15:00 +0200
  Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 08:42 -0500
    Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 16:54 +0200
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 17:56 +0200
        Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 12:52 -0500
      Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-09 12:55 -0400
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:23 +0200
      Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 12:44 -0500
        Re: Quick n-th Square of BigInteger markspace <-@.> - 2012-06-09 11:50 -0700
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:13 +0200
            Re: Quick n-th Square of BigInteger markspace <-@.> - 2012-06-09 12:25 -0700
              Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:29 +0200
        Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-09 21:27 -0400
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:08 +0200
            Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-10 08:23 -0400
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 13:31 +0200
            Re: Quick n-th Square of BigInteger Wanja Gayk <brixomatic@yahoo.com> - 2012-06-17 15:11 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:04 +0200
      Re: Quick n-th Square of BigInteger Roedy Green <see_website@mindprod.com.invalid> - 2012-06-16 17:45 -0700
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-17 03:17 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-17 03:38 +0200
  Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:31 +0200
    Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:35 +0200
    Re: Troll Parade Closing, Award Ceremony Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-10 06:28 -0500
      Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 13:30 +0200
    Re: Troll Parade Closing, Award Ceremony Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-10 08:25 -0400
      Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 14:48 +0200
    Re: Troll Parade Closing, Award Ceremony Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-06-10 11:49 -0700

csiph-web