大数除法之迭代法

只是呼吸

我在编写高精表达式计算器中大量的用到字符串规范化，和高精数的规范化，和高精数范围缩小化，好处就是逻辑清晰（这个很重要，逻辑清晰在整个程序设计中都是非常重要的！），程序设计简单易调试。

你是写的应用程序，就是你的那个“落叶计算机”，（我平时都在用，蛮好用的）肯定是要处理大量的小数，肯定要从顶层把这些设计清楚。我现在只是写了整数的加、减、乘、除。小数的加、减、乘、除一个也没有。主要是没有任务目标。

我的迭代法也是规约了除数的，和你的原理差不多，但没有规约被除数，

这个是我没有留意的，可以说是思维局限。我的做法是：把原来是\(10^8\)进制的被除数 和 除数 都扩大\(10^k\)  倍。扩大以后的被除数 和 除数 仍然采用\(10^8\)进制。这时除数的第一位数字（最高位）就能保证是 \(9\)个数字。
从你们的实践来看，我的这个办法可能臃肿。

落叶

只是呼吸 发表于 2018-1-13 17:56
你是写的应用程序，就是你的那个“落叶计算机”，（我平时都在用，蛮好用的）肯定是要处理大量的小数， ...

自己动手打造“超高精度浮点数类” - HouSisong的专栏
http://blog.csdn.net/housisong/article/details/525215
具疯狂计算器的作者说，他的程序就是调用的这个人的c类库，进行复杂运算时，在算法一样的情况下，速度要比我快好几倍，我计算器1.2版以后，没有想法进行计算器的后期开发，所以也没有研究这个人的代码，这个网址是这个人的个人网页，应该有很多好的东西。
这个地址有源码下载：http://www.itpub.net/forum.php?m ... 6363&highlight=

只是呼吸

惭愧啊，今天发现第27楼我写的那个程序有问题。
      数字（十进制）： \(99999……999（共40个9\)）
      数字（十进制）： \(99999……999（共20个9\)）
这两个数字相除，结果应该是：
       数字（十进制）： \(10000000000  0000000001（共19个0\)）
而用第27楼我写的那个程序的结果是：
       数字（十进制）： \(10000000000  0000000000（共20个0\)）
也就是说，末尾的最后一位不对。
       我现在是将第27楼的代码作如下修改：
       在程序的第53行加入一个函数：  

1. Newton_alter(qut,s,len);

复制代码

这个函数的具体实现是：

1. static int Newton_alter(UINT32 *qut,int s,int len)
   
2. {
   
3.         int i;
   
4.        
   
5.         if(qut[s-len]+5>=100000000)
   
6.         {
   
7.                 for(i=s-len+1;i<=s;i++)
   
8.                 {
   
9.                         qut[i]++;
   
10.                                 if(qut[i]>=100000000)
    
11.                                 {
    
12.                                         qut[i]-=100000000;               
    
13.                                 }
    
14.                                 else
    
15.                                 {
    
16.                                         return 0;
    
17.                                 }
    
18.                 }
    
19.         }
    
20.   return 0;
    
21. }

复制代码

这样，就能得到正确的结果。
现在看来，这个牛顿除法实际上就是一个“近似计算法”，不知道在什么时候又不对了。一直心存顾虑。

落叶

只是呼吸 发表于 2018-2-5 12:01
惭愧啊，今天发现第27楼我写的那个程序有问题。
      数字（十进制）： \(99999……999（共40个9\)）
   ...

象你这种类型的错误我也范过很多，我把这种错误定义为结构化编程产生的错误，也就是我们利用数据的结构特征或隐含的其它特征作为编程的依据，这种方法的缺点是会出现很多难以确定的错误，所以我在后期的编程中非常注重逻辑上的正确和清晰，每完成一个程序，我会从逻辑上推算程序的合理性，例：开始我算除法的余数是从估商法的中间结果取余数，后来我通过已测试好的除法程序算余数，也就是：余数=被除数-整数商（除法程序算出的足够的商取整）*除数；
我这次所述迭代法的初值确定，我的要求就是这个初值是算出来了，这也是我比较满意的地方。
另外我的乘方整指数乘方的指数分解是算出来的，而传统精典程序是根据数在cpu内存中的存储特征分解指数。明显我的方法适用范围更广，更好理解，而传统方法效率更高。
网上宣传得很牛的一个游戏中的开平方程序，也是根据cpu 的构造特征得出的算法，其优缺点显而易见。

只是呼吸

后来我通过已测试好的除法程序算余数，也就是：余数=被除数-整数商（除法程序算出的足够的商取整）*除数；
我这次所述迭代法的初值确定，我的要求就是这个初值是算出来了，这也是我比较满意的地方。

明白了！就是在最后的步骤中，把牛顿除法的“近似商”，用：余数=被除数-整数商*除数  来最终确定为 “精确商”。
这个办法我也是想过的，只是觉得还要做一次乘法，一至两次加法（或者减法），总是想”省略“。
现在看来，还是要正确得出结果才是首要任务。不能把“不定时炸弹”留到将来。

落叶

现在看来，还是要正确得出结果才是首要任务。不能把“不定时炸弹”留到将来。

我设计程序时是先确定怎样在大的方向不错的情况下快速完成程序，然后再考虑效率，如果把设计程序比喻成一个人的话，我觉得效率是腿，总体规划是头脑，正确完成任务为前进的方向。