接着上次的继续聊吧
上次讲到了大数除法,通过试商来求取商的单个位的值。在这个过程中用到了大数的乘法,准确地说是大数与常规数的乘法。
这一做法虽然可行,但效率比较低,原因是乘法本身就是个高成本的运算。
当然,在试商的过程中使用二分法可以减少乘法的运算次数,但由于结果只是10以内的数(PS:我们仍然在讲十进制下的运算),所以二分法在这里的效果并不明显,平均大约只能节省一两次乘法运算。
相比之下,我们用减法来代替乘法,可以提高更多的效率,毕竟减法运算的成本非常低。
具体步骤是将待算部分与除数作比较;如果待算部分比除数大,则将待算部分减去除数;重复执行这一过程,直至待算部分小于除数;这时减法执行的次数即是这一位的商数。
这种方法适用于各种进制的大数运算,但进制越低越有效。如果使用二进制,那最多做一次就够了。如果使用一万进制,那我建议还是用乘法运算吧,因为减法过程不能应用二分法来提高效率。
大数的除法就讲到这里。以上的分析都是针对大整数的,下面聊聊小数该如何处理。
在说小数的处理之前,先得解决它的存储问题。就不废话了,直奔主题。
目前成熟的小数存储方案有两种,一是定点数,二是浮点数。
这里的点指的就是小数点。
所谓定点数,既是小数点位置固定的数。比如一个实际存储位数为N的空间,我们用它的前K位表示整数部分,后面剩下的N-K位表示小数部分。
所谓浮点数,即是小数点位置可以浮动的数。这种表示法与科学计数法一致,只不过这里一般将尾数规范至0到1之间,其指数部分的数值相当于小数点的位置。
定点数的优点在于操作简单,如果忽略小数点的存在,那它就是个整数。
浮点数的优点在于能表达的数值范围更大(与相同精度的定点数相比),但操作略为复杂,因为运算涉及尾数和指数两个部分。
实际中该使用哪种数,需要具体问题具体分析。以这里的第四题求黄金分割数为例,因为我们很容易确定它是一个大于0.5小于1的数,此时用定点数来存储将是简单有效的。
提醒一下,以上的讨论中我一直没提负数的事。对于负数都是通过一个专门的符号位来表达的,这于整数类似,也可以用原码或补码。关于这些有兴趣的朋友可以自己找一下相关资料,这里就不多讲了(一讲开就收不住了)。
下面开始具体讲解我的代码。
在我的代码中,小数是用定点数来表示的。定点数用一个char型数组表示,每个元素表示小数的一个十进制位。
其中第0元素表示小数的整数部分,之后第1元素表示十分位、第2元素表示百分位等等,即小数点在第0元素与第1元素之间。
上次讲到了大数除法,通过试商来求取商的单个位的值。在这个过程中用到了大数的乘法,准确地说是大数与常规数的乘法。
这一做法虽然可行,但效率比较低,原因是乘法本身就是个高成本的运算。
当然,在试商的过程中使用二分法可以减少乘法的运算次数,但由于结果只是10以内的数(PS:我们仍然在讲十进制下的运算),所以二分法在这里的效果并不明显,平均大约只能节省一两次乘法运算。
相比之下,我们用减法来代替乘法,可以提高更多的效率,毕竟减法运算的成本非常低。
具体步骤是将待算部分与除数作比较;如果待算部分比除数大,则将待算部分减去除数;重复执行这一过程,直至待算部分小于除数;这时减法执行的次数即是这一位的商数。
这种方法适用于各种进制的大数运算,但进制越低越有效。如果使用二进制,那最多做一次就够了。如果使用一万进制,那我建议还是用乘法运算吧,因为减法过程不能应用二分法来提高效率。
大数的除法就讲到这里。以上的分析都是针对大整数的,下面聊聊小数该如何处理。
在说小数的处理之前,先得解决它的存储问题。就不废话了,直奔主题。
目前成熟的小数存储方案有两种,一是定点数,二是浮点数。
这里的点指的就是小数点。
所谓定点数,既是小数点位置固定的数。比如一个实际存储位数为N的空间,我们用它的前K位表示整数部分,后面剩下的N-K位表示小数部分。
所谓浮点数,即是小数点位置可以浮动的数。这种表示法与科学计数法一致,只不过这里一般将尾数规范至0到1之间,其指数部分的数值相当于小数点的位置。
定点数的优点在于操作简单,如果忽略小数点的存在,那它就是个整数。
浮点数的优点在于能表达的数值范围更大(与相同精度的定点数相比),但操作略为复杂,因为运算涉及尾数和指数两个部分。
实际中该使用哪种数,需要具体问题具体分析。以这里的第四题求黄金分割数为例,因为我们很容易确定它是一个大于0.5小于1的数,此时用定点数来存储将是简单有效的。
提醒一下,以上的讨论中我一直没提负数的事。对于负数都是通过一个专门的符号位来表达的,这于整数类似,也可以用原码或补码。关于这些有兴趣的朋友可以自己找一下相关资料,这里就不多讲了(一讲开就收不住了)。
下面开始具体讲解我的代码。
在我的代码中,小数是用定点数来表示的。定点数用一个char型数组表示,每个元素表示小数的一个十进制位。
其中第0元素表示小数的整数部分,之后第1元素表示十分位、第2元素表示百分位等等,即小数点在第0元素与第1元素之间。
程序代码:
#include<stdio.h> //下面的宏定义了小数的精度,其中ACC表示我们想计算的精度,N表示实际数组的大小 //因为我们说的精度是指小数点后的精确位数,实际长度还要加上整数位及舍入位,所以实际数组长度要多2 #define ACC 100 #define N ACC + 2 //cmp函数:完成两个小数的比较 //a:第一个小数的指针 //b:第二个小数的指针 //n:两个小数的数组长度 //返回值:当a>b时返回一个正数,当a<b时返回一个负数,当a=b时返回0 int cmp(char * a, char * b, int n) { int i; for(i = 0; i < n; i++) //从小数的最高位(即整数部分)开始比较 if(a[i] != b[i]) return a[i] - b[i]; //如果对应位相同则继续向后比较,否则a、b的比较结果等同于这一位的比较结果 return 0; //如果两个数不同,那一定会在上面的循环中返回。能执行到这里,那两个数一定相同 } //sub函数:完成两个小数的减运算 //a:被减数 //b:减数 //n:两个小数的数组长度 //运算结束后,a的值将被修改为差,b的值不变 void sub(char * a, char * b, int n) { int f; //借位标志 for(f = 0; --n >= 0; f = a[n] < 0 ? (a[n] += 10, 1) : 0) //减运算从低位向高位运算,for语句的迭代部分完成借位标志的判断和处理 a[n] -= b[n] + f; } //div函数:完成两个小数的除运算 //a:被除数 //b:除数 //c:商 //n:a、b、c的数组长度 //运算结束后,c的值将为商,b的值不变,a的值可以认为是达到要求精度后的余数 void div(char * a, char * b, char * c, int n) { int i, j; for(i = 0; i < n; i++) //计算从高位向低位进行 { for(c[i] = 0; cmp(a, b, n) >= 0; c[i]++) sub(a, b, n); //先将商的对应位清零,然后开始反复用被除数的待算部分减去除数,同时用商的对应位计数 a[0] = a[0] * 10 + a[1]; //这一句及以下部分是完成余数的进位,形成下一个待算部分 for(j = 1; j < n - 1; j++) a[j] = a[j + 1]; a[n - 1] = 0; } } //golden_number函数:完成黄金分割数的计算 //x:用于存储计算完成后的黄金分割数 //n:x的数组长度 //这里我对原公式进行了一下变换,这将使收敛速度比直接用原公式快一倍 //原迭代公式为 x1 = 1/(1+x0) //继续迭代一步 x2 = 1/(1+x1) //代入上一步即 x2 = (x0 + 1)/(x0 + 2) //将它作为新的迭代公式使用 x1 = (x0 + 1)/(x0 + 2) //大家可以重复以上步骤在可操作的范围内得到自己更快的公式 void golden_number(char * x, int n) { char * p, * a, * b, * c, * t; int i; p = (char *)malloc(n * 3); //本意是为a、b、c申请空间,只不过将三次申请合成一次,提高一些效率,也方便之后的释放 a = p; b = a + n; c = b + n; for(i = 0; i < n; c[i++] = 0); //清空c数组,a和b不需要清零这个动作,这是我确定的。各位在自己的程序中如果不能确定,那建议都做明确的“初始化”这个动作。 do{ //这里完成公式的迭代,a为公式的分子部分,b为公式的分母部分,c将存储a / b的结果 //一轮计算完成后进入下一轮迭代,这时上一轮的结果c将成为这一轮的a(一会儿加上个1就是了),所以在这里做一下互换 t = a; a = c; c = t; for(i = 0; i < n; b[i] = a[i++]); //公式中分子和分母只差1,所以先做整体复制 a[0] += 1; //现在a就是新的分子了 b[0] += 2; //现在b也是新的分母了 div(a, b, c, n); //对公式进行计算 b[0] -= 2; //由于上一步的除法运算并不改变b的值,所以这里将b减去2后它的值就退回成了上一次公式计算的结果 }while(cmp(b, c, n)); //当两次迭代计算的结果差值为0时,终止迭代过程 for(i = 0; i < n; x[i] = c[i++]); //将结果复制到x中返回给调用方 free(p); //一定记得释放你申请的空间 } //output函数:以我们可阅读的方式输出存储在x中的小数 void output(char * x, int n) { int i; printf("%d.", x[0]); for(i = 1; i < n; printf("%d", x[i++])); } int main() { char x[N]; int i; golden_number(x, N); if(x[N - 1] >= 5) for(i = N - 2; i >= 0 && ++x[i] > 9; x[i--] = 0); //四舍五入 output(x, N - 1); return 0; }
重剑无锋,大巧不工