【讨论】超长精度的计算问题
近段时间，有些坛友提出超大精度的计算问题，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
$exp = $temp
$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, $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 == "" Then
$bNum = StringSplit($num2, "")
_ArrayReverse($bNum, 1, UBound($bNum) - 1)
_ArrayDelete($bNum, 0)
Else
ReDim $bNum
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, $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
$result = $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, $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
$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 = $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, $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 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: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;
}
{:face (361):}...我用了作弊的办法 编译指令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
EndFunc
Func toHex($a, $b)
$dll = DllCall("test.dll", "str*:cdecl", "tohex", "str", "" & $a, "int", $b)
Return $dll
EndFunc
Func toDec($a, $b)
$dll = DllCall("test.dll", "str*:cdecl", "todec", "str", "" & $a, "int", $b)
Return $dll
EndFunc
其余部分...几行的事情把...
强烈要求把gmp整合到au3源码里...
(test.dll是upx压缩版本...)
感谢老萧的帮助... 回复 3# rolaka
呵呵~ 调用外部C代码，也算一种方式吧，GMP库的效果肯定比我上面的代码要高效。
页:
[1]