标题:用牛顿迭代法做的快速除法程序
取消只看楼主
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
结帖率:100%
已结贴  问题点数:20 回复次数:42 
用牛顿迭代法做的快速除法程序
用牛顿迭代法做的除法程序(稍加修改可以用于大整数的快速除法,欢迎沟通探讨),这回准确了,小数点后也准确,代码如下:

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: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册: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
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
谢谢关注和指导!主要是用于大整数的快速除法的,要配合快速乘法程序,否则就更慢!谢谢!给您打分!
2021-02-06 10:42
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
大整数必须转化成字符串再计算,中间过程可以采用整数,最后再移动小数点。根据验证数据的规律选择精确度,就是小数点后所要求的精确度的2倍可能是,就是要求10的必须精确到20位最后再丢掉末尾10位。
2021-02-06 10:53
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册: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
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
回复 8楼 wmf2014
欢迎老师沟通!谢谢!好久不见,祝愿新年快乐!
2021-02-08 18:30
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
回复 9楼 yuma
必须给予大整数的快速乘法基础上才能更快,数据小的没有可比性,没有大整数的快速乘法程序同样很慢。把除法转化成乘以倒数,倒数的精确度靠迭代次数保证的,精确度不是一位一位增长的,而是几位几位增长的,迭代次数小于试商次数,所以速度是快的。
小的数据是无法比较甚至更慢的,因为不管大小都需要迭代,而直接除不用迭代,小数据在计算器中有固化的程序可能是,原理不太清楚或者是转化位二进制(反正和加减法一样直接出结果的),所以反而更快(貌似试商可能原理也不是试商法),再深究我也不知道,说不清楚,等有了学会了快速乘法程序再编程比较一下就明白了。
2021-02-08 18:51
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
回复 9楼 yuma
谢谢您关注,回复和沟通指导!祝您新年快乐!
2021-02-08 18:52
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
回复 13楼 yuma
大整数的加减法容易办到,直接模仿手工计算就行,而且可以从高位算起,当然从低位算起再道序也行,速度很快,就是直接模仿手工竖式算法就行,注意进位(或借位)的问题。乘法和除法我也仅会模仿手工计算的方法,效率低速度慢,不讲了。
把大整数的加法和减法的可调用程序发一下,仅供参考:
加法程序:
 Public Function MPC1(D1 As String, D2 As String) As String 'jiafa
Dim x, Y '两数长度

If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
d3 = D1
Else
D4 = D2
d3 = String(Len(D2) - Len(D1), "0") & D1
End If
x = Len(d3): Y = Len(D4)
Dim a() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim a(1 To x)
ReDim B1(1 To Y)
ReDim C1(1 To x)
ReDim E1(1 To x)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 'D2
JW = 0 '进位清0
B1(J) = Mid$(D4, J, 1) '每位数
For I = x To 1 Step -1  'D1
   a(I) = Mid$(d3, I, 1) '每位数
   C1(I) = a(I) + B1(I) + JW '计算jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To x
  If JW = 0 Then
  MPC1 = MPC1 & E1(r)
  Else
  jc = jc & E1(r)
  MPC1 = JW & jc
  End If
  Next
  
End Function

减法程序(必须大的减去小的不输出负值):
 Public Function MPC(D1 As String, D2 As String) As String ';jianfaqi
Dim x, Y ';两数长度
If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
d3 = D1
Else
D4 = D2
d3 = String(Len(D2) - Len(D1), "0") & D1
End If
x = Len(d3): Y = Len(D4)
Dim a() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim a(1 To x)
ReDim B1(1 To Y)
ReDim C1(1 To x)
ReDim E1(1 To x)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 ';D2
JW = 1 ';yu jie weichuzhi
B1(J) = Mid(D4, J, 1) ';每位数
For I = x To 1 Step -1  ';D1
   a(I) = Mid(d3, I, 1) ';每位数
   C1(I) = 10 + a(I) - B1(I) - 1 + JW ';计算jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To x
  MPC = MPC & E1(r)
  For I = 1 To Len(MPC)
    If Not Mid(MPC, I, 1) = "0" Then
        Exit For
    End If
Next
strtmp = Mid(MPC, I)
  If Len(strtmp) = 0 Then
  MPC = "0"
  Else
MPC = strtmp
End If
  Next
  
  
End Function
2021-02-08 19:14
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
回复 13楼 yuma
这两个程序(加法和减法)都是仅仅计算整数的,要计算带小数的要移动小数点变化为整数(二者移动的位数必须相同,不够的补0),计算完再把小数点移动回去。
2021-02-08 19:20



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-504820-1-1.html




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

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