【讨论】超长精度的计算问题

C.L · 发表于 2010-8-10 01:53:58

近段时间，有些坛友提出超大精度的计算问题，AU3 在这方面好像有点弱，在这里发个讨论贴，看看有没有朋友对这方面有兴趣，本人也写了点代码，抛砖引玉，提供大家讨论。
代码虽然写出来了，但是效率方面好像还不是太好，数据位数大于500位以后延时比较严重，贴出来高手们研究一下，看看有没有更好的办法

关于加减的处理，没想到会这么复杂，代码有点长，处理进位比较麻烦，除法和开方还没有写，这个感觉比加法更麻烦，有待以后再完善吧。

代码里有例子，也是借用了以前的计算题的题目来测试，有兴趣可以下载代码测试，如果计算结果有不准确的地方，也请反馈回来。

热烈欢迎高手们前来讨论

#include-once
#include <array.au3>
;~ #cs
;============Example1.au3
Local $num = InputBox('叠加1-999(除含4和7)', '只能输入数字9', '999999999')
Local $result = ""
Local $i, $j
Local $timer = TimerInit()
For $i = 1 To 99
        If Not StringRegExp($i, "4|7") Then
                $j = $j + $i
        EndIf
        If $i = 9 Then
                $one = $j
        Else
                $two = $j
        EndIf
Next

$len = StringLen($num)
If $len < 2 Then
        $result = $one
Else
        $result = $two
EndIf
$out = ""
$pe = ""
For $i = 1 To $len - 2
        For $j = 1 To $i - 1
                $pe &= "0"
        Next
        $p = '80.' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72' & $pe & '72'
        $result = _MultiX($result, $p)
        $pe = ""
Next
MsgBox(0, "耗时：" & TimerDiff($timer), "1-" & $num & " 相加的数是：" & _RoundX($result) & @CRLF & @CRLF & "未进行四舍五入前的值：" & $result)

;===============Example1.au3 end
;~ #ce

;===============Example2.au3
Dim $input = InputBox("", "输入测试数据"&@CRLF&"格式：数字1^次方", "214748.3647^20")
If $input == "" Then
        MsgBox(0, "", "没有确认输入数据")
        Exit
EndIf
$temp = StringSplit($input, '^')
$num = $temp[1]
$exp = $temp[2]
$result = _ExpX($num, $exp)
$e = StringInStr($result, ".") - 2
MsgBox(0, "超长精度幂运算", $num & '^' & $exp & '=' & $num ^ $exp & @CRLF & _
                "超长精度结果：" & $result & @CRLF & "数据长度：" & StringLen($result) & "   e = +" & $e)
$NewNum2 = StringMid($result, StringInStr($result, ".") - Random(5, 50), Random(50, 100))
$mulresult = _MultiX($num, $NewNum2)
$e = StringInStr($mulresult, ".") - 2
MsgBox(0, "超长精度乘法运算", $num & ' * ' & $NewNum2 & ' = ' & @CRLF & $num * $NewNum2 & @CRLF & _
                "超长精度结果：" & $mulresult & @CRLF & "数据长度：" & StringLen($mulresult) & "   e = +0" & $e)

$newNum1 = StringMid($mulresult, StringInStr($mulresult, ".") - Random(5, 10), Random(50, 100))
$NewNum2 = StringMid($result, StringInStr($result, ".") - Random(5, 10), Random(50, 100))
$subTraresult = _Subtra($newNum1, $NewNum2)
$e = StringInStr($subTraresult, ".") - 2
MsgBox(0, "超长精度减法运算", $newNum1 & '   -   ' & $NewNum2 & '   =   ' & @CRLF & $newNum1 - $NewNum2 & @CRLF & _
                "超长精度结果：" & $subTraresult & @CRLF & "数据长度：" & StringLen($subTraresult) & "   e = +0" & $e)

$newNum1 = StringMid($mulresult, StringInStr($mulresult, ".") - Random(5, 10), Random(50, 100))
$NewNum2 = StringMid($result, StringInStr($result, ".") - Random(5, 10), Random(50, 100))
$Plusresult = _PlusX($newNum1, $NewNum2)
$e = StringInStr($Plusresult, ".") - 2
MsgBox(0, "超长精度加法运算", $newNum1 & '   +   ' & $NewNum2 & '   =   ' & @CRLF & $newNum1 + $NewNum2 & @CRLF & _
                "超长精度结果：" & $Plusresult & @CRLF & "数据长度：" & StringLen($Plusresult) & "   e = +0" & $e)
;==================Example2.au3 end

Func _MultiX($num1, $num2)
        Local $result[10000], $point
        $pointSpace1 = StringInStr($num1, ".")
        $pointSpace2 = StringInStr($num2, ".")
        If $pointSpace1 Then $point += StringLen($num1) - $pointSpace1
        If $pointSpace2 Then $point += StringLen($num2) - $pointSpace2
        $num1 = StringReplace($num1, ".", "")
        $num2 = StringReplace($num2, ".", "")
        $aNum = StringSplit($num1, "")
        _ArrayReverse($aNum, 1, UBound($aNum) - 1)
        _ArrayDelete($aNum, 0)
        If $result[0] == "" Then
                $bNum = StringSplit($num2, "")
                _ArrayReverse($bNum, 1, UBound($bNum) - 1)
                _ArrayDelete($bNum, 0)
        Else
                ReDim $bNum[1]
                For $k = 0 To UBound($result) - 1
                        If $result[$k] == "" Then ExitLoop
                        _ArrayAdd($bNum, $result[$k])
                        $result[$k] = ""
                Next
                _ArrayDelete($bNum, 0)
        EndIf
        For $i = 0 To UBound($aNum) - 1
                For $j = 0 To UBound($bNum) - 1
                        $cur = $i + $j
                        $result[$cur] += $aNum[$i] * $bNum[$j]
                        If $result[$cur] >= 10 Then
                                $temp = Mod($result[$cur], 10)
                                $result[$cur + 1] += Int($result[$cur] / 10)
                                $result[$cur] = $temp
                        EndIf
                Next
        Next
        _ArrayReverse($result, 0, UBound($result) - 1)
        $sResult = StringReplace(_ArrayToString($result), '|', "")
        $temp = StringRight($sResult, $point)
        If $temp Then $sResult = StringTrimRight($sResult, $point) & '.' & $temp
        Return $sResult
EndFunc   ;==>_MultiX

Func _ExpX($num, $e = 2)
        Local $sResult
        $sResult = $num
        If Not $e Then $sResult = 0
        While $e >= 2
                If $sResult Then
                        $sResult = _MultiX($num, $sResult)
                EndIf
                $e -= 1
        WEnd
        Return $sResult
EndFunc   ;==>_ExpX

Func __plusPoint($num1, $num2)
        Local $result[10000], $out = 0
        $temp = ""
        If StringInStr($num1, ".") Then $temp = StringRegExpReplace($num1, ".*\.(\d+)", '$1')
        $point1 = $temp
        $temp = ""
        If StringInStr($num2, ".") Then $temp = StringRegExpReplace($num2, ".*\.(\d+)", '$1')
        $point2 = $temp
        If Not $point1 Or Not $point2 Then Return $point1 + $point2
        $aNum = StringSplit($point1, "")
        $bNum = StringSplit($point2, "")
        _ArrayDelete($aNum, 0)
        _ArrayDelete($bNum, 0)
        $aSize = UBound($aNum) - 1
        $bSize = UBound($bNum) - 1
        $maxSize = $aSize
        If $bSize > $aSize Then $maxSize = $bSize
        $i = 0
        While 1
                $temp1 = ""
                $temp2 = ""
                If $i <= $aSize Then $temp1 = $aNum[$i]
                If $i <= $bSize Then $temp2 = $bNum[$i]
                $temp = $temp1 + $temp2
                If $temp >= 10 Then
                        $result[$i] = $temp - 10
                        If $i == 0 Then
                                $out = 1
                        Else
                                $result[$i - 1] += 1
                                $k = $i - 1
                                While $result[$k] >= 10
                                        $result[$k] = $result[$k] - 10
                                        $result[$k - 1] += 1
                                        $k -= 1
                                        If $k == 0 Then $out += 1
                                WEnd
                        EndIf
                Else
                        $result[$i] += $temp
                        $k = $i
                        While $result[$k] >= 10
                                $result[$k] = $result[$k] - 10
                                $result[$k - 1] += 1
                                $k -= 1
                                If $k == 0 Then $out += 1
                        WEnd
                EndIf
                If $i == $maxSize Then ExitLoop
                $i += 1
        WEnd
        $sResult = $out & '.' & StringReplace(_ArrayToString($result), '|', "")
        Return $sResult
EndFunc   ;==>__plusPoint

Func _PlusX($num1, $num2)
        $pResult = __plusPoint($num1, $num2)
        $pInt = StringLeft($pResult, 1)
        $pResult = StringTrimLeft($pResult, 1)
        Local $result[10000]
        $result[0] = $pInt
        $Integer1 = StringRegExpReplace($num1, '(\d+)\..*', '$1')
        $Integer2 = StringRegExpReplace($num2, '(\d+)\..*', '$1')
        $aNum = StringSplit($Integer1, "")
        $bNum = StringSplit($Integer2, "")
        _ArrayReverse($aNum, 1, UBound($aNum) - 1)
        _ArrayDelete($aNum, 0)
        _ArrayReverse($bNum, 1, UBound($bNum) - 1)
        _ArrayDelete($bNum, 0)
        $aSize = UBound($aNum) - 1
        $bSize = UBound($bNum) - 1
        $maxSize = $aSize
        If $bSize > $aSize Then $maxSize = $bSize
        $i = 0
        While 1
                $temp1 = ""
                $temp2 = ""
                If $i <= $aSize Then $temp1 = $aNum[$i]
                If $i <= $bSize Then $temp2 = $bNum[$i]
                $temp = $temp1 + $temp2
                If $temp1 + $temp2 >= 10 Then
                        $result[$i] += $temp - 10
                        $result[$i + 1] += 1
                        $k = $i + 1
                        While $result[$k] >= 10
                                $result[$k] = $result[$k] - 10
                                $result[$k + 1] += 1
                                $k += 1
                        WEnd
                Else
                        $result[$i] += $temp
                        $k = $i
                        While $result[$k] >= 10
                                $result[$k] = $result[$k] - 10
                                $result[$k + 1] += 1
                                $k += 1
                        WEnd
                EndIf
                If $i == $maxSize Then ExitLoop
                $i += 1
        WEnd
        _ArrayReverse($result, 0, UBound($result) - 1)
        $integerResult = StringReplace(_ArrayToString($result), '|', "")
        Return $integerResult & $pResult
EndFunc   ;==>_PlusX

Func _Subtra($num1, $num2)
        Local $result[10000], $Symbol = "", $pInt = 0, $pResult = ""
        If Number($num1) < Number($num2) Then
                $temp = $num1
                $num1 = $num2
                $num2 = $temp
                $Symbol = "-"
        EndIf
        $subResult = __SubtraPoint($num1, $num2)
        If $subResult <> "" Then
                $pInt = StringRegExpReplace($subResult, '(.*)\..*', '$1')
                $pResult = StringRegExpReplace($subResult, '.*\.(.*)', '$1')
        EndIf
        Local $result[10000]
        $Integer1 = StringRegExpReplace($num1, '(\d+)\..*', '$1')
        $Integer2 = StringRegExpReplace($num2, '(\d+)\..*', '$1')
        $aNum = StringSplit($Integer1, "")
        $bNum = StringSplit($Integer2, "")
        _ArrayReverse($aNum, 1, UBound($aNum) - 1)
        _ArrayDelete($aNum, 0)
        _ArrayReverse($bNum, 1, UBound($bNum) - 1)
        _ArrayDelete($bNum, 0)
        $result[0] = $pInt
        $aSize = UBound($aNum) - 1
        $bSize = UBound($bNum) - 1
        $maxSize = $aSize
        If $bSize > $aSize Then $maxSize = $bSize
        $i = 0
        While 1
                $temp1 = ""
                $temp2 = ""
                If $i <= $aSize Then $temp1 = $aNum[$i]
                If $i <= $bSize Then $temp2 = $bNum[$i]
                $temp = $temp1 - $temp2
                If $temp < 0 Then
                        $result[$i] += $temp + 10
                        $result[$i + 1] -= 1
                Else
                        $result[$i] += $temp
                        If $result[$i] < 0 Then
                                $result[$i] = $result[$i] + 10
                                $result[$i + 1] -= 1
                        EndIf
                EndIf
                If $i == $maxSize Then ExitLoop
                $i += 1
        WEnd
        _ArrayReverse($result, 0, UBound($result) - 1)
        $integerResult = StringReplace(_ArrayToString($result), '|', "")
        Return $Symbol & $integerResult & "." & $pResult

EndFunc   ;==>_Subtra

Func __SubtraPoint($num1, $num2)
        Local $result[10000], $out = 0
        $temp = ""
        If StringInStr($num1, ".") Then $temp = StringRegExpReplace($num1, ".*\.(\d+)", '$1')
        $point1 = $temp
        $temp = ""
        If StringInStr($num2, ".") Then $temp = StringRegExpReplace($num2, ".*\.(\d+)", '$1')
        $point2 = $temp
        If Not $point2 Then Return $point1
        $aNum = StringSplit($point1, "")
        $bNum = StringSplit($point2, "")
        _ArrayDelete($aNum, 0)
        _ArrayDelete($bNum, 0)
        $aSize = UBound($aNum) - 1
        $bSize = UBound($bNum) - 1
        $maxSize = $aSize
        If $bSize > $aSize Then $maxSize = $bSize
        $i = 0
        While 1
                $temp1 = ""
                $temp2 = ""
                If $i <= $aSize Then $temp1 = $aNum[$i]
                If $i <= $bSize Then $temp2 = $bNum[$i]
                $temp = $temp1 - $temp2
                If $temp < 0 Then
                        $result[$i] += $temp + 10
                        If $i == 0 Then
                                $out = -1
                        Else
                                $result[$i - 1] -= 1
                                $k = $i - 1
                                While $result[$k] < 0
                                        $result[$k] = $result[$k] + 10
                                        $result[$k - 1] -= 1
                                        $k -= 1
                                WEnd
                        EndIf
                Else
                        $result[$i] += $temp
                        If $result[$i] < 0 Then
                                $result[$i] = $result[$i] + 10
                                $result[$i - 1] -= 1
                                $k = $i - 1
                                While $result[$k] < 0
                                        $result[$k] = $result[$k] + 10
                                        $result[$k - 1] -= 1
                                        $k -= 1
                                WEnd
                        EndIf
                EndIf
                If $i == $maxSize Then ExitLoop
                $i += 1
        WEnd
        $sResult = $out & '.' & StringReplace(_ArrayToString($result), '|', "")
        Return $sResult
EndFunc   ;==>__SubtraPoint

Func _RoundX($num, $n = 0)
        $point = StringInStr($num, ".")
        If $point <= 0 Then Return $num
        $sResult = StringLeft($num, $point + $n + 1)
        $aResult = StringSplit($sResult, "")
        _ArrayDelete($aResult, 0)
        $arrayCur = UBound($aResult) - 1
        If $aResult[$arrayCur] >= 5 Then
                If $aResult[$arrayCur - 1] <> "." Then
                        $aResult[$arrayCur - 1] += 1
                        $aResult[$arrayCur] = 0
                        $arrayCur -= 1
                Else
                        $aResult[$arrayCur - 2] += 1
                        $aResult[$arrayCur] = 0
                        $arrayCur -= 2
                EndIf
        Else
                _ArrayDelete($aResult, $arrayCur)
                Return
        EndIf
        While $arrayCur

                If $aResult[$arrayCur] >= 10 Then
                        $aResult[$arrayCur] -= 10
                        If $aResult[$arrayCur - 1] == "." Then $arrayCur -= 1
                        $aResult[$arrayCur - 1] += 1
                EndIf
                $arrayCur -= 1
        WEnd
        _ArrayDelete($aResult, UBound($aResult))
        If $n == 0 Then _ArrayDelete($aResult, UBound($aResult))
        $sResult = StringReplace(_ArrayToString($aResult), '|', "")
        Return $sResult
EndFunc   ;==>_RoundX

C.L · 发表于 2010-8-10 16:24:51

本帖最后由 C.L 于 2010-8-10 17:19 编辑

没人有兴趣吗？欢迎大家进来讨论一下啊
没有代码也提供点思路吧，或者对+、-、*、/、开方、次方里那个运算有点心得的朋友提供下运算思路，或者有能力的可以对上面某个运算有独特解法的，也可以单独的写出来嘛，人多力量大啊
我只是觉得我上面的代码，运算过程有点太多复杂了，希望贴出来，能有人帮忙改善一下运算方式。

我将上面的代码说明一下，以便大家看得更清楚一点：

乘法：Func _MultiX($num1, $num2)
思路：将乘数和被乘数分别存入两个数组，然后每位相乘，将相乘结果放到$result数组中，检查是否大于10，大于10则进位，再逐位检查是否需要进位。

幂运算：Func _ExpX($num, $e = 2)
调用乘法函数按$e大小进行连乘

加法运算：Func _PlusX($num1, $num2)
有两个函数组成：Func _PlusX($num1, $num2),整数部份相加和合并，__plusPoint($num1, $num2)小数部份相加

分两步：整数部份相加和小数部份（__plusPoint($num1, $num2)）分别相加，小数部份相加要随时检查是否需要进位，相加完后检查是否有溢出到整数的进位，整数部份和小数部份相加类似，相加完后，和小数部份的返回值合并，输出数值。

加法运算困难的是，有太多的进位和检查，而且不能用到太多的AU3内部运算符，否则精度就不够了，我目前只能是按位来算，算完再合并，想找到更好的思路，更有效率的算法，所以希望大家都能讨论一下算法，我在这里都多谢了。

减法：Func _Subtra($num1, $num2) ， Func __SubtraPoint($num1, $num2)
和加法类似的算法，只是进位方式有所不同

四舍五入：Func _RoundX($num, $n = 0)
测试中发现AU3自带的 Round （）在超大数中的返回值精度也好像有些不够，所以写了这个函数

基本介绍就是这样，所以希望各位朋友，可以说下其他的或者对上面有提议的思路，非常感谢。

rolaka · 发表于 2010-8-10 19:00:30

本帖最后由 rolaka 于 2010-8-10 19:28 编辑

#include "gmp.h"

char *powmod(char *ap, char *bp, char *cp, int base = 10)
{
        mpz_t t, a, b, c;
        mpz_inits(t, a, b ,c, 0);
        mpz_set_str(a, ap, 10);
        mpz_set_str(b, bp, 10);
        mpz_set_str(c, cp, 10);
        mpz_powm(t, a, b, c);
        char *result = mpz_get_str(0, base, t);
        return result;
}

char *tohex(char *ap, int base)
{
        mpz_t a;
        mpz_init(a);
        mpz_set_str(a, ap, base);
        char *result = mpz_get_str(0, 16, a);
        return result;
}

char *todec(char *ap, int base)
{
        mpz_t a;
        mpz_init(a);
        mpz_set_str(a, ap, base);
        char *result = mpz_get_str(0, 10, a);
        return result;
}

...我用了作弊的办法编译指令gcc -share test.c libgmp.a -o test.dll -O2
gmp库自寻...

Func powerAndMod($a, $b, $mod)
        $dll = DllCall("test.dll", "str*:cdecl", "powmod", "str", "" & $a, "str", "" & $b, "str", "" & $mod);
        Return $dll[0]
EndFunc

Func toHex($a, $b)
        $dll = DllCall("test.dll", "str*:cdecl", "tohex", "str", "" & $a, "int", $b)
        Return $dll[0]
EndFunc

Func toDec($a, $b)
        $dll = DllCall("test.dll", "str*:cdecl", "todec", "str", "" & $a, "int", $b)
        Return $dll[0]
EndFunc

其余部分...几行的事情把...

强烈要求把gmp整合到au3源码里...

([upx]test.dll是upx压缩版本...)

感谢老萧的帮助...

C.L · 发表于 2010-8-11 04:57:59

回复 3# rolaka

呵呵~ 调用外部C代码，也算一种方式吧，GMP库的效果肯定比我上面的代码要高效。

		自动登录	找回密码
密码			加入

[效率算法] 【讨论】超长精度的计算问题

相关帖子

评分

本帖子中包含更多资源

评分