BigNum UDF

eukalyptus · October 30, 2008

UDF to perform calculations with big numbers

_BigNum_Parse
_BigNum_Add
_BigNum_Sub
_BigNum_Mul
_BigNum_Div
_BigNum_Pow
_BigNum_SQRT
_BigNum_n_Root
_BigNum_Mod
_BigNum_Round
_BigNum_Compare

EDIT: updated

BigNum.au3

BigNum_example.au3

#include "BigNum.au3"

$X = "10000000000000000000"
$Y = "0.000000000000000001"
MsgBox(0, "Addition", $X & "  +  " & $Y & "  =  " & _BigNum_Add($X, $Y))

$X = "-10000000000000000000"
$Y = "10000000000000000000"
MsgBox(0, "Subtraction", $X & "  -  " & $Y & "  =  " & _BigNum_Sub($X, $Y))

$X = "10000000000000000001"
$Y = "-0.0000001"
MsgBox(0, "Multiplication", $X & "  x  " & $Y & "  =  " & _BigNum_Mul($X, $Y))

$X = "10000000000000000000"
$Y = "3"
MsgBox(0, "Division, 10 Decimalplaces", $X & "  /  " & $Y & "  =  " & _BigNum_Div($X, $Y, 10))
MsgBox(0, "Division & Modulo", $X & "  /  " & $Y & "  =  " & _BigNum_Div($X, $Y) & @CRLF & "Mod: " & _BigNum_Mod($X, $Y))

Edited August 15, 2010 by eukalyptus

Jango · October 30, 2008

hi
this is the current result of the www.autoit.de-september-contest.

Can u tell me what is this contest exactly ?

eukalyptus · October 30, 2008

Can u tell me what is this contest exactly ?

Hi

It´s a scripting competition at www.autoit.de.

Every month, Waluev gives us a new exercise.

For example: in march we had to write a hangman-game.

Winner is the fastest / smallest / best looking /... (depending on the exercise) script.

E

eukalyptus · October 30, 2008

Fixed a bug in _BigNum_Div

and I´ve added a Debug_To_Text option.

Just set the Global Const $BigNum_Debug to True and a TXT-File with the single calculation steps will be created...

E

jennico · December 7, 2009

amazing speed - good work ! this udf should be added to the official includes !

i am impressed

j.

Edit: updated Eukalyptus' UDF

added:

_BigNum_Pow

_BigNum_SQRT

_BigNum_n_Root

no changes applied to original functions

discussion and examples later in this thread.

#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 = $n²
; 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

j.

Edited December 10, 2009 by jennico

Mat · December 7, 2009

amazing speed - good work ! this udf should be added to the official includes !
i am impressed
j.

And it should have a bit more than 84 downloads too. I have added it to my list of links as well.

Mat

jennico · December 7, 2009

problem of this thread is, that you cannot find it because there is hardly text in here with keywords. so i will add some tags:

BigInt BigDec BigNum BigNumber BigDecimal BigInteger overflow stringnumber floating float limitation limit big factorial fibonacci pi calculation arbitrary precision _BigNum_Add _BigNum_Sub _BigNum_Mul _BigNum_Div _BigNum_Mod _BigNum_Round _BigNum_Compare _BigNum_Swap Addition subtrction multiplication division number range size signed

some more operations could be useful: sqrt, exponentiantion, random, abs

j.

jennico · December 7, 2009

concerning the square root:

excluding bignumbers, there is a fantastic algorithm to calculate the sqrt very easy and fast (Newton's method):

While 1

    $n = InputBox("Raw SQRT", "Enter any Number to calculate the Square Root")
    If @error Then ExitLoop

    $timer = TimerInit()
    $g = 10 ^ (Ceiling(StringLen(Int($n)) / 2) - 1)

    For $i = 1 To 50
        $last = $g
        $g = (($n / $g) + $g) / 2
        If $last = $g Then ExitLoop
    Next

    MsgBox(0, "Raw SQRT Result:", "Sqrt(" & $n & ") = " & $g & @CRLF & @CRLF & "Time: " & Round(TimerDiff($timer) / 1000, 10) & " sec" & @CRLF & "Error: " & $g * $g - $n & @CRLF & "Iterations: " & $i)

WEnd

the problem with bignumbers is, that you have to define the desired precision first, because theoretically you could calculate with infinite precision, but infinite time as well. lower precision, on the other hand, will accumulate errors. so it does not really make sense with bignumbers. anyway, at least it helps to calculate the sqrt of small numbers (e.g. 2) to a random precision:

_BigNum_SQRT( [bigNum], [precision] )

#Include <BigNum.au3>

While 1

    $n = InputBox("BigNum SQRT", "Enter any BigNumber to calculate the Square Root")
    If @error Then ExitLoop
    $p = InputBox("BigNum SQRT", "Define the desired precision (decimal places)")
    If @error Then ExitLoop

    $timer = TimerInit()
    ;$l = StringInStr($n, ".") - 1
    ;If $l = -1 Then $l = $n
    ;$l = StringLen($l)
    $g = 1
    
    ;For $i = 3 To $l
    ;   $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 ExitLoop
    Next

    MsgBox(0, "BigNum SQRT Result:", "Sqrt(" & $n & ") = " & $g & @CRLF & @CRLF & "Time: " & Round(TimerDiff($timer) / 1000, 10) & " sec" & @CRLF & "Error: " & _BigNum_Sub (_BigNum_Mul ($g, $g), $n) & @CRLF & @TAB & " (" & _BigNum_Div (_BigNum_Mul (_BigNum_Sub (_BigNum_Mul ($g, $g), $n), 100), $g, 5) & " %)" & @CRLF & "Iterations: " & $i)

WEnd

in this way, i calculated SQRT(2) to 50 decimal places:

Sqrt(2) = 1.41421356237309504880168872420969807856967187537694
Time: 1.0292369561 sec

SQRT(2) to precision 100:

Sqrt(2) = 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727
Time: 3.6602808457 sec

SQRT(2) to precision 500:

Sqrt(2) = 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459686201472851741864088919860955232923048430871432145083976260362799525140798968725339654633180882964062061525835239505474575028775996172983557522033753185701135437460340849884716038689997069900481503054402779031645424782306849293691862158057846311159666871301301561856898723723
Time: 123.7198459581 sec

nice, but quite useless...

j.

edit: improved _BigInt_SQRT()

Edited December 8, 2009 by jennico

jennico · December 8, 2009

well now

i finally succeeded in scripting _BigNum_SQRT with very satisfying results. this could be added to BigNum UDF:

_BigNum_SQRT:

#Include <BigNum.au3>

; #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)
;                            Default: $p = -1 means automatic precision (stringlen of integer part of $n)
; Return values .: Success - Result SQRT($n)
;                            @extended = Precicion of result
;                            @error = Number of Iterations
;                  Failure - -1, sets @error to -1 if $n not valid StringNumber
;                            -1, sets @error to -2 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)
    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(-2, 0, -1)
EndFunc   ;==>_BigNum_SQRT


;# Start Examples

_Example_1()
_Example_2()

;#  Example 1 - SQRT BigNumber with automatic precision

Func _Example_1()
    While 1
        Local $n = InputBox("BigNum SQRT - Example 1", "Enter any BigNumber to calculate its Square Root with automatic precision")
        If @error Then Return
        ;$p = InputBox("BigNum SQRT", "Define the desired precision (decimal places)")
        ;If @error Then Return

        Local $timer = TimerInit()
        Local $g = _BigNum_SQRT($n);, $p)
        Local $steps = @error
        Local $p = @extended
        
        MsgBox(0, "BigNum SQRT Result:", "Sqrt( " & $n & " ) = " & $g & @CRLF & @CRLF & "Time: " & Round(TimerDiff($timer) / 1000, 10) & " sec" & @CRLF & "Error: " & _BigNum_Sub (_BigNum_Mul ($g, $g), $n) & @CRLF & @TAB & " (" & _BigNum_Div (_BigNum_Mul (_BigNum_Sub (_BigNum_Mul ($g, $g), $n), 100), $g, 5) & " %)" & @CRLF & "Iterations: " & $steps & @CRLF & "Automatic precision: " & $p)
    WEnd
EndFunc   ;==>_Example_1


;#  Example 2 - SQRT BigNumber with arbitrary precision

Func _Example_2()
    While 1
        Local $n = 2 ;InputBox("BigNum SQRT", "Enter any BigNumber to calculate the Square Root")
        ;If @error Then Return
        Local $p = InputBox("BigNum SQRT(2) - Example 2", "Define the desired precision (decimal places) for SQRT(2)")
        If @error Then Return

        Local $timer = TimerInit()
        Local $g = _BigNum_SQRT($n, $p)
        Local $steps = @error
        ;$p=@extended
        
        MsgBox(0, "BigNum SQRT Result:", "Sqrt( " & $n & " ) = " & $g & @CRLF & @CRLF & "Time: " & Round(TimerDiff($timer) / 1000, 10) & " sec" & @CRLF & "Error: " & _BigNum_Sub (_BigNum_Mul ($g, $g), $n) & @CRLF & @TAB & " (" & _BigNum_Div (_BigNum_Mul (_BigNum_Sub (_BigNum_Mul ($g, $g), $n), 100), $g, 5) & " %)" & @CRLF & "Iterations: " & $steps & @CRLF & "Precision: " & $p)
    WEnd
EndFunc   ;==>_Example_1

try this very big number as a reference (in Example 1):

Sqrt( 4091003901585987357290452999329796564377935868371155936881162018216821980804517176141145508100318254 ) = 63960956071544047529338853709828067819172266042961.4258272131375271736017940766811164575416725207420800454626613688807390792649133246503981796744005

Time: 12.3042112894 sec
Error: -0.00000000000000000000000000000000000000000000000000601166520170038821256019924587054742167390188347100116103304858424724612102064808643035731561991320069110348870368051385955170224431180496559975
     (-0.00000 %)
Iterations: 12
Automatic precision: 100

j,

edited: _BigNum_SQRT - improved error handling

Edited December 8, 2009 by jennico

Mat · December 8, 2009

Is this going to reach the point where it is faster to use BigNum's than normal numbers?

Apparently newtons method can be used to solve Quadratics... Since you now appear to understand it, any chance of an explanation?

have you tested the accuracy?

Mat

jennico · December 8, 2009

the accuracy is 100%. the error check results are due to rounding according to the desired precision.

only if the iteration limit is reached (100), it will return a false result. i will edit the code above so as it returns an error in this case.

Newton's method (in fact, already the Babylonians new it) is:

- $n is number to be rooted

- $g is a random guess (e.g. 1)

- perform the operation $g = (($n / $g) + $g) / 2 in a loop until it returns twice the same result. this is the correct result.

the term $g = (($n / $g) + $g) / 2 can be transformed to $n = $g^2. the primary guess $g will approach the correct result in a spiral until it does not change anymore because it fulfills $n = $g^2. astonishing thing is that the result usually occurs after only 4 - 12 iterations. i don't know it, but i guess that all calculators use this SQRT method.

it can be used to solve quadratics as well. maybe i will work it out.

iteration is very effective for computer based math. i used lots of different iteration based calculations in my _Primes UDF. funny thing is that all those methods are much older than computers.

j.

Mat · December 8, 2009

Thanks, thats a lot better than wikipedia explains it!

Will it make it faster if you provide a more accurate guess? If so then you could speed it up by doing a simple estimation first.

One more question... How can this be applied to other roots?

Mat

czardas · December 8, 2009

The ancient Greeks did all their geometry with a compas and a straight edge (a ruler without calibration). At least that's what I think is true. I find that quite astonishing.

jennico · December 8, 2009

@mat: the first guess should be placed near the estimated result.

e.g. when int($n) has three or four decimal places, you would guess $g = 10 because 10² = 100.

when int($n) has four or five decimals, you would guess $g = 100 because 100² = 10000.

with 6 or 7, guess 1000, because 1000² = 1000000.

so you can reduce the iterations, but basically it does work with any guess > 0.

accordingly my little algorithm does the approach like this:

$g = 10 ^ (Ceiling(StringLen(Int($n)) / 2) - 1)

in _BigNum_SQRT i use a counting loop instead:

Local $l = StringInStr($n, ".") - 1
If $l = -1 Then $l = StringLen($n)
Local $g = 1
For $i = 3 To $l Step 2
    $g = _BigNum_Mul ($g, 10)
Next

by the way, a quadratic solver is way too easy you don't need Newton, it's just straight forward:

While 1
    $a = InputBox("Quadratic Solver", @CRLF & "ax² + bx + c" & @CRLF & @CRLF & @CRLF & "Enter 'a' :")
    If @error Then Exit
    $b = InputBox("Quadratic Solver", @CRLF & $a & "x² + bx + c" & @CRLF & @CRLF & @CRLF & "Enter 'b' :")
    If @error Then Exit
    $c = InputBox("Quadratic Solver", @CRLF & $a & "x² + " & $b & "x + c" & @CRLF & @CRLF & @CRLF & "Enter 'c' :")
    If @error Then Exit
    MsgBox(0, "Quadratic Solver", @CRLF & $a & "x² + " & $b & "x + " & $c & " = 0 " & @CRLF & @CRLF & "Solution:" & @CRLF & _Algorithm($a, $b, $c))
WEnd

Func _Algorithm($a, $b, $c)
    If $a = 0 Then
        If $b <> 0 Then Return "x = " & - 1 * $c / $b
        If $c = 0 Then Return "all real numbers" 
        Return "none" 
    EndIf
    $d = $b * $b - 4 * $a * $c
    If $d < 0 Then Return "none" 
    If $d = 0 Then Return "x = " & - 1 * $b / (2 * $a)
    Return "x1 = " & (-1 * $b + Sqrt($d)) / (2 * $a) & @CRLF & "x2 = " & (-1 * $b - Sqrt($d)) / (2 * $a)
EndFunc   ;==>_Algorithm

easy to adapt to _BigNum.

cheers

j.

jennico · December 8, 2009

@ czardas:

it's a shame that the romans and moreover the christian church destroyed everything. it was not before Galileo and Columbus when the science recovered from the burning piles. 1000 lost years...

j.

jennico · December 8, 2009

@mat: newton only serves for even two-based roots: 2nd root, 4th root, 8th root 16th root

you just apply the algorithm twice or three times.

j.

jennico · December 9, 2009

ok, derived from Newton's method : n-root algorithm

; #FUNCTION# ;====================================================================================
;
; Name...........: _n_Root
; Description ...: nth Root
; Syntax.........: _n_Root($n [, $e=2])
; Parameters ....: $n - Number to be rooted
;                  $e - [optional] Multiplicity of root (power, exponent)
;                            Default: $e = 2 (=SQRT)
; Return values .: Success - Result $e-root($n)
;                            @extended = Number of Iterations
;                  Failure - -1 and sets @error to 1 if $e = 0
; Author ........: jennicoattminusonlinedotde
; Date ..........: 9.12.09
; References ....: derived from "Newton's Method"
; ;===============================================================================================


Func _n_Root($n, $e = 2)
    If $e = 0 Then Return SetError(1, 0, -1)
    Local $g = 10 ^ (Ceiling(StringLen(Int($n)) / $e) - 1)
    Local $i = 0, $last
    
    While 1
        $i += 1
        $last = $g
        $g = (($n / $g ^ ($e - 1)) + $g * ($e - 1)) / $e
        If $last = $g Then Return SetExtended($i, $g)
    WEnd
EndFunc   ;==>_n_Root


_Example()

;#  Example

Func _Example()
    While 1

        $n = InputBox("Raw nth-root", "Enter any Number to calculate the nth Root")
        If @error Then Return
        $e = InputBox("Raw nth-root", "Enter 'n'  (the multiplicity of the nth Root)")
        If @error Then Return
        
        $timer = TimerInit()

        $g = _n_Root($n, $e)
        $i = @extended

        MsgBox(0, "Raw nth-root Result:", $e & "th root of " & $n & " = " & $g & @CRLF & @CRLF & "Time: " & Round(TimerDiff($timer) / 1000, 10) & " sec" & @CRLF & "Error: " & $g ^ $e - $n & @CRLF & @TAB & "(" & Round(($g ^ $e - $n) * 100 / $n, 6) & " %)" & @CRLF & "Iterations: " & $i)

    WEnd
EndFunc   ;==>_Example

the algo is: $g = (($n / $g ^ ($e - 1)) + $g * ($e - 1)) / $e

when you choose $e=2 then you get Newton again: $g = (($n / $g ) + $g) / 2

it's really fast. doesn't AutoIt need that ?

j.

edit: improved first guess

Edited December 9, 2009 by jennico

Mat · December 9, 2009

I knew it was possible. As to speed:

Func _n_Root_Au3($n, $e)
   Return $n ^ (1 / $e)
EndFunc ; ==> _n_Root_Au3

That runs faster on my computer. I don't know if thats true for big numbers though.

Mat

Edited December 9, 2009 by Mat

jennico · December 9, 2009

That runs faster on my computer

good to see that AutoIt beats the Babylonians - 4000 years later !

Mat · December 9, 2009

Imagine if the greeks had autoit! They say that if the greeks had been very close to inventing electricity, and had already created the first "steam engine".

I don't have a clue how you are supposed to work out on paper x^(1/y)...

Mat

BigNum UDF

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members