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

Groups > comp.lang.java.programmer > #38481 > unrolled thread

Re: Square Root Of java.math.BigInteger

Back to article view | Back to comp.lang.java.programmer

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Square Root Of java.math.BigInteger bursejan@gmail.com - 2018-07-10 04:26 -0700
    Re: Square Root Of java.math.BigInteger bursejan@gmail.com - 2018-07-12 04:38 -0700
      Re: Square Root Of java.math.BigInteger j4n bur53 <janburse@fastmail.fm> - 2018-07-12 15:12 +0200

#38481 — Re: Square Root Of java.math.BigInteger

JDK 9 has now Hacker sqrt():

The closed: JDK-8032027 : Add BigInteger square root methods
https://bugs.java.com/view_bug.do?bug_id=8032027

In the bug there is a mention of Zimmerman, but Hacker is in OpenJDK:
     * @implNote The implementation is based on the material in Henry S. Warren,
     * Jr., <i>Hacker's Delight (2nd ed.)</i> (Addison Wesley, 2013), 279-282.
https://github.com/netroby/jdk9-dev/blob/master/jdk/src/java.base/share/classes/java/math/MutableBigInteger.java#L1883

Am Sonntag, 25. Mai 2008 05:46:53 UTC+2 schrieb Arne Vajhøj:
> j1mb0jay wrote:
> > Posted the wring code, the code is below LOL !!!!
> > 
> > -------------Square Root Code --------------------
> > 
> > package math;
> > 
> > import java.math.BigInteger;
> > 
> > public class SquareRoot 
> > {
> > 	public static BigInteger squareRoot(BigInteger testSubject, 
> > boolean round)
> > 	{
> 
> My suggestion:
> 
>      private final static BigInteger one = new BigInteger("1");
>      private final static BigInteger two = new BigInteger("2");
>      public static BigInteger sqrt(BigInteger v) {
>          int n = v.toByteArray().length;
>          byte[] b = new byte[n/2+1];
>          b[0] = 1;
>          BigInteger guess = new BigInteger(b);
>          while(true) {
>              BigInteger guessadd1 = guess.add(one);
>              BigInteger guesssub1 = guess.subtract(one);
>              if(guess.multiply(guess).compareTo(v) > 0) {
>                  if(guesssub1.multiply(guesssub1).compareTo(v) <= 0) {
>                      return guesssub1;
>                  }
>              } else {
>                  if(guessadd1.multiply(guessadd1).compareTo(v) > 0) {
>                      return guess;
>                  }
>              }
>              guess = guess.add(v.divide(guess)).divide(two);
>          }
>      }
> 
> Arne

[toc] | [next] | [standalone]

#38484

Some empirical data, the JDK 9 implementation
could gain more speed, if it would do instead of:

            int shift = bitLength - 63;

Something as follows:
            int shift = bitLength - 104;

The doubleValue() will take half even rounded 52 bits 
of it, and an exponent, the sqrt() will again produce
52 bits, and when shifting back by shift/2, the Newton 

start value will have 52 bits and not only 31 bits. 
Then after ca. 10^1000 there should be threshold and
a switch to a Zimmerman implementation.

Am Dienstag, 10. Juli 2018 13:26:50 UTC+2 schrieb burs...@gmail.com:
> JDK 9 has now Hacker sqrt():
> 
> The closed: JDK-8032027 : Add BigInteger square root methods
> https://bugs.java.com/view_bug.do?bug_id=8032027
> 
> In the bug there is a mention of Zimmerman, but Hacker is in OpenJDK:
>      * @implNote The implementation is based on the material in Henry S. Warren,
>      * Jr., <i>Hacker's Delight (2nd ed.)</i> (Addison Wesley, 2013), 279-282.
> https://github.com/netroby/jdk9-dev/blob/master/jdk/src/java.base/share/classes/java/math/MutableBigInteger.java#L1883
> 
> Am Sonntag, 25. Mai 2008 05:46:53 UTC+2 schrieb Arne Vajhøj:
> > j1mb0jay wrote:
> > > Posted the wring code, the code is below LOL !!!!
> > > 
> > > -------------Square Root Code --------------------
> > > 
> > > package math;
> > > 
> > > import java.math.BigInteger;
> > > 
> > > public class SquareRoot 
> > > {
> > > 	public static BigInteger squareRoot(BigInteger testSubject, 
> > > boolean round)
> > > 	{
> > 
> > My suggestion:
> > 
> >      private final static BigInteger one = new BigInteger("1");
> >      private final static BigInteger two = new BigInteger("2");
> >      public static BigInteger sqrt(BigInteger v) {
> >          int n = v.toByteArray().length;
> >          byte[] b = new byte[n/2+1];
> >          b[0] = 1;
> >          BigInteger guess = new BigInteger(b);
> >          while(true) {
> >              BigInteger guessadd1 = guess.add(one);
> >              BigInteger guesssub1 = guess.subtract(one);
> >              if(guess.multiply(guess).compareTo(v) > 0) {
> >                  if(guesssub1.multiply(guesssub1).compareTo(v) <= 0) {
> >                      return guesssub1;
> >                  }
> >              } else {
> >                  if(guessadd1.multiply(guessadd1).compareTo(v) > 0) {
> >                      return guess;
> >                  }
> >              }
> >              guess = guess.add(v.divide(guess)).divide(two);
> >          }
> >      }
> > 
> > Arne

[toc] | [prev] | [next] | [standalone]

#38485

int shift = Math.max(bitLength - 104, 0);

bursejan@gmail.com schrieb:
> int shift = bitLength - 104;

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web