怎么解决大数计算的方法

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[1]
$exp = $temp[2]
$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[10000]
        $aNum = StringSplit ($num,"")
        _ArrayReverse($aNum,1,UBound($aNum)-1)
        _ArrayDelete ($aNum,0)
        While $e >=2
                If $result [0] == "" Then
                        $bNum = StringSplit ($num,"")
                        _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
                $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

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

这个网址去看下，据说提供了调用库
用这个网站的软件算的结果：
3mile 发表于 2010-8-3 23:40

这个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[UBound($aX) + UBound($aY) - 1]
    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[0]) + $j * 6 - StringLen($aX[$j])) & $aX[$j] & _BigNum_DS($BN_X - (StringLen($aX[0]) + $j * 6)) & " * " & _BigNum_DS(StringLen($aY[0]) + $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[0])) & _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[0])) & $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 [optional] - 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 [optional] - 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 [optional] - 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 - [optional] Multiplicity of root (power, exponent) (must be a positive 64-bit signed integer > 0)
;                            Default: $e = 2 (=SQRT)
;                  $p - [optional] 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

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

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

[效率算法] 怎么解决大数计算的方法

本帖子中包含更多资源

本帖子中包含更多资源

评分

评分