大数阶乘的计算（五）

发布: 2007-6-21 21:57 | 作者: | 来源: | 查看: 19次 | 进入软件测试论坛讨论

对计算（四）我总觉得没有发挥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亿。不过那时字符串的长度可能也会因超长溢出的。