怎么解决大数计算的方法-『提问交流』-AUTOIT CN

rolaka 发表于 2010-8-3 22:48:38

怎么解决大数计算的方法

php python都有相应的解决办法但au3下没有计算大数字的好办法

现真心觅一高效解决办法调用dll 纯au3皆可

要求:
1. 2147483647^9999必须在2秒内计算完毕
2. 支持模运算(mod|%)

某老萧见死不救 au3调用原生gmp库失败

拜托各位了0 0

afan 发表于 2010-8-3 22:50:06

C.L 上~

3mile 发表于 2010-8-3 23:40:53

这个网址去看下，据说提供了调用库http://www.emath.ac.cn/software.htm#HugeCalc
用这个网站的软件算的结果：

C.L 发表于 2010-8-4 00:00:52

回复 2# afan

没研究过这类超大数求幂的问题，应该会有解决的办法，只是目前还没有思路

C.L 发表于 2010-8-4 03:27:16

本帖最后由 C.L 于 2010-8-4 03:34 编辑

回复 1# rolaka

做了一段超长精度的代码，不过远远不能满足你的要求,理论上不知道是否可以支持你要求达到这么大的数，不过效率肯定达不到，我测试了2147483647^99 ，数据位是 924位，用时12秒，幂越大，运行时间就越长
如果幂为9999，估计数据位可能达到10万位，10万位的数字就是将这个数位放到一个数组中，都不知道要多少时间，而计算出来要求用两秒，不知道用何种方式来实现，实在是无能为力

虽然不能满足楼主的要求，但也上两张测试图，并将代码放出，起个抛砖引玉的作用吧
图1：幂为20，测试较短数据的准确性：

图2：幂为99，测试超长数据用时：

代码：#include <array.au3>
Dim $input = InputBox("","","2147483647^99")

$timer = TimerInit ()
$temp = StringSplit ($input,'^')
$num = $temp
$exp = $temp
$array = _Exp($num,$exp)
$sResult = StringReplace (_ArrayToString ($array),'|',"")
MsgBox (0,TimerDiff($timer),$num&'^'&$exp&'='&$num^$exp&@CRLF& _
"超长精度结果："&$sResult&@CRLF&"数据长度："&StringLen($sResult))

Func _Exp($num,$e = 2)
Local $result
$aNum = StringSplit ($num,"")
_ArrayReverse($aNum,1,UBound($aNum)-1)
_ArrayDelete ($aNum,0)
While $e >=2
If $result == "" Then
$bNum = StringSplit ($num,"")
_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
$e-=1
WEnd
_ArrayReverse($result,0,UBound($result)-1)
Return $result
EndFunc

rolaka 发表于 2010-8-4 10:13:53

回复rolaka

做了一段超长精度的代码，不过远远不能满足你的要求,理论上不知道是否可以支持你要求达到 ...
C.L 发表于 2010-8-4 03:27 http://www.autoitx.com/images/common/back.gif

纯au3只能这样了么。。。。埃

这个网址去看下，据说提供了调用库
用这个网站的软件算的结果：
3mile 发表于 2010-8-3 23:40 http://www.autoitx.com/images/common/back.gif

这个dll不考虑。。。未注册的话有随机延迟还有值的随机干

3mile 发表于 2010-8-4 12:02:35

在官网找了个大数运算的函数。应该是用了汇编指令mul。
初步测试了下执行效率还不错。计算2147483647^99结果不到1秒。
楼主试试。函数在此：#include-once

Global Const $BigNum_Debug = False

; #INDEX# =======================================================================================================================
; Title .........: BigNum
; AutoIt Version : 3.2.12.1
; Language ......: English
; Description ...: Perform calculations with big numbers
; ===============================================================================================================================

; #CURRENT# =====================================================================================================================
;_BigNum_Add
;_BigNum_Sub
;_BigNum_Mul
;_BigNum_Div
;_BigNum_Pow
;_BigNum_SQRT
;_BigNum_n_Root
;_BigNum_Mod
;_BigNum_Round
;_BigNum_Compare
;_BigNum_Swap
; ===============================================================================================================================

; #INTERNAL_USE_ONLY#============================================================================================================
;_BigNum_CheckNegative
;_BigNum_DivAdd
;_BigNum_DivComp
;_BigNum_DivSub
;_BigNum_Div_DivisorGreater14
;_BigNum_Div_DivisorMaxLen14
;_BigNum_InsertDecimalSeparator
;_BigNum_StringIsDecimal
;_BigNum_IsValid
; ===============================================================================================================================

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Add
; Description ...: Addition $sX + $sY
; Syntax.........: _BigNum_Add($sX, $sY)
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $sY - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
; Return values .: Success - Result $sX + $sY
;                Failure - 0, sets @error to 1 if $sX/$sY not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Add($sX, $sY)
If _BigNum_IsValid($sX, $sY) Then Return SetError(1, 0, 0)
Local $iNeg = _BigNum_CheckNegative($sX, $sY), $sNeg = ""
If $iNeg = 3 Then $sNeg = "-"
If $iNeg = 1 Then Return _BigNum_Sub($sY, $sX)
If $iNeg = 2 Then Return _BigNum_Sub($sX, $sY)
If $BigNum_Debug Then Local $BN_File = FileOpen(@ScriptDir & "\BigNum_Debug.txt", 2)
Local $iDec = _BigNum_StringIsDecimal($sX, $sY)
Local $iTmp = StringLen($sX), $iLen = StringLen($sY), $iCar = 0, $sRet = ""
If $BigNum_Debug Then FileWrite($BN_File, " " & _BigNum_DS($iLen - $iTmp, "0") & $sX & " + " & @CRLF & " " & _BigNum_DS($iTmp - $iLen, "0") & $sY & @CRLF)
If $iLen < $iTmp Then $iLen = $iTmp
If $BigNum_Debug Then FileWrite($BN_File, " " & _BigNum_DS($iLen, "-") & @CRLF)
For $i = 1 To $iLen Step 18
   $iTmp = Int(StringRight($sX, 18)) + Int(StringRight($sY, 18)) + $iCar
   $sX = StringTrimRight($sX, 18)
   $sY = StringTrimRight($sY, 18)
   If ($iTmp > 999999999999999999) Then
         $iTmp = StringRight($iTmp, 18)
         $sRet = $iTmp & $sRet
         If $BigNum_Debug Then FileWrite($BN_File, _BigNum_DS($iLen - $i - StringLen($iTmp) + 2) & $iTmp & _BigNum_DS($i) & "+" & $iCar & @CRLF)
         $iCar = 1
   Else
         If $BigNum_Debug Then FileWrite($BN_File, _BigNum_DS($iLen - $i - StringLen($iTmp) + 2) & $iTmp & _BigNum_DS($i) & "+" & $iCar & @CRLF)
         $iTmp = StringRight("000000000000000000" & $iTmp, 18)
         $sRet = $iTmp & $sRet
         $iCar = 0
   EndIf
Next
$sRet = StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
If $iDec > 0 Then $sRet = _BigNum_InsertDecimalSeparator($sRet, $iDec, $iDec)
If $sRet = "0"Then $sNeg = ""
If $BigNum_Debug Then
   FileWrite($BN_File, " " & _BigNum_DS($iLen, "-") & @CRLF)
   FileWrite($BN_File, _BigNum_DS($iLen - StringLen($sRet) + 1) & $sRet)
   FileClose($BN_File)
EndIf
Return $sNeg & $sRet
EndFunc ;==>_BigNum_Add

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Sub
; Description ...: Subtraction $sX - $sY
; Syntax.........: _BigNum_Sub($sX, $sY)
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $sY - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
; Return values .: Success - Result $sX - $sY
;                Failure - 0, sets @error to 1 if $sX/$sY not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Sub($sX, $sY)
If _BigNum_IsValid($sX, $sY) Then Return SetError(1, 0, 0)
Local $iNeg = _BigNum_CheckNegative($sX, $sY), $bNeg = False
If $iNeg = 3 Then Return _BigNum_Add("-" & $sX, $sY)
If $iNeg = 1 Then Return "-" & _BigNum_Add($sX, $sY)
If $iNeg = 2 Then Return _BigNum_Add($sX, $sY)
If $BigNum_Debug Then Local $BN_File = FileOpen(@ScriptDir & "\BigNum_Debug.txt", 2)
Local $iDec = _BigNum_StringIsDecimal($sX, $sY)
If _BigNum_Compare($sX, $sY) = -1 Then $bNeg = _BigNum_Swap($sX, $sY)
Local $iTmp = StringLen($sX), $iLen = StringLen($sY), $iCar = 0, $sRet = ""
If $BigNum_Debug Then FileWrite($BN_File, " " & _BigNum_DS($iLen - $iTmp, "0") & $sX & " - " & @CRLF & " " & _BigNum_DS($iTmp - $iLen, "0") & $sY & @CRLF)
If $iLen < $iTmp Then $iLen = $iTmp
If $BigNum_Debug Then FileWrite($BN_File, " " & _BigNum_DS($iLen, "-") & @CRLF)
For $i = 1 To $iLen Step 18
   $iTmp = Int(StringRight($sX, 18)) - Int(StringRight($sY, 18)) - $iCar
   $sX = StringTrimRight($sX, 18)
   $sY = StringTrimRight($sY, 18)
   If $iTmp < 0 Then
         $iTmp = 1000000000000000000 + $iTmp
         If $BigNum_Debug Then FileWrite($BN_File, _BigNum_DS($iLen - $i - StringLen($iTmp) + 2) & $iTmp & _BigNum_DS($i) & "-" & $iCar & @CRLF)
         $iCar = 1
   Else
         If $BigNum_Debug Then FileWrite($BN_File, _BigNum_DS($iLen - $i - StringLen($iTmp) + 2) & $iTmp & _BigNum_DS($i) & "-" & $iCar & @CRLF)
         $iCar = 0
   EndIf
   $sRet = StringRight("0000000000000000000" & $iTmp, 18) & $sRet
Next
$sRet = StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
If $iDec > 0 Then $sRet = _BigNum_InsertDecimalSeparator($sRet, $iDec, $iDec)
If $BigNum_Debug Then
   FileWrite($BN_File, " " & _BigNum_DS($iLen, "-") & @CRLF)
   FileWrite($BN_File, _BigNum_DS($iLen - StringLen($sRet) + 1) & $sRet)
   FileClose($BN_File)
EndIf
If $bNeg = True And $sRet <> "0"Then
   Return "-" & $sRet
Else
   Return $sRet
EndIf
EndFunc ;==>_BigNum_Sub

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Mul
; Description ...: Multiplication $sX * $sY
; Syntax.........: _BigNum_Mul($sX, $sY)
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $sY - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
; Return values .: Success - Result $sX * $sY
;                Failure - 0, sets @error to 1 if $sX/$sY not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Mul($sX, $sY)
If _BigNum_IsValid($sX, $sY) Then Return SetError(1, 0, 0)
Local $iNeg = _BigNum_CheckNegative($sX, $sY), $sNeg = ""
Local $iDec = _BigNum_StringIsDecimal($sX, $sY)
If $BigNum_Debug Then
   Local $BN_File = FileOpen(@ScriptDir & "\BigNum_Debug.txt", 2), $BN_X = StringLen($sX)
   FileWrite($BN_File, " " & $sX & " * " & $sY & " = " & @CRLF)
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + StringLen($sY) + 3, "-") & @CRLF)
EndIf
Local $aX = StringRegExp($sX, '\A.{' & 6 - (Ceiling(StringLen($sX) / 6) * 6 - StringLen($sX)) & '}|.{6}+', 3)
Local $aY = StringRegExp($sY, '\A.{' & 6 - (Ceiling(StringLen($sY) / 6) * 6 - StringLen($sY)) & '}|.{6}+', 3)
Local $aRet
For $j = 0 To UBound($aX) - 1
   For $i = 0 To UBound($aY) - 1
         If $BigNum_Debug Then
            FileWrite($BN_File, " " & _BigNum_DS(StringLen($aX) + $j * 6 - StringLen($aX[$j])) & $aX[$j] & _BigNum_DS($BN_X - (StringLen($aX) + $j * 6)) & " * " & _BigNum_DS(StringLen($aY) + $i * 6 - StringLen($aY[$i])) & $aY[$i])
            FileWrite($BN_File, " " & _BigNum_DS(((UBound($aY) - 1 - $i) * 6) + ($i * 15 + $j * 15)) & $aX[$j] * $aY[$i] & @CRLF)
         EndIf
         $aRet[$j + $i] += $aX[$j] * $aY[$i]
   Next
Next
If $BigNum_Debug Then
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + StringLen($sY) + 3) & _BigNum_DS($i * 15 + $j * 15, "-") & @CRLF)
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + StringLen($sY) + 6))
   For $i = 0 To UBound($aRet) - 1
         FileWrite($BN_File, $aRet[$i] & _BigNum_DS(15 - StringLen($aRet[$i])))
   Next
   FileWrite($BN_File, @CRLF & @CRLF)
   For $i = 0 To UBound($aRet) - 1
         FileWrite($BN_File, _BigNum_DS($BN_X + StringLen($sY)) & _BigNum_DS($i * 6 + 15 - StringLen($aRet[$i])) & $aRet[$i] & @CRLF)
   Next
   FileWrite($BN_File, _BigNum_DS($BN_X + StringLen($sY)) & _BigNum_DS(15 - StringLen($aRet)) & _BigNum_DS($i * 6, "-") & @CRLF)
EndIf
Local $sRet = "", $iCar = 0, $iTmp
For $i = UBound($aRet) - 1 To 0 Step - 1
   $aRet[$i] += $iCar
   $iCar = Floor($aRet[$i] / 1000000)
   $iTmp = Mod($aRet[$i], 1000000)
   If $iTmp <= 1000000 Then $iTmp = StringRight("000000" & $iTmp, 6)
   $sRet = $iTmp & $sRet
Next
If $iCar > 0 Then $sRet = $iCar & $sRet
$sRet = StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
If ($iNeg = 1 Or $iNeg = 2) And $sRet <> "0"Then $sNeg = "-"
If $iDec > 0 Then $sRet = _BigNum_InsertDecimalSeparator($sRet, $iDec * 2, $iDec * 2)
If $BigNum_Debug Then
   FileWrite($BN_File, _BigNum_DS($BN_X + StringLen($sY)) & _BigNum_DS(15 - StringLen($aRet)) & $sRet)
   FileClose($BN_File)
EndIf
Return $sNeg & $sRet
EndFunc ;==>_BigNum_Mul

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Div
; Description ...: Division $sX / $sY
; Syntax.........: _BigNum_Div($sX, $sY, [$iD = 0])
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $sY - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $iD - Number of Decimalplaces
; Return values .: Success - Result $sX / $sY
;                Failure - 0, sets @error to 1 if $sX/$sY not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Div($sX, $sY, $iD = 0)
If _BigNum_IsValid($sX, $sY) Then Return SetError(1, 0, 0)
Local $iNeg = _BigNum_CheckNegative($sX, $sY), $sNeg = ""
Local $iDec = _BigNum_StringIsDecimal($sX, $sY), $sMod
If $sX = 0 Or $sY = 0 Then Return "0"
If $sY = "1"Then Return $sNeg & $sX
While StringLeft($sX, 1) = "0"
   $sX = StringTrimLeft($sX, 1)
   $iDec += 1
WEnd
While StringLeft($sY, 1) = "0"
   $sY = StringTrimLeft($sY, 1)
   $iDec += 1
WEnd
Local $sRet = "", $iLnX = StringLen($sX), $iLnY = StringLen($sY), $iTmp, $iCnt, $sTmp, $iDe1 = 0
If $iD > 0 Then $iDe1 += $iD
If $iNeg = 1 Or $iNeg = 2 Then $sNeg = "-"
$iTmp = _BigNum_Compare($sX, $sY)
If $iTmp = -1 Then
   For $iCnt = $iLnX To $iLnY
         $sX &= 0
         $iDe1 += 1
   Next
EndIf
If $iTmp = 0 Then Return $sNeg & "1"
If $iD = -1 Then $iD = $iDec * 2
For $iCnt = 1 To $iD
   $sX &= "0"
Next
If $iLnY > 14 Then
   $sRet = _BigNum_Div_DivisorGreater14($sX, $sY, $sMod)
Else
   $sRet = _BigNum_Div_DivisorMaxLen14($sX, $sY, $sMod)
EndIf
If $iDe1 > 0 Then $sRet = _BigNum_InsertDecimalSeparator($sRet, $iDe1, $iD)
If $sRet = "0"Then
   Return "0"
Else
   Return $sNeg & $sRet
EndIf
EndFunc ;==>_BigNum_Div

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Pow
; Description ...: Exponentiation $n^$e
; Syntax.........: _BigNum_Pow($n [, $e = 2])
; Parameters ....: $n - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $e - Exponent (must be a positive 64-bit signed integer)
;                               Default: $e = 2 means result = $n2
; Return values .: Success - Result $n^$e
;                Failure - -1, sets @error to 1 if $n not valid StringNumber
;                         -1, sets @error to 2 if $e is not a positive Integer
; Author ........: jennicoattminusonlinedotde
; Date ..........: 9.12.09
; Remarks .......: Fractional exponents not allowed - use BigNum_n_root instead.
;                _BigNum_Pow() offers a drastically better efficiency than looping _BigNum_Mul()
; Reference .....: http://en.wikipedia.org/wiki/Exponentiation_by_squaring
; ;===============================================================================================
Func _BigNum_Pow($n, $e = 2)
$e = Number($e)
If IsInt($e) = 0 Or $e < 0 Then Return SetError(2, 0, -1)
;If $e < -2147483648 Or $e > 2147483647 Then Return SetError(-2, 0, -1)
If _BigNum_IsValid($n, $n) Then Return SetError(1, 0, -1)

Local $res = 1

While $e
   ;If BitAND($e, 1) Then; bitoperation is not faster !
   If Mod($e, 2) Then
         $res = _BigNum_Mul($res, $n)
         $e -= 1
   EndIf
   $n = _BigNum_Mul($n, $n)
   ;$e = BitShift($e, 1) ; bitoperation is not faster !
   $e /= 2
WEnd

Return $res
EndFunc ;==>_BigNum_Pow

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_SQRT
; Description ...: Square Root (BigNum)
; Syntax.........: _BigNum_SQRT($n [, $p = -1])
; Parameters ....: $n - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $p - Precision (Number of Decimalplaces) (must be positive Integer)
;                         Default: $p = -1 means automatic precision (stringlen of integer part of $n)
; Return values .: Success - Result SQRT($n)
;                         @extended = Precicion of result (if $p set to automatic precision)
;                         @error = Number of Iterations
;                Failure - -1, sets @error to -1 if $n not valid StringNumber
;                         -1, sets @error to -2 if $p is out of valid range
;                         -1, sets @error to -3 if time-out (>100 iterations)
; Author ........: jennicoattminusonlinedotde
; Date ..........: 8.12.09
; Remarks .......: use Precision param when u want to obtain the square root of a small number with the desired decimal places.
; References ....: http://www.merriampark.com/bigsqrt.htm
;                "Newton's Method" - before: Heron of Alexandria
; ;===============================================================================================
Func _BigNum_SQRT($n, $p = -1)
If _BigNum_IsValid($n, $n) Then Return SetError(-1, 0, -1)
$p = Number($p)
If IsInt($p) = 0 Or $p < -1 Then Return SetError(-2, 0, -1)
Local $l = StringInStr($n, ".") - 1
If $l = -1 Then $l = StringLen($n)
If $p < 0 Then $p = $l
Local $g = 1, $last

For $i = 3 To $l Step 2
   $g = _BigNum_Mul($g, 10)
Next

For $i = 1 To 100
   $last = $g
   $g = _BigNum_Div(_BigNum_Add(_BigNum_Div($n, $g, $p), $g), 2, $p)
   If $last = $g Then Return SetError($i, $p, $g)
Next
Return SetError(-3, 0, -1)
EndFunc ;==>_BigNum_SQRT

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_n_Root
; Description ...: $e-th Root of $n
; Syntax.........: _n_Root($n [, $e=2])
; Parameters ....: $n - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $e - Multiplicity of root (power, exponent) (must be a positive 64-bit signed integer > 0)
;                         Default: $e = 2 (=SQRT)
;                $p - Precision (Number of desired Decimalplaces) (must be positive Integer)
;                         Default: $p = -1 means automatic precision (stringlen of integer part of $n)
; Return values .: Success - Result $e-root($n)
;                         @extended = Number of Iterations
;                Failure - -1 and sets @error to 1 if $n not valid StringNumber
;                         -1 and sets @error to 2 if $e out of valid range
;                         -1 and sets @error to 3 if $p out of valid range
; Author ........: jennicoattminusonlinedotde
; Date ..........: 9.12.09
; References ....: derived from "Newton's Method"
; ;===============================================================================================
Func _BigNum_n_Root($n, $e = 2, $p = -1)
If _BigNum_IsValid($n, $n) Then Return SetError(1, 0, -1)
$e = Number($e)
If IsInt($e) = 0 Or $e < 1 Then Return SetError(2, 0, -1)
$p = Number($p)
If IsInt($p) = 0 Or $p < -1 Then Return SetError(3, 0, -1)

Local $l = StringInStr($n, ".") - 1
If $l = -1 Then $l = StringLen($n)
If $p < 0 Then $p = $l
Local $g = 1, $last, $i = 0

For $i = 3 To $l Step 2
   $g = _BigNum_Mul($g, 10)
Next

While 1
   $i += 1
   $last = $g
   $g = _BigNum_Div(_BigNum_Add(_BigNum_Div($n, _BigNum_Pow($g, $e - 1), $p), _BigNum_Mul($g, $e - 1)), $e, $p)
   If $last = $g Then Return SetExtended($i, $g)
WEnd
EndFunc ;==>_BigNum_n_Root

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Mod
; Description ...: Modulo Mod($sX, $sY)
; Syntax.........: _BigNum_Mod($sX, $sY)
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $sY - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
; Return values .: Success - Result Mod($sX, $sY)
;                Failure - 0, sets @error to 1 if $sX/$sY not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Mod($sX, $sY)
If _BigNum_IsValid($sX, $sY) Then Return SetError(1, 0, 0)
If $sY = 0 Or $sY = 1 Then Return "0"
Local $sRes = $sX
Local $iNeg = _BigNum_CheckNegative($sX, $sY)
Local $iDec = _BigNum_StringIsDecimal($sX, $sY)
If _BigNum_Compare($sX, $sY) < 0 Then Return $sRes
Local $sRet = "", $iLnX = StringLen($sX), $iLnY = StringLen($sY)
If $iLnY > 14 Then
   _BigNum_Div_DivisorGreater14($sX, $sY, $sRet)
Else
   _BigNum_Div_DivisorMaxLen14($sX, $sY, $sRet)
EndIf
$sRet = _BigNum_InsertDecimalSeparator($sRet, $iDec, StringLen($sRet))
If ($iNeg = 3 Or $iNeg = 1) And $sRet <> "0"Then $sRet = "-" & $sRet
Return $sRet
EndFunc ;==>_BigNum_Mod

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Round
; Description ...: Round $sX to $iD Decimalplaces
; Syntax.........: _BigNum_Round($sX, $iD)
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $iD - Number of Decimalplaces
; Return values .: Success - Result Round($sX, $iD)
;                Failure - 0, sets @error to 1 if $sX not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Round($sX, $iD)
If _BigNum_IsValid($sX, $sX) Then Return SetError(1, 0, 0)
Local $sTmp = 0, $sRet, $sRes = $sX
Local $iNeg = _BigNum_CheckNegative($sX, $sTmp)
Local $iDec = _BigNum_StringIsDecimal($sX, $sTmp)
If $iD > $iDec Or $iDec = 0 Then Return $sRes
$sTmp = StringLeft(StringRight($sX, $iDec - $iD), 1)
$sRet = StringTrimRight($sRes, $iDec - $iD)
If $sTmp >= 5 And $iD > 0 Then
   If $iNeg = 1 Then
         $sRet = _BigNum_Add($sRet, "-0." & StringFormat("%0" & String($iD) & "u", "1"))
   Else
         $sRet = _BigNum_Add($sRet, "0." & StringFormat("%0" & String($iD) & "u", "1"))
   EndIf
ElseIf $sTmp >= 5 And $iD = 0 Then
   If $iNeg = 1 Then
         $sRet = _BigNum_Add($sRet, "-1")
   Else
         $sRet = _BigNum_Add($sRet, "1")
   EndIf
Else
   If StringRight($sRet, 1) = "."Then $sRet = StringTrimRight($sRet, 1)
EndIf
Return $sRet
EndFunc ;==>_BigNum_Round

; #FUNCTION# ;====================================================================================
;
; Name...........: _BigNum_Compare
; Description ...: Compares $sX $sY
; Syntax.........: _BigNum_Compare($sX, $sY)
; Parameters ....: $sX - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
;                $sY - StringNumber: Minus"-" Digits"0"..."9" Separator"." ("-1234567890.12345")
; Return values .: Success - Return:
;                |0- $sX and $sY are equal
;                |1- $sX is greater than $sY
;                |-1 - $sX is less than $sY
;                Failure - sets @error to 1 if $sX/$sY not valid StringNumber
; Author ........: Eukalyptus www.autoit.de
;
; ;===============================================================================================
Func _BigNum_Compare($sX, $sY)
Local $iNeg = _BigNum_CheckNegative($sX, $sY)
If $iNeg = 1 Then Return -1
If $iNeg = 2 Then Return 1
Local $iLnX = StringLen($sX), $iLnY = StringLen($sY)
If $iNeg = 3 Then
   If $iLnX > $iLnY Then
         Return -1
   ElseIf $iLnX < $iLnY Then
         Return 1
   Else
         If $sX > $sY Then
            Return -1
         ElseIf $sX < $sY Then
            Return 1
         Else
            Return 0
         EndIf
   EndIf
Else
   If $iLnX > $iLnY Then
         Return 1
   ElseIf $iLnX < $iLnY Then
         Return -1
   Else
         If $sX > $sY Then
            Return 1
         ElseIf $sX < $sY Then
            Return -1
         Else
            Return 0
         EndIf
   EndIf
EndIf
EndFunc ;==>_BigNum_Compare

Func _BigNum_Swap(ByRef $sX, ByRef $sY)
Local $sSwap = $sX
$sX = $sY
$sY = $sSwap
Return True
EndFunc ;==>_BigNum_Swap

; #INTERNAL_USE_ONLY#============================================================================================================

#region Internal Functions
Func _BigNum_Div_DivisorGreater14($sX, $sY, ByRef $sM)
$sM = "0"
If $sY = "1"Then Return $sX
If $sX = "0"Or $sY = "0"Or $sX = "" Or $sY = "" Then Return "0"
If $BigNum_Debug Then
   Local $BN_File = FileOpen(@ScriptDir & "\BigNum_Debug.txt", 2), $BN_X = StringLen($sX)
   FileWrite($BN_File, " " & $sX & " / " & $sY & " = " & @CRLF)
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + StringLen($sY) + 3, "-") & @CRLF)
EndIf
Local $iLnY = StringLen($sY), $bRed = False
Local $sRet = "", $sRem = StringLeft($sX, $iLnY), $sTmp = "", $sTm2 = "", $iCnt, $iLen = 1
$sX = StringTrimLeft($sX, $iLnY)
Do
   If _BigNum_DivComp($sRem, $sY) = -1 Then
         $sTmp = StringLeft($sX, 1)
         $sRem &= $sTmp
         $sX = StringTrimLeft($sX, 1)
         If StringLen($sTmp) > 0 Then $iLen += 1
   EndIf
   $sTmp = $sY
   $sTm2 = "0"
   If _BigNum_DivComp($sRem, $sY) >= 0 Then
         For $iCnt = 1 To 9
            $sTm2 = $sTmp
            $sTmp = _BigNum_DivAdd($sTmp, $sY)
            If _BigNum_DivComp($sRem, $sTmp) < 0 Then ExitLoop
         Next
   Else
         $iCnt = 0
   EndIf
   If $BigNum_Debug Then FileWrite($BN_File, _BigNum_DS($BN_X - StringLen($sX) - StringLen($sRem) + 1) & $sRem & _BigNum_DS($BN_X + 10 - $iLen - $iLnY) & StringFormat("%0" & String($iLen) & "u", $iCnt) & @CRLF)
   If StringLen($sX) = 0 Then $bRed = True
   $sM = $sRem
   $sRem = _BigNum_DivSub($sRem, $sTm2)
   If $iCnt > 0 Then $sM = $sRem
   $sRet &= StringFormat("%0" & String($iLen) & "u", $iCnt)
   $iTrm = $iLnY - StringLen($sRem)
   $sTmp = StringLeft($sX, $iTrm)
   $sX = StringTrimLeft($sX, $iTrm)
   $iLen = StringLen($sTmp)
   $sRem &= $sTmp
Until $bRed
$sM = StringRegExpReplace($sM, "^0+([^0]|0$)", "\1", 1)
If $BigNum_Debug Then
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + 9 + StringRegExp($sRet, "^0+([^0]|0$)", "\1", 1)) & _BigNum_DS(StringLen(StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)), "-") & @CRLF)
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + 9 + StringRegExp($sRet, "^0+([^0]|0$)", "\1", 1)) & StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1))
   FileClose($BN_File)
EndIf
Return StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>_BigNum_Div_DivisorGreater14

Func _BigNum_Div_DivisorMaxLen14($sX, $sY, ByRef $sM)
$sM = "0"
If $sY = "1"Then Return $sX
If $sX = "0"Or $sY = "0"Or $sX = "" Or $sY = "" Then Return "0"
If $BigNum_Debug Then
   Local $BN_File = FileOpen(@ScriptDir & "\BigNum_Debug.txt", 2), $BN_X = StringLen($sX)
   FileWrite($BN_File, " " & $sX & " / " & $sY & " = " & @CRLF)
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + StringLen($sY) + 3, "-") & @CRLF)
EndIf
Local $sRet = "", $iRem = StringLeft($sX, 15), $iTmp = 0, $iTrm = 6, $iLen
$sX = StringTrimLeft($sX, 15)
$iTmp = Floor($iRem / $sY)
$sRet &= $iTmp
If $BigNum_Debug Then FileWrite($BN_File, " " & $iRem & _BigNum_DS(StringLen($sX) + 10) & $iTmp & @CRLF)
$iRem -= $iTmp * $sY
While StringLen($sX) > 0
   $iTrm = 15 - StringLen($iRem)
   $iTmp = StringLeft($sX, $iTrm)
   $iLen = StringLen($iTmp)
   $iRem &= $iTmp
   $sX = StringTrimLeft($sX, $iTrm)
   $iTmp = Floor($iRem / $sY)
   $iTmp = StringRight("000000000000000" & $iTmp, $iLen)
   If $BigNum_Debug Then FileWrite($BN_File, _BigNum_DS($BN_X - StringLen($sX) + 1 - StringLen($iRem)) & $iRem & _BigNum_DS(StringLen($sX) + 10 + StringLen($sRet)) & $iTmp & @CRLF)
   $sRet &= $iTmp
   $iRem -= $iTmp * $sY
WEnd
$sM = String($iRem)
If $BigNum_Debug Then
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + 10) & _BigNum_DS(StringLen(StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)), "-") & @CRLF)
   FileWrite($BN_File, " " & _BigNum_DS($BN_X + 10) & StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1))
   FileClose($BN_File)
EndIf
Return StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc ;==>_BigNum_Div_DivisorMaxLen14

Func _BigNum_DivComp($sX, $sY)
$sX = StringRegExpReplace($sX, "^0+([^0]|0$)", "\1", 1)
$sY = StringRegExpReplace($sY, "^0+([^0]|0$)", "\1", 1)
Local $iLnX = StringLen($sX), $iLnY = StringLen($sY)
If $iLnX < $iLnY Then
   Return -1
ElseIf $iLnX > $iLnY Then
   Return 1
Else
   If $sX < $sY Then
         Return -1
   ElseIf $sX > $sY Then
         Return 1
   Else
         Return 0
   EndIf
EndIf
EndFunc ;==>_BigNum_DivComp

Func _BigNum_DivAdd($sX, $sY)
Local $iTmp = StringLen($sX), $iLen = StringLen($sY), $iCar = 0, $sRet = ""
If $iLen < $iTmp Then $iLen = $iTmp
For $i = 1 To $iLen Step 18
   $iTmp = Int(StringRight($sX, 18)) + Int(StringRight($sY, 18)) + $iCar
   $sX = StringTrimRight($sX, 18)
   $sY = StringTrimRight($sY, 18)
   If ($iTmp > 999999999999999999) Then
         $sRet = StringRight($iTmp, 18) & $sRet
         $iCar = 1
   Else
         $iTmp = StringRight("000000000000000000" & $iTmp, 18)
         $sRet = $iTmp & $sRet
         $iCar = 0
   EndIf
Next
$sRet = StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
Return $sRet
EndFunc ;==>_BigNum_DivAdd

Func _BigNum_DivSub($sX, $sY)
Local $iTmp = StringLen($sX), $iLen = StringLen($sY), $iCar = 0, $sRet = ""
If $iLen < $iTmp Then $iLen = $iTmp
For $i = 1 To $iLen Step 18
   $iTmp = Int(StringRight($sX, 18)) - Int(StringRight($sY, 18)) - $iCar
   $sX = StringTrimRight($sX, 18)
   $sY = StringTrimRight($sY, 18)
   If $iTmp < 0 Then
         $iTmp = 1000000000000000000 + $iTmp
         $iCar = 1
   Else
         $iCar = 0
   EndIf
   $sRet = StringRight("0000000000000000000" & $iTmp, 18) & $sRet
Next
$sRet = StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
Return $sRet
EndFunc ;==>_BigNum_DivSub

Func _BigNum_IsValid($sX, $sY)
If StringRegExp($sX, "[^0-9.-]") <> 0 Or StringRegExp($sY, "[^0-9.-]") <> 0 Then Return True
Return False
EndFunc ;==>_BigNum_IsValid

Func _BigNum_InsertDecimalSeparator($sX, $iDec, $iD = 18)
If $iD = 0 And $iDec = 0 Then Return $sX
Local $sRet = StringRegExpReplace(StringRight(StringFormat("%0" & String($iDec) & "u", "") & $sX, $iDec), "0+$", "\1", 1)
$sX = StringTrimRight($sX, $iDec)
If $sX = "" Then $sX = "0"
$sRet = StringLeft($sRet, $iD)
If $sRet = "" Or $sRet = "0"Then Return $sX
Return $sX & "." & $sRet
EndFunc ;==>_BigNum_InsertDecimalSeparator

Func _BigNum_StringIsDecimal(ByRef $sX, ByRef $sY)
If StringLeft($sX, 1) = "."Then $sX = "0" & $sX
If StringLeft($sY, 1) = "."Then $sY = "0" & $sY
Local $iPsX = StringInStr($sX, ".", 0, 1) - 1, $iPsY = StringInStr($sY, ".", 0, 1) - 1
$sX = StringRegExpReplace($sX, "\D", "")
$sY = StringRegExpReplace($sY, "\D", "")
Local $iLnX = StringLen($sX), $iLnY = StringLen($sY)
If $iPsX <= 0 Then $iPsX = $iLnX
If $iPsY <= 0 Then $iPsY = $iLnY
If $iLnX - $iPsX > $iLnY - $iPsY Then
   For $iCnt = $iLnY - $iPsY To $iLnX - $iPsX - 1
         $sY &= "0"
   Next
   Return $iLnX - $iPsX
ElseIf $iLnX - $iPsX < $iLnY - $iPsY Then
   For $iCnt = $iLnX - $iPsX To $iLnY - $iPsY - 1
         $sX &= "0"
   Next
   Return $iLnY - $iPsY
EndIf
Return $iLnX - $iPsX
EndFunc ;==>_BigNum_StringIsDecimal

Func _BigNum_CheckNegative(ByRef $sX, ByRef $sY)
Local $bNgX = False, $bNgY = False
While StringLeft($sX, 1) = "-"
   $bNgX = Not $bNgX
   $sX = StringTrimLeft($sX, 1)
WEnd
While StringLeft($sY, 1) = "-"
   $bNgY = Not $bNgY
   $sY = StringTrimLeft($sY, 1)
WEnd
$sX = StringRegExpReplace($sX, "^0+([^0]|0$)", "\1", 1)
$sY = StringRegExpReplace($sY, "^0+([^0]|0$)", "\1", 1)
If $sX = "" Then $sX = "0"
If $sY = "" Then $sY = "0"
If $bNgX = True And $bNgY = True Then
   Return 3
ElseIf $bNgX = True And $bNgY = False Then
   Return 1
ElseIf $bNgX = False And $bNgY = True Then
   Return 2
Else
   Return 0
EndIf
EndFunc ;==>_BigNum_CheckNegative

Func _BigNum_DS($iC, $sS = " ")
Local $sRet = "", $iCnt
For $iCnt = 1 To $iC
   $sRet &= $sS
Next
Return $sRet
EndFunc ;==>_BigNum_DS
#endregion Internal Functions测试代码在此：#include "bignumber.au3"
$time=TimerInit()
$aa=_BigNum_Pow(2147483647,99)
MsgBox(0,0,TimerDiff($time))
ConsoleWrite($aa)
顺便说一下，C.L兄的数学和思维能力太强了，赞一个。

rolaka 发表于 2010-8-4 12:22:57

在官网找了个大数运算的函数。应该是用了汇编指令mul。
初步测试了下执行效率还不错。计算2147483647^99结 ...
3mile 发表于 2010-8-4 12:02 http://www.autoitx.com/images/common/back.gif

囧当初作为第一个解决办法但因为效率所以放弃

页: [1]

AUTOIT CN's Archiver

怎么解决大数计算的方法