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

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

Re: Quick n-th Square of BigInteger

From Jan Burse <janburse@fastmail.fm>
Newsgroups comp.lang.java.programmer
Subject Re: Quick n-th Square of BigInteger
Date 2012-06-09 01:44 +0200
Organization albasani.net
Message-ID <jqu2oi$hd4$1@news.albasani.net> (permalink)
References <jqtian$er7$1@news.albasani.net> <dlu4t7llbfgb1n8esgs5hbjhn7t2hb6ft8@4ax.com> <jqtuqh$9uo$1@news.albasani.net> <jqu25k$6f4$1@speranza.aioe.org>

Show all headers | View raw

glen herrmannsfeldt schrieb:
> 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.

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?).

Hm

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