欧几里得算法和牛顿迭代法

发表于 | 分类于

欧几里得算法和牛顿迭代法

求最大公约数

辗转相除法：f(x,y) = f(y,x%y),x和y的最大公约数和y和x%的最大公约数相同

1
2
3
4
5
6
7
8
public static int Gcd (int a, int b) {
        while (b > 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

求平方根

牛顿迭代法： k=(k+x/k)/2

1
2
3
4
5
6
7
8
9
public static double Sqrt (int x) {
        double res=0;
        double last=x;
        while(Math.abs(res-last)>0.000000001){
            res = last;
            last = (res+(x/res))/2;
        }
        return res;
    }

之前也听说卡马克快速平方根倒数算法，好奇这几个平方根算法哪个更快
cmark: 

1
2
3
4
5
6
7
8
9
10
11
12
13
public static double cmark(int number) {
       int i;
       float x2, y;
       float threehalfs = 1.5F;
       x2 = number * 0.5F;
       y = number;
       i = Float.floatToRawIntBits(y); // evil floating point bit level hacking
       i = 0x5f3759df - (i >> 1); // what the fuck?
       y = Float.intBitsToFloat(i);
       y = y * (threehalfs - (x2 * y * y)); // 1st iteration
       y = y * (threehalfs - (x2 * y * y)); // 2nd iteration, this can be removed
       return 1 / y;
   }

结果是库函数最快，其次是牛顿迭代法（和库函数差不多），卡马克稍慢，啊哈哈哈

Thanks!