找回密码
 欢迎注册
楼主: 落叶

[原创] 大数除法之迭代法

[复制链接]
发表于 2018-1-13 17:56:58 | 显示全部楼层
我在编写高精表达式计算器中大量的用到字符串规范化,和高精数的规范化,和高精数范围缩小化,好处就是逻辑清晰(这个很重要,逻辑清晰在整个程序设计中都是非常重要的!),程序设计简单易调试。


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

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

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

点评

你的不臃肿,我的方法更臃肿,效率也比你的低,但我更注重逻辑的清晰,思路的完成,设计的模块性。  发表于 2018-1-13 18:38
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-1-13 20:49:29 | 显示全部楼层
本帖最后由 落叶 于 2018-1-13 21:19 编辑
只是呼吸 发表于 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=

点评

是,感谢分享。我已经复制了,慢慢的研究。  发表于 2018-1-13 22:21
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-5 12:01:15 | 显示全部楼层
本帖最后由 只是呼吸 于 2018-2-5 12:36 编辑

惭愧啊,今天发现第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 15:13:42 | 显示全部楼层
本帖最后由 落叶 于 2018-2-5 20:19 编辑
只是呼吸 发表于 2018-2-5 12:01
惭愧啊,今天发现第27楼我写的那个程序有问题。
      数字(十进制): \(99999……999(共40个9\))
   ...


象你这种类型的错误我也范过很多,我把这种错误定义为结构化编程产生的错误,也就是我们利用数据的结构特征或隐含的其它特征作为编程的依据,这种方法的缺点是会出现很多难以确定的错误,所以我在后期的编程中非常注重逻辑上的正确和清晰,每完成一个程序,我会从逻辑上推算程序的合理性,例:开始我算除法的余数是从估商法的中间结果取余数,后来我通过已测试好的除法程序算余数,也就是:余数=被除数-整数商(除法程序算出的足够的商取整)*除数;
我这次所述迭代法的初值确定,我的要求就是这个初值是算出来了,这也是我比较满意的地方。
另外我的乘方整指数乘方的指数分解是算出来的,而传统精典程序是根据数在cpu内存中的存储特征分解指数。明显我的方法适用范围更广,更好理解,而传统方法效率更高。
网上宣传得很牛的一个游戏中的开平方程序,也是根据cpu 的构造特征得出的算法,其优缺点显而易见。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-6 15:22:49 | 显示全部楼层
后来我通过已测试好的除法程序算余数,也就是:余数=被除数-整数商(除法程序算出的足够的商取整)*除数;
我这次所述迭代法的初值确定,我的要求就是这个初值是算出来了,这也是我比较满意的地方。

明白了!就是在最后的步骤中,把牛顿除法的“近似商”,用:余数=被除数-整数商*除数  来最终确定为 “精确商”。
这个办法我也是想过的,只是觉得还要做一次乘法,一至两次加法(或者减法),总是想”省略“。
现在看来,还是要正确得出结果才是首要任务。不能把“不定时炸弹”留到将来。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-2-6 16:54:21 | 显示全部楼层
现在看来,还是要正确得出结果才是首要任务。不能把“不定时炸弹”留到将来。

我设计程序时是先确定怎样在大的方向不错的情况下快速完成程序,然后再考虑效率,如果把设计程序比喻成一个人的话,我觉得效率是腿,总体规划是头脑,正确完成任务为前进的方向。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 19:56 , Processed in 0.058351 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表