jscience
  1. jscience
  2. JSCIENCE-139

LargeInteger sqrt function fails for integers that are 1 less than perfrct squares

    Details

    • Type: Bug Bug
    • Status: Open
    • Priority: Major Major
    • Resolution: Unresolved
    • Affects Version/s: current
    • Fix Version/s: Version 6.0
    • Component/s: www
    • Labels:
      None
    • Environment:

      Operating System: Windows XP
      Platform: All

    • Issuezilla Id:
      139

      Description

      I have been working with the LargeInteger class and have discovered a problem:

      If you use the "sqrt" function on some integers it loops until it runs out of
      memory:

      So far I have discovered that it fails on integers that are 1 less that a
      perfect square (15, 35, 63...)

      — code ----
      LargeInteger current = LargeInteger.valueOf("15");
      LargeInteger root = current.sqrt() ;

      — code ----

      — output —
      Java heap spaceException in thread "main" java.lang.OutOfMemoryError: Java heap
      spacejava.lang.OutOfMemoryError: Java heap space
      Java Result: 1
      — output —

      I am using the sun JDK 1.6.0_14

      compiled using ant.

      The javolution and geoapi jars are the ones that are packaged with the source
      version of the JScience library.

      Upon further investigation, the approximation method alternates between 2
      values.

      For example, in the case of 15 is vibrates between 3 and 4

      — code —
      /**

      • Returns the integer square root of this integer.
      • @return <code>k<code> such as <code>k^2 <= this < (k + 1)^2</code>
      • @throws ArithmeticException if this integer is negative.
        */
        public LargeInteger sqrt() {
        if (this.isNegative())
        throw new ArithmeticException("Square root of negative integer");
        int bitLength = this.bitLength();
        StackContext.enter();
        try
        Unknown macro: { // First approximation. LargeInteger k = this.times2pow(-((bitLength >> 1) + (bitLength & 1))); while (true) { LargeInteger newK = (k.plus(this.divide(k))).times2pow(-1); System.out.println("Next approximation: " + newK) ; if (newK.equals(k)) return StackContext.outerCopy(k); k = newK; } }

        finally

        { StackContext.exit(); }
        }
        – code –
        Next approximation: 4
        Next approximation: 3
        Next approximation: 4
        Next approximation: 3
        .
        .
        .
        Next approximation: 4
        Next approximation: 3
        Next approximation: 4
        Next approximation: 3
        Next approximation: 4
        — output (for an integer value of 15) –


        The solution for the oscillation of values could be constructed as (assuming it
        only oscillates between 2 values):

        — code —
        /**
        * Returns the integer square root of this integer.
        *
        * Also prevents the approximation method from being caught in an
        * infinite loop when the approximations start oscillating between
        * 2 values
        *
        * @return <code>k<code> such as <code>k^2 <= this < (k + 1)^2</code>
        * @throws ArithmeticException if this integer is negative.
        */
        public LargeInteger sqrt() {
        if (this.isNegative())
        throw new ArithmeticException("Square root of negative integer");
        int bitLength = this.bitLength();
        StackContext.enter();
        try {
        // First approximation.
        LargeInteger k = this.times2pow(-((bitLength >> 1) + (bitLength &
        1)));
        LargeInteger previousK = LargeInteger.valueOf("-1") ;

        while (true) {
        LargeInteger newK = (k.plus(this.divide(k))).times2pow(-1);
        if (newK.equals(k))
        return StackContext.outerCopy(k);

        // Detect the occurrence of oscillation of a value such as the
        // sqrt of 15 oscillates between 3 and 4
        if ( newK.equals(previousK) ) {
        if ( previousK.compareTo(k) > 0 ) { return StackContext.outerCopy(previousK) ; } else { return StackContext.outerCopy(k) ; }
        }

        previousK = k ;
        k = newK;
        }
        } finally { StackContext.exit(); }

        }

          • code —

        Activity

        There are no comments yet on this issue.

          People

          • Assignee:
            jscience-issues
            Reporter:
            0x4765654b
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated: