Board logo

标题: 如何实现超大数据的运算??? [打印本页]

作者: 只爱陌生人    时间: 2006-9-15 16:15     标题: 如何实现超大数据的运算???

VB能够表示的最大数据为多少???我用下面的代码片段测试
Private Sub Command1_Click()
    Dim valDblAs Double
    Print Len(Text1.Text)
    valDbl = Val(Text1.Text)
    Print valDbl
End Sub
然后输入308个“9”,可以正常转换,再多输入一个9,就发生溢出错误,是不是说明最多可以表示308位的数字呢?
再用 windows 自带的计算器,发现最大可输入22048^9999,得到2.23*******E+43429,比VB里也要大许多。

那么,如何在VB里实现大数的计算呢???曾幼稚地想过用数组保存各位数字,并以此来实现乘法,但面对如此大的数据,光是几个for循环就够增加时间复杂度了,而且也要创建如此大容量的数组!
  dim fac1(100000)as string*1  ,还要保证进位准确。两个如此大的数相乘,如果一个乘数为m位,另一个为n 位,那么其结果最多可达到m+n位。相当于要创建四个这样容量的数组!空间也够大(虽然相对于时间来说是 小case)
        对这个问题,有没有好的算法啊???
作者: 只爱陌生人    时间: 2006-9-16 11:03

其实这种超大数据的精确计算没有什么实际用处,只不过是一时心血来潮,想到这么一个算法而已。
    我初步设计用一个数组的各个元素来代表相应某数的各位上的数字。如用数组fac1(100)=9, fac1(99)=8,fac1(98)=5,fac1(97)=4来表示数字4589,同样的用另一个数组来表示另一个乘数,之后,用fac1(100)来和另一乘数fac2()的各个元素相乘,并把结果保存在另一个数组result(200)的相应元素中。接着是fac1(99)和fac2()各位相乘,……这样,只通过10以内的乘法就可以实现了。
    但是,这样遇到的最大的问题是,一要保证进位准确,比如,9乘9,进位8,该位留1,而且也要判断进位上去的8加上原位的数是否还要继续进位,依次类推。二是,如此大的数据,空间复杂度倒还好说,可时间复杂度是不容忽视的。按我的算法,至少两个for嵌套,每层循环的次数就要看数据的大小位数了,所以也很难。
作者: Nothing    时间: 2006-9-16 11:55

VB的数据算法是有大小的,你整308个9当然要出错了.
大数位计算一般都是通过字符串来实现的。你可以研究一下这个例子,大数阶乘的计算<
作者: 只爱陌生人    时间: 2006-9-17 17:27

谢谢Nothing!
上面这段代码对我很有启发。尤其是关于进位的那一段,
j = 0
        Do Until j > intR
            intA(j) = intT(j) Mod 10
            If intT(j) >= 10 Then intT(j + 1) = intT(j + 1) + intT(j) \ 10
            j = j + 1
        Loop
在启发之下,初步写出以下代码来实现数组乘法:
Option Explicit
Private Sub Command1_Click()
    Dim fac1(100) As Integer        '保存被乘数各位数字
    Dim fac2(100) As Integer        '保存乘数各位数字
    Dim result(200) As Integer      '保存结果
   
    Dim lenOfFac1 As Integer        '保存被乘数的字符长度
    Dim lenOfFac2 As Integer        '保存乘数的字符长度
   
    Dim i As Integer, j As Integer, p As Integer, q As Integer
    Dim pos As Integer, m As Integer, n As Integer
    'Debug.Print "result(100) =  " & result(100)
    lenOfFac1 = Len(Text1.Text)
    lenOfFac2 = Len(Text2.Text)
    '*********************************************
    '*读取并保存被乘数和乘数到相应的数组
    '
    For i = 0 To lenOfFac1 - 1
        fac1(100 - i) = Val(Mid(Text1.Text, lenOfFac1 - i, 1))
        'Debug.Print "fac1(" & 100 - i & ")=" & fac1(100 - i),
    Next
    For j = 0 To lenOfFac2 - 1
        fac2(100 - j) = Val(Mid(Text2.Text, lenOfFac2 - j, 1))
        'Debug.Print "fac2(" & 100 - j & ")=" & fac2(100 - j),
    Next
    '************************************************
    '*此处关键是要理解乘数m位与被乘数n位的数字相乘,其结果对应于"十进制数"的m+n-1
    '*之后,再转换到数组的相应元素index中
   For m = 1 To lenOfFac2          '控制乘数各位
        For n = 1 To lenOfFac1     '控制被乘数各位
            result(201 - (m + n - 1)) = result(201 - (m + n - 1)) + fac1(100 - n + 1) * fac2(100 - m + 1)
            If result(201 - (m + n - 1)) >= 10 Then result(201 - (m + n - 1) - 1) = result(201 - (m + n - 1) - 1) + result(201 - (m + n - 1)) \ 10
               
            result(201 - (m + n - 1)) = result(201 - (m + n - 1)) Mod 10
            Debug.Print "result(201-(" & m & "+" & n & "-1))=" & result(201 - (m + n - 1)), _
                        "result(201-(" & m & "+" & n & "-1)-1)=" & result(201 - (m + n - 1) - 1)
        Next n
    Next m
   
    For p = 0 To 200
        If result(p) <> 0 Then
            pos = p
            Exit For
        End If
    Next
    Debug.Print "pos=" & pos
    Text3.Text = ""
    For q = pos To 200
        Text3.Text = Text3.Text & result(q)
    Next
         
     Debug.Print "len(text3)=" & Len(Text3.Text)
End Sub

Private Sub Text1_KeyPress(KeyAscii As Integer)
    'Debug.Print KeyAscii,
    If KeyAscii <> 8 And (KeyAscii < 48 Or KeyAscii > 57) Then
        KeyAscii = 0
    End If
End Sub

Private Sub Text2_KeyPress(KeyAscii As Integer)
'*只能输入数字和BackSpace键.Text1与此相同
    If KeyAscii <> 8 And (KeyAscii < 48 Or KeyAscii > 57) Then
        KeyAscii = 0
    End If
End Sub

以上可以实现不超过100位的整数的相乘.当然,暂时还没有进行错误处理
作者: 只爱陌生人    时间: 2006-9-18 11:20

关于这个问题的更好算法,请参见http://www.programfan.com/club/showbbs.asp?id=192389




欢迎光临 编程开发论坛 (http://bbs.lihuasoft.net/) Powered by Discuz! 6.0.0