Java中確定整數的平方根是否是整數

    1.概述

    理想平方是一個數字,可以表示為兩個相等整數的乘積。

    在本文中,我們將發現多種方法來確定整數在Java中是否是理想的平方。另外,我們將討論每種技術的優缺點,以確定其效率,這是最快的。

    2.檢查整數是否為完美平方

    眾所周知,Java為定義整數提供了兩種數據類型。第一個是int ,它表示32位數字,而另一個是long ,它表示64位數字。在本文中,我們將使用long數據類型來處理最壞的情況(可能的最大整數)。

    由於Java以64位表示長整數,因此長整數的範圍是-9,223,372,036,854,775,808,223,372,036,854,775,807 。而且,由於我們要處理完美的平方,因此我們只關心處理正整數集,因為將任何整數自身相乘總是會產生一個正數。

    另外,由於最大數目是2^63 ,這意味著大約2^31.5整數的平方小於2^63 。此外,我們可以假設擁有一個包含這些數字的查找表是無效的。

    2.1。在Java中使用sqrt方法

    檢查整數是否為理想平方的最簡單,最直接的方法是使用sqrt函數。眾所周知, sqrt函數返回一個double sqrt值。因此,我們需要做的就是將結果轉換為int並乘以它本身。然後,我們檢查結果是否等於開始的整數:

    public static boolean isPerfectSquareByUsingSqrt(long n) {
    
     if (n <= 0) {
    
     return false;
    
     }
    
     double squareRoot = Math.sqrt(n);
    
     long tst = (long)(squareRoot + 0.5);
    
     return tst*tst == n;
    
     }

    請注意,由於處理double精度值時可能遇到的精度誤差,我們可能需要將結果加0.5。有時,將整數分配給double變量時,可以用小數點表示。

    例如,如果我們將數字3分配給double精度變量,則其值可能是3.00000001或2.99999999。因此,為避免這種表示方式,在將其強制轉換為long值之前,我們先添加0.5以確保獲得實際值。

    另外,如果我們用一個數字測試sqrt函數,我們會注意到執行時間很快。另一方面,如果需要多次調用sqrt函數,並嘗試減少sqrt函數執行的操作數,則這種微優化實際上可能會有所作為。

    2.2。使用二進制搜索

    我們可以使用二進制搜索來查找數字的平方根,而無需使用sqrt函數

    由於該數字的範圍是1到2 63 ,所以根在1到2 31.5之間。因此,二分查找算法需要約16次迭代才能獲得平方根:

    public boolean isPerfectSquareByUsingBinarySearch(long low, long high, long number) {
    
     long check = (low + high) / 2L;
    
     if (high < low) {
    
     return false;
    
     }
    
     if (number == check * check) {
    
     return true;
    
     }
    
     else if (number < check * check) {
    
     high = check - 1L;
    
     return isPerfectSquareByUsingBinarySearch(low, high, number);
    
     }
    
     else {
    
     low = check + 1L;
    
     return isPerfectSquareByUsingBinarySearch(low, high, number);
    
     }
    
     }

    2.3。二進制搜索的增強

    為了增強二進制搜索,我們可以注意到,如果我們確定基本數的位數,則可以確定根的範圍。

    例如,如果數字僅由一位數字組成,則平方根的範圍在1到4之間。原因是,一位數字的最大整數為9,其根為3。此外,如果數字為由兩位數字組成,範圍在4到10之間,依此類推。

    因此,我們可以構建一個查找表,以基於開頭的數字的位數來指定平方根的範圍。這將減少二進制搜索的範圍。因此,將需要較少的迭代來獲得平方根:

    public class BinarySearchRange {
    
     private long low;
    
     private long high;
    
    
    
     // standard constructor and getters
    
     }
    private void initiateOptimizedBinarySearchLookupTable() {
    
     lookupTable.add(new BinarySearchRange());
    
     lookupTable.add(new BinarySearchRange(1L, 4L));
    
     lookupTable.add(new BinarySearchRange(3L, 10L));
    
     for (int i = 3; i < 20; i++) {
    
     lookupTable.add(
    
     new BinarySearchRange(
    
     lookupTable.get(i - 2).low * 10,
    
     lookupTable.get(i - 2).high * 10));
    
     }
    
     }
    public boolean isPerfectSquareByUsingOptimizedBinarySearch(long number) {
    
     int numberOfDigits = Long.toString(number).length();
    
     return isPerfectSquareByUsingBinarySearch(
    
     lookupTable.get(numberOfDigits).low,
    
     lookupTable.get(numberOfDigits).high,
    

    2.4。整數算法的牛頓法

    通常,我們可以使用牛頓法來獲得任何數字的平方根,甚至是非整數。牛頓法的基本思想是假設數字X是數字N平方根。之後,我們可以開始循環並繼續計算根,該根肯定會朝N的正確平方根移動。

    但是,通過對牛頓方法進行一些修改,我們可以使用它來檢查整數是否是理想的平方:

    public static boolean isPerfectSquareByUsingNewtonMethod(long n) {
    
     long x1 = n;
    
     long x2 = 1L;
    
     while (x1 > x2) {
    
     x1 = (x1 + x2) / 2L;
    
     x2 = n / x1;
    
     }
    
     return x1 == x2 && n % x1 == 0L;
    
     }

    3.優化整數平方根算法

    正如我們所討論的,有多種算法可以檢查整數的平方根。儘管如此,我們始終可以通過一些技巧來優化任何算法。

    技巧應考慮避免執行將確定平方根的主要操作。例如,我們可以直接排除負數。

    我們可以使用的事實之一是“完美的平方只能以16為底的0、1、4或9結尾” 。因此,我們可以在開始計算之前將整數轉換為以16為底的整數。之後,我們排除將數字視為不完美平方根的情況:

    public static boolean isPerfectSquareWithOptimization(long n) {
    
     if (n < 0) {
    
     return false;
    
     }
    
     switch((int)(n & 0xF)) {
    
     case 0: case 1: case 4: case 9:
    
     long tst = (long)Math.sqrt(n);
    
     return tst*tst == n;
    
     default:
    
     return false;
    
     }
    
     }

    4。結論

    在本文中,我們討論了確定整數是否為完美平方的多種方法。如我們所見,我們總是可以通過一些技巧來增強算法。

    這些技巧將在開始算法的主要操作之前排除大量情況。原因是可以很容易地將許多整數確定為不完美的平方。