接着上次的继续聊吧
上次讲到了大数除法，通过试商来求取商的单个位的值。在这个过程中用到了大数的乘法，准确地说是大数与常规数的乘法。
这一做法虽然可行，但效率比较低，原因是乘法本身就是个高成本的运算。
当然，在试商的过程中使用二分法可以减少乘法的运算次数，但由于结果只是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;
}
重剑无锋，大巧不工
