#include <stdio.h>
#include <sys/time.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
long long a[(1 << 14)];
long long getCurrentTime()
{
//用于获取系统微秒时间
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec * 1000000 + tv.tv_usec;
}
long long Sqrt1(long long n)
{
long long L = 0, R = 3e9;
//二分开区间(L,R]，最终L和R相等。
//最后答案可能是L或者L-1
while (L < R)
{
long long Mid = (L + R) / 2;
if (Mid * Mid >= n)
{
//答案在右边，继续搜索(Mid,R]
R = Mid;
}
else
{
//答案在左边,继续搜索(Mid+1,R]
L = Mid + 1;
}
}
//>要返回L-1
if (L * L > n)L--;
return L;
}
long long Sqrt2(long long n)
{
//选择x=0和x=1的前后两项
long long pre = 0, nxt = 1;
while (1)
{
/*
xn+1=xn-(xn^2-n)/(2xn)
也就是后一项为前一项减去(当前的值)/(导数)
即nxt+(nxt*nxt-n)/(2*nxt)
化简之后如lst所示
*/
long long lst = (nxt + n / nxt) / 2;
//已经收敛
if (lst == pre)
{
return pre;
}
//进行迭代
pre = nxt;
nxt = lst;
}
}
long long Sqrt3(double x)
{
double xhalf = 0.5 * (double)x;
// get bits for floating VALUE
long long i = *(long long *)&x;
// gives initial guess y0
i = 0x5fe6ec85e7de30da - (i >> 1);
// convert bits BACK to float
x = *(double *)&i;
// Newton step, repeating increases accuracy
x = x * (1.5f - xhalf * x * x);
x = x * (1.5f - xhalf * x * x);
x = x * (1.5f - xhalf * x * x);
return 1.0 / (double)x;
}
long long Sqrt4(double x)
{
return sqrt(x);
}
int main()
{
srand(time(NULL));
//2.3GHz*10^9/10^6，得到每微秒的时钟周期数
long long t_c = 2300;
for (int k = 0; k <= 14; k += 2)
{
long long v = 1 << k, t1, t2,tt=0;
int i;
for (int i = 0; i < v; ++i)
{
a[i] = rand() * 1LL * rand();
}
t1 = getCurrentTime();
for (i = 0; i < v; ++i)
{
long long j=Sqrt1(a[i]);
}
t2 = getCurrentTime();
printf("Sqrt1:%.6f\n", t_c * 1. * (t2 - t1) / v);
t1 = getCurrentTime();
for (i = 0; i < v; ++i)
{
long long j=Sqrt2(a[i]);
}
t2 = getCurrentTime();
printf("Sqrt2:%.6f\n", t_c * 1. * (t2 - t1) / v);
t1 = getCurrentTime();
for (i = 0; i < v; ++i)
{
long long j=Sqrt3(a[i]);
}
t2 = getCurrentTime();
printf("Sqrt3:%.6f\n", t_c * 1. * (t2 - t1) / v);
t1 = getCurrentTime();
for (i = 0; i < v; ++i)
{
long long j=Sqrt4(a[i]);
}
t2 = getCurrentTime();
printf("Sqrt4:%.6f\n", t_c * 1. * (t2 - t1) / v);
}
return 0;
}