平方根倒数的倒数

原题链接

解题思路

需要64位的魔数和三次牛顿迭代才能达到要求的计算精度。

代码

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let x_half = 0.5f64 * x as f64;
        let mut i = (x as f64).to_bits();
        i = 0x5FE6EC85E7DE30DA_u64 - (i >> 1);
        let mut f = f64::from_bits(i);
        f = f * (1.5 - x_half * f * f);
        f = f * (1.5 - x_half * f * f);
        f = f * (1.5 - x_half * f * f);
        (1.0f64 / f) as i32
    }
}
class Solution {
public:
    int mySqrt(int x) {
        union {
            long long i;
            double f;
        };
        double xHalf = 0.5 * x;
        f = x;
        i = 0x5FE6EC85E7DE30DALL - (i >> 1);
        f = f * (1.5 - xHalf * f * f); // 牛顿迭代法,重复此句可提高精度
        f = f * (1.5 - xHalf * f * f);
        f = f * (1.5 - xHalf * f * f); // 三次迭代
        return 1.0 / f;
    }
};
class Solution {
    public int mySqrt(int x) {
        double xHalf = 0.5 * x;
        long i = Double.doubleToLongBits(x);
        i = 0x5FE6EC85E7DE30DAL - (i >> 1);
        double f = Double.longBitsToDouble(i);
        f = f * (1.5 - xHalf * f * f);
        f = f * (1.5 - xHalf * f * f);
        f = f * (1.5 - xHalf * f * f);
        return (int)(1.0 / f);
    }
}
int mySqrt(int x) {
    double xHalf = 0.5 * x;
    double f = x;
    long long i = *(long long *) &f;
    i = 0x5FE6EC85E7DE30DALL - (i >> 1);
    f = *(double *) &i;
    f = f * (1.5 - xHalf * f * f); // 牛顿迭代法,重复此句可提高精度
    f = f * (1.5 - xHalf * f * f);
    f = f * (1.5 - xHalf * f * f); // 三次迭代
    return 1.0 / f;
}
object Solution {
    def mySqrt(x: Int): Int = {
        val xHalf: Double = 0.5 * x
        var i:Long = java.lang.Double.doubleToLongBits(x)
        i = 0x5FE6EC85E7DE30DAL - (i >> 1)
        var f:Double = java.lang.Double.longBitsToDouble(i)
        f = f * (1.5 - xHalf * f * f)
        f = f * (1.5 - xHalf * f * f)
        f = f * (1.5 - xHalf * f * f)
        (1.0 / f).toInt
    }
}
class Solution:
    def mySqrt(self, x: int) -> int:
        import struct
        x_half = 0.5 * x
        i = struct.unpack("Q", struct.pack("d", float(x)))[0]
        i = 0x5FE6EC85E7DE30DA - (i >> 1)
        f = struct.unpack("d", struct.pack("Q", i))[0]
        f = f * (1.5 - x_half * f * f)
        f = f * (1.5 - x_half * f * f)
        f = f * (1.5 - x_half * f * f)
        return int(1.0 / f)
public class Solution {
    public int MySqrt(int x) {
        double xHalf = 0.5 * x;
        long i = BitConverter.DoubleToInt64Bits(x);
        i = 0x5FE6EC85E7DE30DAL - (i >> 1);
        double f = BitConverter.Int64BitsToDouble(i);
        f = f * (1.5 - xHalf * f * f);
        f = f * (1.5 - xHalf * f * f);
        f = f * (1.5 - xHalf * f * f);
        return (int)(1.0 / f);
    }
}
class Solution {
    fun mySqrt(x: Int): Int {
        val xHalf: Double = 0.5 * x
        var i:Long = x.toDouble().toBits()
        i = 0x5FE6EC85E7DE30DAL - i.shr(1)
        var f:Double = Double.Companion.fromBits(i)
        f *= (1.5 - xHalf * f * f)
        f *= (1.5 - xHalf * f * f)
        f *= (1.5 - xHalf * f * f)
        return (1.0 / f).toInt()
    }
}
class Solution {
    func mySqrt(_ x: Int) -> Int {
        let x_half = 0.5 * Double(x)
        var i : UInt64 = Double(x).bitPattern
        i = 0x5FE6EC85E7DE30DA - (i >> 1)
        var f : Double = Double.init(bitPattern: i)
        f = f * (1.5 - x_half * f * f)
        f = f * (1.5 - x_half * f * f)
        f = f * (1.5 - x_half * f * f)
        return Int(1.0 / f)
    }
}
import "math"

func mySqrt(x int) int {
    var xHalf = 0.5 * float64(x)
	var i = math.Float64bits(float64(x))
	i = 0x5FE6EC85E7DE30DA - (i >> 1)
	var f = math.Float64frombits(i)
	f = f * (1.5 - xHalf * f * f)
	f = f * (1.5 - xHalf * f * f)
	f = f * (1.5 - xHalf * f * f)
	return int(1.0 / f)
}
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    const xHalf = 0.5 * x;
    let i = new BigInt64Array(new Float64Array([x]).buffer)[0];
    i = 0x5FE6EC85E7DE30DAn - (i >> 1n);
    let f = new Float64Array(new BigInt64Array([i]).buffer)[0];
    f = f * (1.5 - xHalf * f * f);
    f = f * (1.5 - xHalf * f * f);
    f = f * (1.5 - xHalf * f * f);
    return Math.floor(1.0 / f);
};

参考

这个链接解释了上面的魔数0x5FE6EC85E7DE30DA的计算方法。

我的题解

链接