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

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

Re: Quick n-th Square of BigInteger

Path csiph.com!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail
From Jan Burse <janburse@fastmail.fm>
Newsgroups comp.lang.java.programmer
Subject Re: Quick n-th Square of BigInteger
Date Sat, 09 Jun 2012 00:30:24 +0200
Organization albasani.net
Lines 28
Message-ID <jqtudr$9b1$1@news.albasani.net> (permalink)
References <jqtian$er7$1@news.albasani.net> <jqtpd1$jda$1@dont-email.me> <jqtq8d$vv6$1@news.albasani.net> <jqtrgt$vp9$2@dont-email.me> <jqtrm4$2k4$2@news.albasani.net> <2c0e8fd7-c593-439f-953f-ad1dfc735937@googlegroups.com>
Mime-Version 1.0
Content-Type text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding 7bit
X-Trace news.albasani.net Ch19XnOfjAESVdunKH6POBDl4gw8nXrEq6ip14JatSi2T0O/oKFwoBEKGcijOStxvryx+fzcr2bPr7NSYaBtHg==
NNTP-Posting-Date Fri, 8 Jun 2012 22:30:19 +0000 (UTC)
Injection-Info news.albasani.net; logging-data="IPQjGVFiH9HLVL0rKBELtOAa/NurZF9Zh2zsWT21ZEmc46XFVxtFkquLf2cBkT9h4htIXigLlbpskYZ9O8BhU6A9HDHYrFQwChp8L+rjWCnGLSY8HR2dUxKIo/zE+m6K"; mail-complaints-to="abuse@albasani.net"
User-Agent Mozilla/5.0 (Windows NT 6.1; WOW64; rv:13.0) Gecko/20120604 Firefox/13.0 SeaMonkey/2.10
In-Reply-To <2c0e8fd7-c593-439f-953f-ad1dfc735937@googlegroups.com>
Cancel-Lock sha1:urwWJJrv/KiqDv2zUnZLLdJab5k=
Xref csiph.com comp.lang.java.programmer:15127

Show key headers only | View raw

Lew schrieb:
>> 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.
>

It took me only one second to find it. But it doesn't
solve the question.

Should we now also apply Newton to n<>2? What can we
do about that Newton might oscillate for integers?
Is the lowerBound and upperBound fence trick of isSqrt
also good for n<>2?

Given the fence trick, we can probably abandon max-
iteration approaches, or not?

CORDIC methods, are they appropriate on CPUs that have
multiplication?

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