#include-once

;Opt("MustDeclareVars", 1)

Func _BigNum_Pow($sB, $iE = 2)
	$iE = Number($iE)
	Select
		Case Not IsInt($iE)
			Return SetError(1, 1, -1)
		Case $iE < 0
			Return SetError(1, 2, -1)
		Case $iE = 0
			Return "1"
		Case $iE = 1
			Return $sB
	EndSelect

	If Not _BigNum_IsValid($sB) Then Return SetError(1, 3, -1)

	Local $sR = "1"

	While $iE
		If Mod($iE, 2) Then
			$sR = _BigNum_Mul($sB, $sR)
			$iE -= 1
		EndIf
		$sB = _BigNum_Mul($sB, $sB)
		$iE = $iE / 2
	WEnd

	Return $sR
EndFunc   ;==>_BigNum_Pow





Func _BigNum_SQRT($sX, $iD = -1)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, -1)
	If __BN_Abs($sX) Then Return "-1"

	Local $iLX = StringInStr($sX, ".") - 1
	If $iLX = -1 Then $iLX = StringLen($sX)
	If $iD < 0 Then $iD = $iLX
	Local $sG = "1" & __BN_Null(Floor(($iLX - 1) / 2))
	Local $sLast

	For $i = 1 To 100
		$sLast = $sG
		$sG = _BigNum_Div(_BigNum_Add(_BigNum_Div($sX, $sG, $iD), $sG), 2, $iD)
		If $sLast = $sG Then Return SetError(0, $i, $sG)
	Next
	Return SetError(-3, 0, -1)
EndFunc   ;==>_BigNum_SQRT



Func _BigNum_n_Root($sX, $iE = 2, $iD = -1)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, -1)
	If __BN_Abs($sX) Then Return "-1"

	$iE = Number($iE)
	Select
		Case Not IsInt($iE)
			Return SetError(1, 1, -1)
		Case $iE < 1
			Return SetError(1, 2, -1)
		Case $iE = 1
			Return $sX
	EndSelect

	Local $iLX = StringInStr($sX, ".") - 1
	If $iLX = -1 Then $iLX = StringLen($sX)
	If $iD < 0 Then $iD = $iLX
	Local $sG = "1" & __BN_Null(Floor(($iLX - 1) / 2))
	Local $sLast, $i = 0

	While 1
		$i += 1
		$sLast = $sG
		$sG = _BigNum_Div(_BigNum_Add(_BigNum_Div($sX, _BigNum_Pow($sG, $iE - 1), $iD), _BigNum_Mul($sG, $iE - 1)), $iE, $iD)
		If $sLast = $sG Then Return SetError(0, $i, $sG)
	WEnd

	Return SetError(-3, 0, -1)
EndFunc   ;==>_BigNum_n_Root








Func _BigNum_Div($sX, $sY, $iD = 20)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	If Not _BigNum_IsValid($sY) Then Return SetError(1, 2, False)

	Local $bNgX = __BN_Abs($sX)
	Local $bNgY = __BN_Abs($sY)
	Local $iDec = __BN_RemDec($sX, $sY)

	Local $sMod, $sDec, $sRet

	$sMod = "0"
	Select
		Case $sX = "0" Or $sY = "0" ; Div oder Did = 0
			Return 0

		Case $sY = "1" ; Div = 1
			If ($sX <> "0") And BitXOR($bNgX, $bNgY) Then
				Return "-" & $sX
			Else
				Return $sX
			EndIf

		Case Else
			Switch __BN_Comp($sX, $sY)
				Case -1 ; X ist kleiner also = Rest
					$sRet = "0"
					$sMod = $sX
				Case 0 ; X und Y gleich
					If BitXOR($bNgX, $bNgY) Then
						Return "-1"
					Else
						Return "1"
					EndIf

				Case Else
					Switch StringLen($sY)
						Case 0 To 14 ; Div ist max 14 Zeichan lang => Didision kann "normal" gerechnet werden
							$sRet = __BN_Div_14($sX, $sY, $sMod)
						Case Else ; Lange Division
							$sRet = __BN_Div_14P($sX, $sY, $sMod)
					EndSwitch
			EndSwitch
	EndSelect

	Switch StringLen($sY)
		Case 0 To 14 ; Div ist max 14 Zeichan lang => Didision kann "normal" gerechnet werden
			$sDec = __BN_Div_14($sMod & __BN_Null($iD), $sY, $sMod)
		Case Else ; Lange Division
			$sDec = __BN_Div_14P($sMod & __BN_Null($iD), $sY, $sMod)
	EndSwitch

	$sRet = $sRet & StringLeft(StringFormat("%0" & $iD & "s", $sDec), $iD)

	__BN_InsDec($sRet, $iD)

	If ($sRet <> "0") And BitXOR($bNgX, $bNgY) Then
		Return "-" & $sRet
	Else
		Return $sRet
	EndIf
EndFunc   ;==>_BigNum_Div





Func _BigNum_Round($sX, $iD = 0)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	Local $sRet = $sX
	Local $bNgX = __BN_Abs($sX)
	Local $sTmp = "0"
	Local $iDec = __BN_RemDec($sX, $sTmp)

	If $iD < 0 Then $iD = 0

	If $iD > $iDec Or $iDec = 0 Then Return $sRet

	$sTmp = StringLeft(StringRight($sX, $iDec - $iD), 1)
	$sRet = StringTrimRight($sRet, $iDec - $iD)

	If $sTmp >= 5 And $iD > 0 Then
		If $bNgX Then
			$sRet = _BigNum_Add($sRet, "-0." & __BN_Null($iD - 1) & "1")
		Else
			$sRet = _BigNum_Add($sRet, "0." & __BN_Null($iD - 1) & "1")
		EndIf
	ElseIf $sTmp >= 5 And $iD = 0 Then
		If $bNgX 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








Func _BigNum_Mod($sX, $sY)
	Local $sMod
	_BigNum_DivR($sX, $sY, $sMod)
	If @error Then Return SetError(@error, @extended, False)
	Return $sMod
EndFunc   ;==>_BigNum_Mod




Func _BigNum_DivR($sX, $sY, ByRef $sM)
	$sM = "0"
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	If Not _BigNum_IsValid($sY) Then Return SetError(1, 2, False)

	Local $bNgX = __BN_Abs($sX)
	Local $bNgY = __BN_Abs($sY)
	Local $iDec = __BN_RemDec($sX, $sY)

	Local $sRet
	Select
		Case $sX = "0" Or $sY = "0" ; Div oder Did = 0
			$sRet = "0"
		Case $sY = "1" ; Div = 1
			$sRet = $sX
		Case Else
			Switch __BN_Comp($sX, $sY)
				Case -1 ; X ist kleiner also = Rest
					$sRet = "0"
					$sM = $sX
				Case 0 ; X und Y gleich
					$sRet = "1"
				Case Else
					Switch StringLen($sY)
						Case 0 To 14 ; Div ist max 14 Zeichan lang => Didision kann "normal" gerechnet werden
							$sRet = __BN_Div_14($sX, $sY, $sM)
						Case Else ; Lange Division
							$sRet = __BN_Div_14P($sX, $sY, $sM)
					EndSwitch
			EndSwitch
	EndSelect

	__BN_InsDec($sM, $iDec)

	If ($sM <> "0") And ($bNgX = True) Then $sM = "-" & $sM

	If ($sRet <> "0") And BitXOR($bNgX, $bNgY) Then
		Return "-" & $sRet
	Else
		Return $sRet
	EndIf
EndFunc   ;==>_BigNum_DivR




Func __BN_Div_14($sX, $iY, ByRef $iM)
	$iY = Int($iY)

	Local $sRet = "", $iRem = StringLeft($sX, 15), $iTmp = 0, $iTrm = 6, $iLen
	$sX = StringTrimLeft($sX, 15)
	$iTmp = Floor($iRem / $iY)
	$sRet &= $iTmp

	$iRem -= $iTmp * $iY
	While StringLen($sX) > 0
		$iTrm = 15 - StringLen($iRem)
		$iTmp = StringLeft($sX, $iTrm)
		$iLen = StringLen($iTmp)
		$iRem &= $iTmp
		$sX = StringTrimLeft($sX, $iTrm)
		$iTmp = Floor($iRem / $iY)
		$iTmp = StringRight("000000000000000" & $iTmp, $iLen)

		$sRet &= $iTmp
		$iRem -= $iTmp * $iY
	WEnd
	$iM = $iRem

	Return StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc   ;==>__BN_Div_14


Func __BN_Div_14P($sX, $sY, ByRef $sM)
	Local $aDiv[11] = ["0", $sY]

	For $i = 2 To 10
		$aDiv[$i] = __BN_Add($aDiv[$i - 1], $sY) ; LookUpTable
	Next

	Local $iLY = StringLen($sY)
	Local $bReady = False
	Local $sRet = "", $sRem = StringLeft($sX, $iLY), $sTmp = "", $iTrm, $iCnt, $iLen = 1
	$sX = StringTrimLeft($sX, $iLY)

	Local $iTile, $iOff, $iCnt, $iComp

	Do
		If __BN_Comp($sRem, $sY) = -1 Then
			$sTmp = StringLeft($sX, 1)
			$sRem &= $sTmp
			$sX = StringTrimLeft($sX, 1)
			If StringLen($sTmp) > 0 Then $iLen += 1
		EndIf

		$iTile = 5
		$iOff = 0

		While $iTile > 0
			$iCnt = $iOff + $iTile
			If $iCnt > 10 Then
				$iCnt = 10
				ExitLoop
			EndIf
			$iComp = __BN_Comp($sRem, $aDiv[$iCnt])
			If $iComp = 0 Then
				$iCnt += 1
				ExitLoop
			ElseIf $iComp = -1 Then
				$iTile = Floor($iTile / 2)
			Else
				$iOff += $iTile
			EndIf
		WEnd

		$iCnt -= 1

		If StringLen($sX) = 0 Then $bReady = True
		$sM = $sRem
		$sRem = __BN_Sub($sRem, $aDiv[$iCnt])
		If $iCnt > 0 Then $sM = $sRem
		$sRet &= StringFormat("%0" & String($iLen) & "u", $iCnt)
		$iTrm = $iLY - StringLen($sRem)
		$sTmp = StringLeft($sX, $iTrm)
		$sX = StringTrimLeft($sX, $iTrm)
		$iLen = StringLen($sTmp)
		$sRem &= $sTmp
	Until $bReady
	$sM = StringRegExpReplace($sM, "^0+([^0]|0$)", "\1", 1)

	Return StringRegExpReplace($sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc   ;==>__BN_Div_14P








Func _BigNum_Mul($sX, $sY)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	If Not _BigNum_IsValid($sY) Then Return SetError(1, 2, False)

	Local $bNgX = __BN_Abs($sX)
	Local $bNgY = __BN_Abs($sY)
	Local $iDec = __BN_RemDec($sX, $sY)

	Local $iLX = StringLen($sX)
	Local $iLY = StringLen($sY)

	Local $sRet

	Select
		Case $iLX < 10 And $iLY < 10
			$sRet = String(Int($sX) * Int($sY))

		Case $iLY < 10
			$sRet = __BN_Mul_9($sX, $sY, $iLX)

		Case $iLX < 10
			$sRet = __BN_Mul_9($sY, $sX, $iLY)

		Case Else
			Local $aX = __BN_Mul_Split($sX)
			Local $aY = __BN_Mul_Split($sY)
			Local $aRet, $sRet
			If $aX[0] < $aY[0] Then
				$aRet = __BN_Mul($aX, $aY)
				$sRet = __BN_Mul_Merge($aRet)
			Else
				$aRet = __BN_Mul($aY, $aX)
				$sRet = __BN_Mul_Merge($aRet)
			EndIf

	EndSelect

	__BN_InsDec($sRet, $iDec * 2)

	If ($sRet <> "0") And BitXOR($bNgX, $bNgY) Then
		Return "-" & $sRet
	Else
		Return $sRet
	EndIf

EndFunc   ;==>_BigNum_Mul





Func __BN_Mul_9($sX, $iY, $iLX)
	$iY = Int($iY)
	Local $iCar = 0, $sRet = "", $iTmp

	For $i = 1 To $iLX Step 9
		$iTmp = Int(StringRight($sX, 9)) * $iY + $iCar
		$sX = StringTrimRight($sX, 9)

		$iCar = Int(StringTrimRight($iTmp, 9))
		$iTmp = Mod($iTmp, 1000000000)
		If $iTmp < 999999999 Then $iTmp = StringRight("000000000" & $iTmp, 9)

		$sRet = $iTmp & $sRet
	Next

	Return StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc   ;==>__BN_Mul_9





Func __BN_Mul($aX, $aY)
	Local $iX = $aX[0]
	Local $iY = $aY[0]
	Local $iR = $iX + $iY
	Local $aR[$iR + 1]

	For $r = 0 To $iR
		$aR[$r] = 0
	Next

	Local $sR = "", $iC = 0

	For $x = 1 To $iX
		For $y = 1 To $iY
			$aR[$x + $y - 1] += $aX[$x] * $aY[$y]
		Next
		$iC = 0
		For $r = $x To $x + $iY - 1
			$aR[$r] += $iC
			$iC = Int(StringTrimRight($aR[$r], 9))
			$aR[$r] = Mod($aR[$r], 1000000000)
		Next
		$aR[$x + $iY] += $iC
	Next
	If $aR[$iR] = 0 Then
		$aR[0] = $iR - 1
	Else
		$aR[0] = $iR
	EndIf
	Return $aR
EndFunc   ;==>__BN_Mul


Func __BN_Mul_Split($sX)
	Local $iLX = StringLen($sX)
	Local $aX = StringRegExp($sX, '\A.{' & 9 - (Ceiling($iLX / 9) * 9 - $iLX) & '}|.{' & 9 & '}+', 3)
	Local $iX = UBound($aX)
	Local $aR[$iX + 1] = [$iX]
	For $i = 0 To $iX - 1
		$aR[$iX - $i] = Int($aX[$i])
	Next
	Return $aR
EndFunc   ;==>__BN_Mul_Split


Func __BN_Mul_Merge($aR)
	Local $sR = ""

	For $r = 1 To $aR[0]
		If $aR[$r] < 1000000000 Then $aR[$r] = StringRight("0000000000" & $aR[$r], 9)
		$sR = $aR[$r] & $sR
	Next

	Return StringRegExpReplace($sR, "^0+([^0]|0$)", "\1", 1)
EndFunc   ;==>__BN_Mul_Merge


























Func __BN_RemDec(ByRef $sX, ByRef $sY)
	Local $iPX = StringInStr($sX & ".", ".", 0, 1) - 1
	Local $iPY = StringInStr($sY & ".", ".", 0, 1) - 1

	$sX = StringReplace($sX, ".", "")
	$sY = StringReplace($sY, ".", "")
	Local $iLX = StringLen($sX) - $iPX
	Local $iLY = StringLen($sY) - $iPY

	If $iLX > $iLY Then
		$sY = StringLeft($sY & __BN_Null($iLX + $iPY), $iLX + $iPY)
		Return $iLX
	ElseIf $iLX < $iLY Then
		$sX = StringLeft($sX & __BN_Null($iLY + $iPX), $iLY + $iPX)
		Return $iLY
	EndIf

	Return $iLX
EndFunc   ;==>__BN_RemDec





Func __BN_InsDec(ByRef $sX, $iPX)
	If $iPX < 1 Then Return
	If StringLen($sX) < $iPX Then $sX = StringFormat("%0" & $iPX & "s", $sX)
	$sX = StringTrimRight($sX, $iPX) & "." & StringRight($sX, $iPX)
	If StringLeft($sX, 1) = "." Then $sX = "0" & $sX
	$sX = StringRegExpReplace($sX, "[0]+$", "") ;entferne Nullen am Ende (nach dem Komma)
	$sX = StringRegExpReplace($sX, "\.+$", "") ;entferne Komma, wenn keine Zahlen dahinter
EndFunc   ;==>__BN_InsDec





Func __BN_Null($iC)
	Local $tT = DllStructCreate("byte[" & Ceiling($iC / 2) & "];")
	Return StringRight(DllStructGetData($tT, 1), $iC)
EndFunc   ;==>__BN_Null





Func _BigNum_Add($sX, $sY)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	If Not _BigNum_IsValid($sY) Then Return SetError(1, 2, False)

	Local $bNgX = __BN_Abs($sX)
	Local $bNgY = __BN_Abs($sY)
	Local $iDec = __BN_RemDec($sX, $sY)
	Local $bNg = False
	Local $sRet

	Select
		Case ($bNgX = True) And ($bNgY = True)
			$sRet = __BN_Add($sX, $sY)
			$bNg = True
		Case ($bNgX = True) And ($bNgY = False)
			$sRet = __BN_Sub($sY, $sX)
			$bNg = __BN_Abs($sRet)
		Case ($bNgX = False) And ($bNgY = True)
			$sRet = __BN_Sub($sX, $sY)
			$bNg = __BN_Abs($sRet)
		Case Else
			$sRet = __BN_Add($sX, $sY)
	EndSelect

	__BN_InsDec($sRet, $iDec)

	If $bNg = True And $sRet <> "0" Then
		Return "-" & $sRet
	Else
		Return $sRet
	EndIf
EndFunc   ;==>_BigNum_Add




Func __BN_Add($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
			$iTmp = StringRight($iTmp, 18)
			$sRet = $iTmp & $sRet
			$iCar = 1
		Else
			$iTmp = StringRight("000000000000000000" & $iTmp, 18)
			$sRet = $iTmp & $sRet
			$iCar = 0
		EndIf
	Next

	Return StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc   ;==>__BN_Add







Func _BigNum_Sub($sX, $sY)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	If Not _BigNum_IsValid($sY) Then Return SetError(1, 2, False)

	Local $bNgX = __BN_Abs($sX)
	Local $bNgY = __BN_Abs($sY)
	Local $iDec = __BN_RemDec($sX, $sY)

	Local $bNg = False
	Local $sRet

	Select
		Case ($bNgX = True) And ($bNgY = True)
			$sRet = __BN_Sub($sY, $sX)
			$bNg = __BN_Abs($sRet)
		Case ($bNgX = True) And ($bNgY = False)
			$sRet = __BN_Add($sY, $sX)
			$bNg = True
		Case ($bNgX = False) And ($bNgY = True)
			$sRet = __BN_Add($sX, $sY)
		Case Else
			$sRet = __BN_Sub($sX, $sY)
			$bNg = __BN_Abs($sRet)
	EndSelect

	__BN_InsDec($sRet, $iDec)

	If $bNg = True And $sRet <> "0" Then
		Return "-" & $sRet
	Else
		Return $sRet
	EndIf

EndFunc   ;==>_BigNum_Sub



Func __BN_Sub($sX, $sY)
	If __BN_Comp($sX, $sY) = -1 Then Return "-" & __BN_Sub($sY, $sX)

	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
	Return StringRegExpReplace($iCar & $sRet, "^0+([^0]|0$)", "\1", 1)
EndFunc   ;==>__BN_Sub





Func _BigNum_Compare($sX, $sY)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	If Not _BigNum_IsValid($sY) Then Return SetError(1, 2, False)
	Local $bNgX = __BN_Abs($sX)
	Local $bNgY = __BN_Abs($sY)

	Select
		Case ($bNgX = True) And ($bNgY = True)
			__BN_Swap($sX, $sY)
		Case ($bNgX = True) And ($bNgY = False)
			Return -1
		Case ($bNgX = False) And ($bNgY = True)
			Return 1
	EndSelect

	Return __BN_Comp($sX, $sY)
EndFunc   ;==>_BigNum_Compare





Func __BN_Comp($sX, $sY)
	If StringLeft($sX, 1) = "0" Then $sX = StringRegExpReplace($sX, "^0+([^0]|0$)", "\1", 1)
	If StringLeft($sY, 1) = "0" Then $sY = StringRegExpReplace($sY, "^0+([^0]|0$)", "\1", 1)
	Local $iLX = StringLen($sX)
	Local $iLY = StringLen($sY)
	Select
		Case $iLX > $iLY
			Return 1
		Case $iLX < $iLY
			Return -1
		Case Else
			Return StringCompare($sX, $sY)
	EndSelect
EndFunc   ;==>__BN_Comp





Func __BN_Swap(ByRef $sX, ByRef $sY)
	Local $sTmp = $sX
	$sX = $sY
	$sY = $sTmp
EndFunc   ;==>__BN_Swap





;Zahl war negativ => Extended = True
Func _BigNum_Abs($sX)
	If Not _BigNum_IsValid($sX) Then Return SetError(1, 1, False)
	Local $bNeg = __BN_Abs($sX)
	Return SetError(0, $bNeg, $sX)
EndFunc   ;==>_BigNum_Abs


;Zahl war negativ => Return = True
Func __BN_Abs(ByRef $sX)
	Local $bNg = False
	While StringLeft($sX, 1) = "-"
		$bNg = Not $bNg
		$sX = StringTrimLeft($sX, 1)
	WEnd
	$sX = StringRegExpReplace($sX, "^0+([^0]|0$)", "\1", 1)
	Return $bNg
EndFunc   ;==>__BN_Abs







Func _BigNum_IsValid($sX)
	Return StringRegExp($sX, "(?m)^\-*\d+\.?\d*$")
EndFunc   ;==>_BigNum_IsValid