| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 414 人关注过本帖
标题:用牛顿迭代法做的快速除法程序
只看楼主 加入收藏
ysr2857
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:403
专家分:24
注 册:2020-2-10
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:24 
用牛顿迭代法做的快速除法程序
用牛顿迭代法做的除法程序(稍加修改可以用于大整数的快速除法,欢迎沟通探讨),这回准确了,小数点后也准确,代码如下:

Private Sub Command1_Click()
Dim a, b
a = Text1: b = Text2: b3 = b
If Len(b) = 1 Then
X1 = Mid(b, 1, 1): X2 = 1 / X1
Else
X1 = Mid(b, 1, 2): X2 = 10 / X1
End If
x = Mid(X2, 1, 4)
y = 0: x3 = 0
If Len(b) = 1 Then
b = b
Else
b1 = Mid(b, 1, 1)
b2 = Mid(b, 2)
b = b1 & "." & b2
End If

Do While Abs(x3 - x) >= 0.0000000001

Print x
y = Val(x * (2 - b * x))
x3 = x
x = Val(y)
Loop
a1 = Mid(a, 1, Len(a) - Len(b3) + 1)
a2 = Right(a, Len(b3) - 1)
a = a1 & "." & a2
Print a
s = Len(a) - Len(b3)
Text3 = a * y
End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
Text3 = ""

End Sub
搜索更多相关主题的帖子: Mid Sub 除法 If 牛顿 
2021-02-06 07:23
ysr2857
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:403
专家分:24
注 册:2020-2-10
收藏
得分:0 
大数除法之迭代法
除法:u/y=u*(1/y);

      先讲一下倒数迭代式:x1=(2-y*x0)*x0,x0是y的倒数的近似值,它必须要小于y的倒数。另外迭代式中的乘法子程序要选用快速乘法(如FFT算法的乘法子程序)。

      否则迭代法的除法速度是很慢的,远远小于估商法。
例:求 6666666/23333 。
转换问题变成求 6.666666/2.3333*10^2 。先求 1/2.333,初值设为 10/23=0.4 ,
第一次迭代: x=0.4
第二次迭代: x=0.426
第三次迭代: x=0.4285620
第四次迭代:x=0.42857755……
第五次迭代 :x=0.42857755……
需要注意的是最后的答案只有一半的位数是正确的,计算答案得到 6666666/23333=285.71833……。

实现细节:

1.为了方便可以将整数转换成多项式:a0+a1*10^-1+a2*10^-2+…………
2.类似多项式求逆,每一次计算时只需要取 b 的前 n 位参加计算,同样答案需要舍弃后面的位数。(可以直接把b的位数写全,这样稍慢些但编程简单)
3.迭代初值在 (0,2/b) 收敛,那么初值可以设置为答案的第一位(例如 b=7时初值设为 0.1 , b=1.23时,初值设为 0.8)。
例如上例中:
第一次迭代:x=x(2-x*2.3)=0.4
第二次迭代:x=x(2-x*2.33)=0.426
………………
2021-02-06 08:56
yuma
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:银河系
等 级:版主
威 望:12
帖 子:1355
专家分:2058
注 册:2009-12-22
收藏
得分:10 
跟直接计算感觉差不多。
图片附件: 游客没有浏览图片的权限,请 登录注册

例,22222222555552233/7 结果会出现科学计数法数字,和直接计算方法相同。

[此贴子已经被作者于2021-2-6 10:19编辑过]


心生万象,万象皆程序!
本人计算机技术站:http://bbs.
2021-02-06 10:11
ysr2857
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:403
专家分:24
注 册:2020-2-10
收藏
得分:0 
谢谢关注和指导!主要是用于大整数的快速除法的,要配合快速乘法程序,否则就更慢!谢谢!给您打分!
2021-02-06 10:42
ysr2857
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:403
专家分:24
注 册:2020-2-10
收藏
得分:0 
大整数必须转化成字符串再计算,中间过程可以采用整数,最后再移动小数点。根据验证数据的规律选择精确度,就是小数点后所要求的精确度的2倍可能是,就是要求10的必须精确到20位最后再丢掉末尾10位。
2021-02-06 10:53
ysr2857
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:403
专家分:24
注 册:2020-2-10
收藏
得分:0 
看几个例子:10002/3=3334,15/3=4.99999999999999,这个不对了,不过也没事,余数若大于等于除数,可以减去除数,商值再加上减的次数。
105/3=35,207/3=68.9999999999999(实际应该为69),2007/3=668.999999999999(实际应该是669),20007/3=6668.99999999999(实际应该是6669),20001/3=6666.99999999999(实际是6667),10002/3=3334(这个对),42/3=14(这个也对),402/3=134,204/3=67.9999999999999(应该是68),702/3=234.405/3=135,705/3=235这样的对。
10001/11=909.181818181818,10001/17=588.294117647059这个也对,可能仅限于3,还是也有其他除数会有此情况?
411/3=137这个也对,4101/3=1367这个也对,343/7=49,49/7=7.00000000000001(这个也不对,不知道如何处理,或许不用处理,我们移动小数点后仅仅取到整数部分就是仅仅取到7,可能倒是不用考虑的)。
2021-02-06 10:59
yuma
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:银河系
等 级:版主
威 望:12
帖 子:1355
专家分:2058
注 册:2009-12-22
收藏
得分:0 
回复 6楼 ysr2857
理论上,代码越多,运行速度越慢。

下面计算 1234567891234567 /7

你用你说的这种方法,直接 debug.print它的结果给我写段代码。

我直接debug.print 它的结果。

然后我测试一下这两种代码的运行速度。

心生万象,万象皆程序!
本人计算机技术站:http://bbs.
2021-02-08 11:15
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:209
帖 子:2007
专家分:11168
注 册:2014-12-6
收藏
得分:0 
回复 7楼 yuma
"理论上,代码越多,运行速度越慢。"
哪里的理论?
那你认为:
程序代码:
a=1234567891234567 /7
a=a /7
a=a /7
a=a /7
a=a /7
a=a /7
a=a /7
a=a /7
a=a /7
a=a /7


程序代码:
a=1234567891234567 /7
for i=1 to 9
  a=a /7
next

谁更快呢?
达夫设备了解下,其本质是利用代码空间换取执行效率的算法。

能编个毛线衣吗?
2021-02-08 16:57
yuma
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:银河系
等 级:版主
威 望:12
帖 子:1355
专家分:2058
注 册:2009-12-22
收藏
得分:0 
牛皮,第一组代码更快。

第一组:
耗时:0.0018毫秒
耗时:0.0016毫秒
耗时:0.0014毫秒

第二组:
耗时:0.0041毫秒
耗时:0.0037毫秒
耗时:0.004毫秒

心生万象,万象皆程序!
本人计算机技术站:http://bbs.
2021-02-08 17:59
ysr2857
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:13
帖 子:403
专家分:24
注 册:2020-2-10
收藏
得分:0 
回复 8楼 wmf2014
欢迎老师沟通!谢谢!好久不见,祝愿新年快乐!
2021-02-08 18:30
快速回复:用牛顿迭代法做的快速除法程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.077045 second(s), 9 queries.
Copyright©2004-2021, BCCN.NET, All Rights Reserved