很难想象只要改动几句代码就可以大幅提高执行的效率,在前几篇文章中我写了几种大数阶乘的算法(http://www.csdn.net/Develop/read_article.asp?id=28306,http://www.csdn.net/Develop/read_article.asp?id=28308,http://www.csdn.net/Develop/read_article.asp?id=28432),效率都比较低。今日看了homezj(http://www.csdn.net/Develop/article/28/28584.shtm )的代码,很受启发,优化如下:
<一>按每四位进行一次计算:
Sub calcfactorial(ByVal num As Long, Optional ByRef factorial As String)
Dim numlen As Long, last As Long, i As Long, j As Long, temp As Long
Dim result() As Long, s() As String, stime As Double numlen = 1 stime = Timer ReDim result(1 To numlen) result(1) = 1 i = 0 Do While i < num i = i + 1 last = 0 For j = 1 To numlen temp = result(j) * i + last result(j) = temp Mod 10000 last = temp \ 10000 Next Do While Not last = 0 ReDim Preserve result(1 To numlen + 1) result(numlen + 1) = last Mod 10000 last = last \ 10000 numlen = UBound(result) Loop Loop ReDim s(1 To numlen) For i = 2 To numlen s(i) = Format(result(numlen + 1 - i), "0000") Next s(1) = result(numlen)
factorial = Join(s, "") Debug.Print num & "! : 用时 "; Timer - stime & " 秒, 结果 " & Len(factorial) & " 位,前5位为 " & Left(factorial, 5) ''''Debug.Print factorial Erase s Erase result End Sub
Private Sub Command1_Click() For i = 1 To 20 calcfactorial i * 1000 Next End Sub
输出结果: ''''1000! : 用时 7.82500000059372E-02 秒, 结果 2568 位,前5位为 40238 ''''2000! : 用时 .391499999997905 秒, 结果 5736 位,前5位为 33162 ''''3000! : 用时 .968875000005937 秒, 结果 9131 位,前5位为 41493 ''''4000! : 用时 1.78174999999464 秒, 结果 12674 位,前5位为 18288 ''''5000! : 用时 2.84412500000326 秒, 结果 16326 位,前5位为 42285 ''''6000! : 用时 4.20387500000652 秒, 结果 20066 位,前5位为 26839 ''''7000! : 用时 5.84387500000594 秒, 结果 23878 位,前5位为 88420 ''''8000! : 用时 7.75012500000594 秒, 结果 27753 位,前5位为 51841 ''''9000! : 用时 9.98512500000652 秒, 结果 31682 位,前5位为 80995 ''''10000! : 用时 12.5160000000033 秒, 结果 35660 位,前5位为 28462 ''''11000! : 用时 15.2818750000006 秒, 结果 39681 位,前5位为 31624 ''''12000! : 用时 18.4063750000059 秒, 结果 43742 位,前5位为 12018 ''''13000! : 用时 21.7975000000006 秒, 结果 47838 位,前5位为 77871 ''''14000! : 用时 25.5320000000065 秒, 结果 51969 位,前5位为 13864 ''''15000! : 用时 29.5627499999973 秒, 结果 56130 位,前5位为 27465 ''''16000! : 用时 33.90625 秒, 结果 60320 位,前5位为 51187 ''''17000! : 用时 38.5786249999946 秒, 结果 64538 位,前5位为 13797 ''''18000! : 用时 43.5477499999979 秒, 结果 68781 位,前5位为 13525 ''''19000! : 用时 48.84375 秒, 结果 73048 位,前5位为 18269 ''''20000! : 用时 54.4375 秒, 结果 77338 位,前5位为 18192
<二>按每五位进行一次计算:
Sub calcfactorial(ByVal num As Long, Optional ByRef factorial As String)
Dim numlen As Long, last As Long, i As Long, j As Long, temp As Long
Dim result() As Long, s() As String, stime As Double
numlen = 1 stime = Timer ReDim result(1 To numlen) result(1) = 1 i = 0 Do While i < num i = i + 1 last = 0 For j = 1 To numlen temp = result(j) * i + last result(j) = temp Mod 100000 last = temp \ 100000 Next Do While Not last = 0 ReDim Preserve result(1 To numlen + 1) result(numlen + 1) = last Mod 100000 last = last \ 100000 numlen = UBound(result) Loop Loop ReDim s(1 To numlen) For i = 2 To numlen s(i) = Format(result(numlen + 1 - i), "00000") Next s(1) = result(numlen)
factorial = Join(s, "") Debug.Print num & "! : 用时 "; Timer - stime & " 秒, 结果 " & Len(factorial) & " 位,前5位为 " & Left(factorial, 5) ''''Debug.Print factorial Erase s Erase result End Sub
Private Sub Command1_Click() For i = 1 To 20 calcfactorial i * 1000 Next End Sub
输出结果:
1000! : 用时 6.26250000059372E-02 秒, 结果 2568 位,前5位为 40238 2000! : 用时 .297124999997322 秒, 结果 5736 位,前5位为 33162 3000! : 用时 .782000000006519 秒, 结果 9131 位,前5位为 41493 4000! : 用时 1.421875 秒, 结果 12674 位,前5位为 18288 5000! : 用时 2.26612499999464 秒, 结果 16326 位,前5位为 42285 6000! : 用时 3.79700000000594 秒, 结果 20066 位,前5位为 26839 7000! : 用时 4.65625 秒, 结果 23878 位,前5位为 88420 8000! : 用时 6.21899999999732 秒, 结果 27753 位,前5位为 51841 9000! : 用时 8.375 秒, 结果 31682 位,前5位为 80995 10000! : 用时 9.98512500000652 秒, 结果 35660 位,前5位为 28462 11000! : 用时 12.2351250000065 秒, 结果 39681 位,前5位为 31624 12000! : 用时 14.6882500000065 秒, 结果 43742 位,前5位为 12018 13000! : 用时 17.4696249999979 秒, 结果 47838 位,前5位为 77871 14000! : 用时 20.4071249999979 秒, 结果 51969 位,前5位为 13864 15000! : 用时 23.625 秒, 结果 56130 位,前5位为 27465 16000! : 用时 27.0783749999973 秒, 结果 60320 位,前5位为 51187 17000! : 用时 30.875 秒, 结果 64538 位,前5位为 13797 18000! : 用时 34.8131250000006 秒, 结果 68781 位,前5位为 13525 19000! : 用时 39.0320000000065 秒, 结果 73048 位,前5位为 18269 20000! : 用时 43.5783749999973 秒, 结果 77338 位,前5位为 18192
可以看出,按五位五位的进行计算效率较高。但有一点必须明确,末尾多个“0”参与运算浪费了时间和内存,所以缩短运行时间仍有相当大的空间。
没有相关教程
|