关于手算开方的一些问题
X_Chara
·
2020-01-06 17:19:17
·
个人记录
大家在做题的过程中有时就会用到开方，相信大家可能都是有的cmath里的sqrt()函数吧，但有的时候，出题人会毒瘤的让你高精度开方，真是千刀万剐
那我们就没办法了（看来我只会用魔刀和玩剪刀,qwq）
今天，我们就来看一下如何高精度开方怎么算吧
众所周知，但凡是高精度运算，就和模拟列竖式分不开关系，所以，我们先看一下如何手算平方根
1.手算方根
丑图
1.将被开方数(为了形象，表述成“被除数”，此例中即为65536)从个位往高位每两位一断写成6,55,35的形式，为了方便表述，以下每一个“,”称为一步。
2．从高位开始计算开方。例如第一步为6，由于2^2 = 4 < 6 < 9 = 3^2，因此只能商2(这就是和除法不同的地方，“除数”和“商”的计算位必须相同)。于是将2写在根号上方，计算开方余项。即高位余项加一步低位，此例中，即为高位余项2和低位一步55，余项即为255。
3．将第二步得到的第一步开方得数2乘以20(原理证不来，可以在评论区疯狂盖楼骂楼主，但你们可能舍不得骂阿柒qwq)作为第二步除数的高位。即本步除数是\overline{4x}(四十几)。按照要求，本步的商必须是x。因为45×5 = 225 < 255 < 46×6 = 276，所以本步商5。
相信大家都没看懂 （大雾 ， 那我们就直接讲算法吧
2.算法
1.穷举法（屎一样的算法，建议跳过，你可能会疯掉）
缩进保命
看到x = 9 ，求时，它会首先在大脑里搜索是否存在直接能用的结果，相信九九乘法表早已刻在你的脑子里，因此你会毫不犹豫地说出，\sqrt{9} = 3；但是当x = 784时，你的脑中不存在的直接储备，但是你记得25的平方与30的平方这两个节点，而784恰好处在625与900之间，因此，如果运气够好的话，只需要计算26~29的平方，当然，你的运气足够好，28^2 = 784.
好了，现在我们将784更换成744，你又如何做呢？显然经过计算你又知道了在27,28之间，是一个小数，因此你需要猜测，小数点后那一位究竟是多少。
现在，我们用代码模拟以上过程(我就说嘛，都是模拟，模拟就完了)。需要解决以下几个问题：
1.为了让计算机快速找到解区间，你需要一个乘法表来存储各个关键节点，那么这个表应该多大呢？如果一个好事者输入了10位整数，我们的计算机能够存储那么大的乘法表吗？
既然这样，不如利用计算机的优势，当场算出相应的区间就好。
2.猜测的小数后一位应该是多少呢？
既然找到了区间，不如设定一个步长假设为0.1，依次计算区间内的数据。（27.1，27.2，27.3······）
显然步长越小，计算次数越多。
2.计算机无法精确表达浮点数，只能通过设置误差a来确定是否取值（|i^2 - x| < a），这时你惊奇的发现
27.2^2 = 739.84
27.3^2 = 745.29
因此误差a至少要取到1.29，如果我们令a = 1，那么就无法得到答案。
如果步长与误差设置不合适，很可能计算机会跳过正确的解。
以上的问题搞得人焦头烂额，让人感觉像吃屎一样。
因此很不负责任地得到以下代码
#include
using namespace std;
int main()
{
int x;
cin >> x;
double i = 0;
int cnt = 0;
while(i*i < x)
{
i += 1;
cnt += 1;
}
i -= 1;
while(i*i < x)
{
i += 0.01;
cnt += 1;
}
printf("sqrt(x) = %.6lf, cnt = %d", i, cnt );
}
2.二分法
实际上，对于一个数x，其解必定在（0,x）之间，那么将x/2作为猜测值，若大了，说明解在区间（0，x/2）之间，若小了，说明解在区间（x/2，x）。
#include
using namespace std;
int main()
{
double x;
scanf("%lf", &x);
double left = 0.0, right = 0.0, a = 0.001, i = x / 2;
int cnt = 0; //计步
while(abs(i*i - x) > a) //当i^2与x误差小于0.001，退出循环
{
if(i * i - x < 0)
{
left = i;
i += (right - left) / 2; // 如果真实解在右侧区间，则更新i为新区间中点
cnt += 1;
}
else
{
right = i;
i -= (right - left) / 2; //如果真实解在左侧区间，更新i为新区间中点
cnt ++;
}
}
printf("sqrt(x) = %lf,const = %d", i, cnt);
}