大数阶乘的计算(五)

王朝vb·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

对计算(四)我总觉得没有发挥Long类型的最大潜力,一定是我的算法还有改进余地。经进一步推敲,终于又有了突破,速度一下子又提高 4 倍!同一台机器上10000!用时9.8秒,而且大胆的算了一次20000!,啊,43秒搞定。现将代码贴出,供大家参考,看还能不能再快了?

Private Function cacl(num As Long) As String

Dim numlen As Long, last As Long, x As Long

Dim i As Long, m As Long, n As Long, nl As Long, s0 As String

Dim result() As Long, starttime As Single, s() As String

numlen = 1

starttime = Timer

ReDim result(1 To numlen)

nl = 9 - Len(CStr(num)) '根据两数相乘最大得数长度,不会超过两数长度总和的原理,

'让数组中每个元素长度与阶乘数长度之和不能超过9,以防止溢出。

If nl < 1 Then nl = 1 '最小长度是1位,若真到了这么大的数,恐怕没人会去试了^-^

n = 10 ^ nl '缓存用于分隔大数的被除数,数组中每个元素的长度是 nl,该数就是10的 nl 次方

result(1) = 1

x = 1

Do While x <= num

last = 0

For i = 1 To numlen

m = result(i) * x + last '数组中每个元素进行与待乘数相乘后,再加上上次进位数

result(i) = m Mod n '分隔大数

last = m \ n '保存进位数并等待累计进下一个数组元素

Next

If last > 0 Then

m = Len(CStr(last)) \ nl + 1 '对超过数组元素上限的进位数要增加数组大小,并按长度nl分隔

ReDim Preserve result(1 To numlen + m)

For i = 1 To m

result(numlen + i) = last Mod n

last = last \ n

Next

numlen = UBound(result)

End If

x = x + 1

Loop

ReDim s(1 To numlen)

s0 = String(nl, "0") '对长度不足nl的数组元素要在前面补0,不然结果就在错特错了

For i = 1 To numlen

s(i) = Format(result(numlen + 1 - i), s0) '格式化补 0 每个数组元素

Next

s(1) = Val(s(1))

If s(1) = 0 Then s(1) = "" '最高位要去掉0,虽对得数没影响,但位数会错。

cacl = Join(s, "")

Debug.Print num & "! : 用时 "; Timer - starttime & " 秒, 结果 " & Len(cacl) & " 位"

End Function

Private Sub Command1_Click()

Dim i As Long

'cacl 20000

For i = 1 To 9

cacl i * 100

Next

For i = 1 To 10

cacl i * 1000

Next

End Sub

计算结果:

100! : 用时 0 秒, 结果 158 位

200! : 用时 0 秒, 结果 375 位

300! : 用时 .015625 秒, 结果 615 位

400! : 用时 0 秒, 结果 869 位

500! : 用时 .015625 秒, 结果 1135 位

600! : 用时 .015625 秒, 结果 1409 位

700! : 用时 .03125 秒, 结果 1690 位

800! : 用时 .03125 秒, 结果 1977 位

900! : 用时 .0625 秒, 结果 2270 位

1000! : 用时 .078125 秒, 结果 2568 位

2000! : 用时 .3125 秒, 结果 5736 位

3000! : 用时 .75 秒, 结果 9131 位

4000! : 用时 1.390625 秒, 结果 12674 位

5000! : 用时 2.265625 秒, 结果 16326 位

6000! : 用时 3.3125 秒, 结果 20066 位

7000! : 用时 4.609375 秒, 结果 23878 位

8000! : 用时 6.125 秒, 结果 27753 位

9000! : 用时 7.9375 秒, 结果 31682 位

10000! : 用时 9.890625 秒, 结果 35660 位

这个算法有个缺陷:就是阶乘数位数越大时,效率就越会成倍的下降,当要计算8位数的阶乘时,就会降到与计算(四)等效了,最大阶乘数仍是不能超过20亿。不过那时字符串的长度可能也会因超长溢出的。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航