15

このMath.sqrt()関数は引数としてdoubleを取り、doubleを返します。私はすべての状況で完全な平方グリッドを使用するプログラムを使用しており、整数形式の平方根を取得する必要があります。これを行う唯一の方法は、引数をとしてキャストしてから、キャストされたdoubleintを返すことですか?int

4

4 に答える 4

29

キャストテクニックは、一見したところよりもはるかに優れています。

intからdoubleへの変換は正確です。

Math.sqrtは、通常の正の数に対して、「引数値の真の数学的平方根に最も近いdouble値」を返すように指定されています。入力が完全な平方intの場合、結果はint範囲内の整数値のdoubleになります。

同様に、その整数値のdoubleをintに戻すことも正確です。

正味の効果は、キャスト手法が状況に丸め誤差を導入しないことです。

プログラムでGuavaintMathAPIを使用することでメリットが得られる場合は、それを使用して平方根を実行できますが、キャストを回避するためだけにAPIへの依存関係を追加することはしません。

于 2013-03-04T22:50:46.887 に答える
10

Google GuavaIntMathAPIはいつでも使用できます

final int sqrtX = IntMath.sqrt(x, RoundingMode.HALF_EVEN);
于 2013-03-04T22:41:51.707 に答える
1

完全な正方形の平方根のみを計算する場合、それらをテーブルに事前計算するオプションを検討しましたか?整数の完全な正方形の数には限りがあり、ほとんどのJVMは、多くの労力をかけずにそれらすべてを一度に保持できます。スペースが限られている場合は、この方向に他のオプションがあると確信しています。

65535がありますが、それが多すぎる場合は、おそらく4つに1つを格納し、その間の1つを計算できます。結局のところ、(x + 1)^ 2 =(x + 1)(x + 1)= x ^ 2 + 2x+1。

于 2013-03-04T22:57:25.340 に答える
1

多分興味のある人がリンクを見つけました:

http://atoms.alife.co.uk/sqrt/index.html

/*
ATOMS
Fast integer square roots in Java

Here are several fast integer square root methods, written in Java, including:
sqrt(x) agrees completely with (int)(java.lang.Math.sqrt(x)) for x < 2147483648 (i.e. 2^31), while executing about three times faster than it1.

fast_sqrt(x) agrees completely with (int)(java.lang.Math.sqrt(x)) for x < 289 (and provides a reasonable approximation thereafter), while executing about five times faster than it1.

SquareRoot.java - fast integer square root class;
SquareRootTest.java - basic speed and accuracy test class.
Thanks to Paul Hsieh's square root page for the accurate algorithm.
This code has been placed in the public domain.

Can you improve on the speed or accuracy of these methods (without chewing an "unreasonable" quantity of cache with a huge look-up table)?

If so, drop us a line, and hopefully we'll put your name up in lights.

[1: your mileage may vary]



tim@tt1.org | http://atoms.org.uk/
*/

/*
 * Integer Square Root function
 * Contributors include Arne Steinarson for the basic approximation idea, Dann 
 * Corbit and Mathew Hendry for the first cut at the algorithm, Lawrence Kirby 
 * for the rearrangement, improvments and range optimization, Paul Hsieh 
 * for the round-then-adjust idea, Tim Tyler, for the Java port
 * and Jeff Lawson for a bug-fix and some code to improve accuracy.
 * 
 * 
 * v0.02 - 2003/09/07
 */

/**
 * Faster replacements for (int)(java.lang.Math.sqrt(integer))
 */
public class SquareRoot {
  final static int[] table = {
     0,    16,  22,  27,  32,  35,  39,  42,  45,  48,  50,  53,  55,  57,
     59,   61,  64,  65,  67,  69,  71,  73,  75,  76,  78,  80,  81,  83,
     84,   86,  87,  89,  90,  91,  93,  94,  96,  97,  98,  99, 101, 102,
     103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118,
     119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
     133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145,
     146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157,
     158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
     169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178,
     179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188,
     189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
     198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206,
     207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215,
     215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
     224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231,
     231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
     239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246,
     246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
     253, 254, 254, 255
  };

  /**
   * A faster replacement for (int)(java.lang.Math.sqrt(x)).  Completely accurate for x < 2147483648 (i.e. 2^31)...
   */
  static int sqrt(int x) {
    int xn;

    if (x >= 0x10000) {
      if (x >= 0x1000000) {
        if (x >= 0x10000000) {
          if (x >= 0x40000000) {
            xn = table[x >> 24] << 8;
          } else {
            xn = table[x >> 22] << 7;
          }
        } else {
          if (x >= 0x4000000) {
            xn = table[x >> 20] << 6;
          } else {
            xn = table[x >> 18] << 5;
          }
        }

        xn = (xn + 1 + (x / xn)) >> 1;
        xn = (xn + 1 + (x / xn)) >> 1;
        return ((xn * xn) > x) ? --xn : xn;
      } else {
        if (x >= 0x100000) {
          if (x >= 0x400000) {
            xn = table[x >> 16] << 4;
          } else {
            xn = table[x >> 14] << 3;
          }
        } else {
          if (x >= 0x40000) {
            xn = table[x >> 12] << 2;
          } else {
            xn = table[x >> 10] << 1;
          }
        }

        xn = (xn + 1 + (x / xn)) >> 1;

        return ((xn * xn) > x) ? --xn : xn;
      }
    } else {
      if (x >= 0x100) {
        if (x >= 0x1000) {
          if (x >= 0x4000) {
            xn = (table[x >> 8]) + 1;
          } else {
            xn = (table[x >> 6] >> 1) + 1;
          }
        } else {
          if (x >= 0x400) {
            xn = (table[x >> 4] >> 2) + 1;
          } else {
            xn = (table[x >> 2] >> 3) + 1;
          }
        }

        return ((xn * xn) > x) ? --xn : xn;
      } else {
        if (x >= 0) {
          return table[x] >> 4;
        }
      }
    }

    illegalArgument();
    return -1;
  }

  /**
   * A faster replacement for (int)(java.lang.Math.sqrt(x)).  Completely accurate for x < 2147483648 (i.e. 2^31)...
   * Adjusted to more closely approximate 
   * "(int)(java.lang.Math.sqrt(x) + 0.5)"
   * by Jeff Lawson.
   */
  static int accurateSqrt(int x) {
    int xn;

    if (x >= 0x10000) {
      if (x >= 0x1000000) {
        if (x >= 0x10000000) {
          if (x >= 0x40000000) {
            xn = table[x >> 24] << 8;
          } else {
            xn = table[x >> 22] << 7;
          }
        } else {
          if (x >= 0x4000000) {
            xn = table[x >> 20] << 6;
          } else {
            xn = table[x >> 18] << 5;
          }
        }

        xn = (xn + 1 + (x / xn)) >> 1;
        xn = (xn + 1 + (x / xn)) >> 1;
        return adjustment(x, xn);
      } else {
        if (x >= 0x100000) {
          if (x >= 0x400000) {
            xn = table[x >> 16] << 4;
          } else {
            xn = table[x >> 14] << 3;
          }
        } else {
          if (x >= 0x40000) {
            xn = table[x >> 12] << 2;
          } else {
            xn = table[x >> 10] << 1;
          }
        }

        xn = (xn + 1 + (x / xn)) >> 1;

         return adjustment(x, xn);
      }
    } else {
      if (x >= 0x100) {
        if (x >= 0x1000) {
          if (x >= 0x4000) {
            xn = (table[x >> 8]) + 1;
          } else {
            xn = (table[x >> 6] >> 1) + 1;
          }
        } else {
          if (x >= 0x400) {
            xn = (table[x >> 4] >> 2) + 1;
          } else {
            xn = (table[x >> 2] >> 3) + 1;
          }
        }

        return adjustment(x, xn);
      } else {
        if (x >= 0) {
          return adjustment(x, table[x] >> 4);
        }
      }
    }

    illegalArgument();
    return -1;
  }

  private static int adjustment(int x, int xn) {
    // Added by Jeff Lawson:
    // need to test:
    //   if  |xn * xn - x|  >  |x - (xn-1) * (xn-1)|  then xn-1 is more accurate
    //   if  |xn * xn - x|  >  |(xn+1) * (xn+1) - x|  then xn+1 is more accurate
    // or, for all cases except x == 0:
    //    if  |xn * xn - x|  >  x - xn * xn + 2 * xn - 1 then xn-1 is more accurate
    //    if  |xn * xn - x|  >  xn * xn + 2 * xn + 1 - x then xn+1 is more accurate
    int xn2 = xn * xn;

    // |xn * xn - x|
    int comparitor0 = xn2 - x;
    if (comparitor0 < 0) {
      comparitor0 = -comparitor0;
    }

    int twice_xn = xn << 1;

    // |x - (xn-1) * (xn-1)|
    int comparitor1 = x - xn2 + twice_xn - 1;
    if (comparitor1 < 0) { // need to correct for x == 0 case?
      comparitor1 = -comparitor1; // only gets here when x == 0
    }

    // |(xn+1) * (xn+1) - x|
    int comparitor2 = xn2 + twice_xn + 1 - x;

    if (comparitor0 > comparitor1) {
      return (comparitor1 > comparitor2) ? ++xn : --xn;
    }

    return (comparitor0 > comparitor2) ? ++xn : xn;
  }

  /**
  * A *much* faster replacement for (int)(java.lang.Math.sqrt(x)).  Completely accurate for x < 289...
  */
  static int fastSqrt(int x) {
    if (x >= 0x10000) {
      if (x >= 0x1000000) {
        if (x >= 0x10000000) {
          if (x >= 0x40000000) {
            return (table[x >> 24] << 8);
          } else {
            return (table[x >> 22] << 7);
          }
        } else if (x >= 0x4000000) {
          return (table[x >> 20] << 6);
        } else {
          return (table[x >> 18] << 5);
        }
      } else if (x >= 0x100000) {
        if (x >= 0x400000) {
          return (table[x >> 16] << 4);
        } else {
          return (table[x >> 14] << 3);
        }
      } else if (x >= 0x40000) {
        return (table[x >> 12] << 2);
      } else {
        return (table[x >> 10] << 1);
      }
    } else if (x >= 0x100) {
      if (x >= 0x1000) {
        if (x >= 0x4000) {
          return (table[x >> 8]);
        } else {
          return (table[x >> 6] >> 1);
        }
      } else if (x >= 0x400) {
        return (table[x >> 4] >> 2);
      } else {
        return (table[x >> 2] >> 3);
      }
    } else if (x >= 0) {
      return table[x] >> 4;
    }
    illegalArgument();
    return -1;
  }

  private static void illegalArgument() {
    throw new IllegalArgumentException("Attemt to take the square root of negative number");
  }

  /** From http://research.microsoft.com/~hollasch/cgindex/math/introot.html
     * where it is presented by Ben Discoe (rodent@netcom.COM)
     * Not terribly speedy...
     */

  /*
     static int unrolled_sqrt(int x) {
        int v;
        int t = 1<<30;
        int r = 0;
        int s;

        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;} t >>= 2;
        s = t + r; r>>= 1; 
        if (s <= x) { x -= s; r |= t;}

        return r;
     }
  */

  /**
   * Mark Borgerding's algorithm...
   * Not terribly speedy...
   */

  /*
     static int mborg_sqrt(int val) {
        int guess=0;
        int bit = 1 << 15;
        do {
           guess ^= bit;  
           // check to see if we can set this bit without going over sqrt(val)...
           if (guess * guess > val )
              guess ^= bit;  // it was too much, unset the bit...
        } while ((bit >>= 1) != 0);

        return guess;
     }
    */

  /** 
   * Taken from http://www.jjj.de/isqrt.cc
   * Code not tested well...
   * Attributed to: http://www.tu-chemnitz.de/~arndt/joerg.html / email: arndt@physik.tu-chemnitz.de
   * Slow.
   */

  /*
     final static int BITS = 32;
     final static int NN = 0;  // range: 0...BITSPERLONG/2

     final static int test_sqrt(int x) {
        int i;
        int a = 0;                   // accumulator...
        int e = 0;                   // trial product...
        int r;

        r=0;                         // remainder...

        for (i=0; i < (BITS/2) + NN; i++)
        {
           r <<= 2;
           r +=  (x >> (BITS - 2));
           x <<= 2;

           a <<= 1;
           e = (a << 1)+1;

           if(r >= e)
           {
              r -= e;
              a++;
           }
        }

        return a;
     }
  */

  /*
  // Totally hopeless performance...
     static int test_sqrt(int n) {
        float r = 2.0F;
        float s = 0.0F;
        for(; r < (float)n / r; r *= 2.0F);
        for(s = (r + (float)n / r) / 2.0F; r - s > 1.0F; s = (r + (float)n / r) / 2.0F) {
           r = s;
        }

        return (int)s;
     }
    */
}


/*
 * Test Integer Square Root function
 */

public class SquareRootTest {
  public static void main(String args[]) {
    int x = -2;
    debug("" + (x == -2L));

    // perform timings...
    //testSpeed();

    // accuracy test...
    testAccuracy();

    // hang...
    do {} while (true);
  }

  static void testSpeed() {
    int i;
    long newtime;
    long oldtime;
    int N = 10000000;
    int mask = (1 << 16) - 1;

    // SquareRoot.fast_sqrt()...
    oldtime = System.currentTimeMillis();

    for (i = 0; i < N; i++) {
      int temp = SquareRoot.fastSqrt(i & mask);
    }

    newtime = System.currentTimeMillis();
    debug("SquareRoot.fast_sqrt:" + (newtime - oldtime));

    // SquareRoot.sqrt()...
    oldtime = System.currentTimeMillis();

    for (i = 0; i < N; i++) {
     int temp = SquareRoot.sqrt(i & mask);
    }

    newtime = System.currentTimeMillis();
    debug("SquareRoot.sqrt:" + (newtime - oldtime));

    /*
       // SquareRoot.mborg_sqrt()...
       oldtime = System.currentTimeMillis();

       for (i = 0; i < N; i++) {
          temp = SquareRoot.mborg_sqrt(i & mask);
       }

       newtime = System.currentTimeMillis();
       debug("SquareRoot.mborg_sqrt:" + (newtime - oldtime));


       // SquareRoot.test_sqrt()...
       oldtime = System.currentTimeMillis();

       for (i = 0; i < N; i++) {
          temp = SquareRoot.test_sqrt(i & mask);
       }

       newtime = System.currentTimeMillis();
       debug("SquareRoot.test_sqrt:" + (newtime - oldtime));
    */

    // java.lang.Math.sqrt()...
    oldtime = System.currentTimeMillis();

    for (i = 0; i < N; i++) {
     int temp = (int) (java.lang.Math.sqrt(i & mask));
    }

    newtime = System.currentTimeMillis();
    debug("java.lang.Math.sqrt:" + (newtime - oldtime));
  }

  static void testAccuracy() {
    int i;
    int a;
    int b;
    int c;
    int d;
    int e;
    int start = 0;
    int last_wrong_value = 0;

    for (i = start; ; i++) {
      a = (int) (java.lang.Math.sqrt(i));
      b = (int) (java.lang.Math.sqrt(i) + 0.5);
      c = SquareRoot.sqrt(i);
      d = SquareRoot.fastSqrt(i);
      e = SquareRoot.accurateSqrt(i);
      // e = SquareRoot.mborg_sqrt(i);
      // f = SquareRoot.test_sqrt(i);

      if (b != e) {
        //if (a > (last_wrong_value * 1.05)) { // don't print too many wrong values - just a sample...
          last_wrong_value = a;
          debug("N:" + i + " - Math.sqrt:" + a + " - Math.sqrt+:" + b + " - accurateSqrt:" + e + " - sqrt:" + c);
        }
      //}
    }
  }

  final static void debug(String o) {
    System.out.println(o);
  }
}

; ;

于 2015-02-14T08:46:45.983 に答える