模組:BigNumber/sandbox

模块文档[查看] [编辑] [历史] [清除缓存]

以百萬进制運作的大數運算系統（或稱高精度计算）。當中也包含了大數運算进制轉換系統。目前支援加法、減法、乘法、除法與整數冪次。

使用方法

Lua

.bigint("bignumber", base)

以一個指定底數的字串初始化一個大數。底數預設值為10。底數可接受的值與.convertBase函數相同。

參數：

• bignumber（大數）：要初始化的大數。若未輸入則默認為0。
• base（輸入的底數）：輸入值的進位制，默認為10。（參見.convertBase函數的from參數）

例如：

local bigint = require('Module:BigNumber')
print(bigint.bigint("425731578351266") * bigint.bigint("948700000017358"))

輸出：403891548389235902937021275228

這個函數會返回一個bigint物件。每個bigint都可以互相進行加法、減法、乘法、除法和乘冪運算（乘冪運算的指數不能是bigint物件）

每個bigint物件有以下成員函數可供使用：

bigint物件:equal(other)

比較兩個bigint物件的值是否相等

參數：

• other：要和自身比較的另一個數，可以是數字或其他bigint物件

bigint物件:less(other)

比較bigint物件的值是否小於other的值

參數：

• other：要和自身比較的另一個數，可以是數字或其他bigint物件

bigint物件:lessequal(other)

比較bigint物件的值是否小於等於other的值

參數：

• other：要和自身比較的另一個數，可以是數字或其他bigint物件

bigint物件:clone()

製作bigint物件的副本

bigint物件:divsmall(other)

計算bigint物件與一般數字相除的商

參數：

• other：被除數。只能是數字，不可以是bigint物件

bigint物件:inverse(precision)

計算bigint物件所代表的值之倒數

參數：

• precision：運算精度

bigint物件:length()

取得這個bigint物件的位數（含非整數部分）。可用於計算倒數時的精度位數

bigint物件:intlength()

取得這個bigint物件整數部分的位數

.bigintmath

提供支援bigint物件的math函數庫。

使用方法

使用.bigintmath前須先呼叫.bigintmath.init()初始化方能使用當中的各項函數

例如：

local bigint = require('Module:BigNumber')
local mymath = bigint.bigintmath.init()
print(mymath.abs("-12345"))

輸出：12345

成員函數

init(base)：初始化bigint的math函數庫

三角函數（sin、 cos、 tan、 cot、 sinh、 cosh、 tanh、 coth、 asin、 acos、 atan、 atan2、 acot、 asinh、 acosh、 atanh、 acoth）

這些函數是取同界角後（避免經度丟失）直接調用math函數庫的函數。單位是弧度。

deg(x)：弧度轉角度

rad(x)：角度轉弧度

e：數學常數e

pi：數學常數圓周率

huge：無窮大

abs(x)：取絕對值

sgn(x)：取符號函數

floor(x)：取向下取整

ceil(x)：取向上取整

div(x,y)：除法，x / y

inverse(x)：取倒數，小數點16位精度

digits(x)：取得整數的位數

sqrt(x)：使用牛頓法以大數運算計算平方根，過大的數字可能會需要較長的計算時間

modf(x)：將一數拆成整數部分與小數部分

fmod(x,y)：計算x除以y的餘數，商向零取整

exp(x)：計算$e^{x}$

frexp(x)：將x表達為$x=m\times 2^{e}$，回傳m和e

ldexp(m, e)：計算$m\times 2^{e}$

pow(x,y)：計算$x^{y}$

log(x)：計算$\ln x$（直接調用math函數庫的函數）

log(a,x)：計算$\log _{a}x$（直接調用math函數庫的函數）

log10(x)：計算$\log _{10}x$

factorial(x)：計算$x!$

max(x0,x1,x2,...)：取得一系列數字的最大值

min(x0,x1,x2,...)：取得一系列數字的最小值

random(a,b)：取[a,b]之間的亂數。若b未輸入則取[1,a]之間的亂數。若皆未輸入則取[0,1)之間的亂數。

.convertBase("number", base, from, width, precision, sub)

將特定進位制的數字轉成以另一個進位制表示。在本模組中用於大數輸入輸出。本函數可模板调用。

參數：

• number（數字）：（必填）須轉換的數字，以字符串形式輸入。十进制的數字可直接以數字形式輸入，但需注意過大的數字若以數字的形式輸入可能會丟失精度，應視情況換用字串輸入。
• base（目標底數）：目標進位制，可取任意絕對值介於1到9007199254740900之間的所有實數（含負數）、純虛數和高斯整數，可接受非整數的底數，如${\frac {1+{\sqrt {5}}}{2}}$进制。支持特殊进制：「!」表示阶乘进制、「fibcode」表示斐波那契編碼。默認為10。
• from（原始底數）：輸入值的進位制，可取絕對值小於9007199254740900的任意複數，默認為10（如果輸入的數字以「0x」開頭，則默認為16）。
• width（位數補齊）：小數點前至少顯示的位數，達不到時會加「0」。
• precision（小數計算最大位數）：小數點後的位數，達不到時會加「0」。不填該項會顯示所有位數，但不超過20位數。
• sub（輸出模式）：見Template:進制/doc#sub的值。
• prefix：加在輸出值前的維基代碼。number為空時則不加。例如在轉換到十六进制後在前面加上0x。
• suffix：加在輸出值後的維基代碼。number為空時則不加。例如在轉換到八进制後在後面加上<sub>8</sub>。

例如：

local bigint = require('Module:BigNumber')
print(bigint.convertBase({n = 3.14159265358979, base = 3}))

輸出：10.010211012222010（OEIS數列A004602）

由於模組本身是大數運算系統，因此若數字過大失去精度的話可以考慮改成以字串輸入：

bigint.convertBase(123456789123456789)→123456789123460000

bigint.convertBase("123456789123456789")→123456789123456789

._FFT(re, im, length, ifft)

執行快速傅里叶变换。在本模組中用於大數乘法。

參數：

• re（實部陣列）：須傅里叶变换的實部序列
• im（虛部陣列）：須傅里叶变换的虛部序列
• length（長度）：傅里叶变换長度
• ifft（是否為逆變換）：若此參數填入true，則為傅里叶变换的逆變換，若未填，則為正常的傅里叶变换。

模板

搭配{{計算}}使用，僅需將|number class=參數指定為Module:BigNumber.bigintmath即可调用大數運算相關函數。

{{計算| 2^64 | number class=Module:BigNumber.bigintmath}}

→18446744073709551616

對比{{計算| 2^64 }}→1.844674407371e+19

以及{{#expr:2^64 }}→1.844674407371E+19

{{計算| 425731578351266 * 948700000017358 | number class=Module:BigNumber.bigintmath}}

→403891548389235902937021275228

對比{{計算| 425731578351266 * 948700000017358 }}→4.0389154838924e+29

以及{{#expr:425731578351266 * 948700000017358 }}→4.0389154838924E+29

{{計算| factorial(70) | number class=Module:BigNumber.bigintmath}}

→11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000

對比{{計算| factorial(70) }}→1.197857166997e+100

注意事項

雖然大數運算系統（或稱高精度计算）理論上無計算上的上限，但考慮到維基百科伺服器有限制腳本運作時間為10秒（見WP:模板限制）因此也不能運算過大的數；此外冪次的運算是使用傳統的一次一次相乘的方法，因此過大的指數也可能導致超過模板運算上限。雖然目前乘法演算法已使用傅里叶变换進行加速，但使用此模組時仍應留意效能。

此外，本模組主要是設計給整數的大數運算（Big Integer），但有保留小數運算的能力，尤其是運算除法不整除時，多次的除法會導致小數位數的增長，因而導致計算時間增加，因此若需要做多次除法建議取整，可使用number:setpoint(0)或.bigintmath.floor(number)（搭配{{計算}}時使用floor(number)）來清除小數。

參見

• Module:BigNumber/utils

上述文档嵌入自Module:BigNumber/doc。 (编辑 | 历史)
编者可以在本模块的沙盒 (编辑 | 差异)和测试样例 (创建)页面进行实验。
请在/doc子页面中添加分类。 本模块的子页面。

local p={}
local getArgs = require('Module:Arguments').getArgs
local lib_calc = require('Module:Complex_Number/Calculate')
local lib_solve = require("Module:Complex_Number/Solver")
local function is_zero(n)
	for _,d in ipairs(n) do
		if d ~= 0 then return false end
	end
	return true
end

local function myfloor(n)
	if math.abs(math.ceil(n)-n)<1e-12 then return math.ceil(n) end
	return math.floor(n)
end

local function isInt(n)
	return math.abs(myfloor(n)-n)<1e-12
end

local function toDecimal(int_digits, fractional_digits, base)
	local n = int_digits[#int_digits]
	local j = 1
	for i = #int_digits-1, 1, -1 do
		n = n + int_digits[i] * math.pow(base, j)
		j = j + 1
	end
	for i = 1, #fractional_digits do
		n = n + fractional_digits[i] * math.pow(base, -i)
	end
	return n
end

local function non_integer_base(int_digits, fractional_digits, original_base, destination_base)
	local n = toDecimal(int_digits, fractional_digits, original_base)
	local k = myfloor(math.log(n)/math.log(destination_base)) + 1
	local int_result, fractional_result = {}, {}
	for i=k-1,0,-1 do
		local digit = myfloor((n / math.pow(destination_base, i)) % destination_base)
		n = n - digit * math.pow(destination_base, i)
		int_result[#int_result + 1] = digit
	end
	if n > 0 then
		for i=1,20 do
			local digit = myfloor((n / math.pow(destination_base, -i)) % destination_base)
			n = n - digit * math.pow(destination_base, -i)
			fractional_result[#fractional_result + 1] = digit
			if n <= 0 then break end
		end
	end
	return int_result, fractional_result
end

local function modulo_div(n, original_base, destination_base, fractional_flag)
	local carry = 0
	local result = {0}
	for i =fractional_flag and #n or 1,fractional_flag and 1 or #n, fractional_flag and -1 or 1 do
		local d = n[i]
		if fractional_flag then
			d = d * destination_base + carry
			carry = math.floor(d / original_base)
			d = d % original_base
		else
			d = d + original_base * carry
			carry = d % destination_base
			d = math.floor(d / destination_base)
		end
		result[i] = math.floor(d)
	end
	return result, carry
end

local function _convertBase(n, original_base, destination_base, fractional_flag)
	local digits = {}
	local dn, digit = n
	local max_digit = #n + 1
	local i = 0
	while not is_zero(dn) do
		dn, digit = modulo_div(dn, original_base, destination_base, fractional_flag)
		if digit < 0 then
			digit = digit + math.abs(destination_base)
			if fractional_flag then
				for i=1,#dn do
					dn[i] = original_base - dn[i]
				end
			else
				dn[#dn] = dn[#dn] + 1
			end
		end
		if fractional_flag then
			digits[#digits + 1] = digit
			if i >= max_digit then break end
		else
			table.insert(digits, 1, digit)
		end
		i = i + 1
	end
	return digits
end

local function print_base_string(int_result, fractional_result, ori_int_digits, ori_fractional_digits, sign, from, to, _subarg, prefix, suffix)
	local subarg = _subarg or 0
	local point_string = (to > 36) and ';' or '.'
	local result = (prefix or '') .. ((sign < 0) and '−' or '') .. (int_result == '' and '0' or int_result) .. (fractional_result == '' and '' or (point_string..fractional_result)) .. (suffix or '') 
	if subarg == 1 then
		result = string.format("%s<sub>(%d)</sub>", result, to)
	elseif subarg == 2 then
		result = string.format("(%s)<sub>%d</sub>", result, to)
	elseif subarg == 3 then
		local lib_num2zh = require('Module:NumberToChinese')
		local num = toDecimal(ori_int_digits, ori_fractional_digits, from)
		result = mw.ustring.format("[[%s|%s]]<sub>[[%s|(%d)]]</sub>", tostring(num), result, lib_num2zh._numberToChinese(to)..'進制', to)
	end
	return result
end

function p.convertBase(_num, _to, _from, _digs, _precision, _sub)
	local num, from, to, digs, subarg, precision = tostring(_num) or "0", _from or 10, _to or 10, _digs or 0, _sub or 0, _precision or -1
	local default, prefix, suffix = '', '', ''
	local no_from = not _from
	local is_template = false
	if type(_num) == type({}) then
		local frame = _num
		local success, args = false, frame
		if type((((type(_num) == type(0)) and {} or _num) or {}).args) == type({}) then
			success, args = pcall(getArgs, frame, {
	        	parentFirst=true
	        }) --frame.args
			if not success then args = frame.args or frame end
		end
		local arg1 = mw.ustring.gsub(mw.text.trim(args[1] or args['1'] or ''), "[-−]+", "-")
		local arg2 = mw.text.trim(args[2] or args['2'] or args.number or args.Number or args.num or args.Num or args.n or args.N or '')
		local arg3 = mw.text.trim(args[3] or args['3'] or args.width or args.Width or '')
		local argTo = mw.ustring.gsub(mw.text.trim(args.to or args.To or args.base or args.Base or ''), "[-−]+", "-")
		local argFrom = mw.ustring.gsub(mw.text.trim(args.from or args.From or ''), "[-−]+", "-")
		local argSub = mw.text.trim(args['sub'] or args.Sub or '')
		local argDefault = args.default or args.Default or ''
		local argPrecision = mw.text.trim(args.precision or args.Precision or '')
		local argPrefix = args.prefix or args.Prefix or ''
		local argSuffix = args.suffix or args.Suffix or ''
		if arg1 ~= '' then 
			to = tonumber(arg1) or 10
		elseif argTo ~= '' then 
			to = tonumber(argTo) or 10 
		end
		if arg2 ~= '' then num = tostring(arg2)end
		if arg3 ~= '' then digs = tonumber(arg3) or 0 end
		if argFrom ~= '' then 
			from = tonumber(argFrom)
			no_from = not from
			from = from or 10
		else no_from = true end
		if argSub ~= '' then subarg = tonumber(argSub) or 10 end
		if argDefault ~= '' then default = argDefault end
		if argPrefix ~= '' then prefix = argPrefix end
		if argSuffix ~= '' then suffix = argSuffix end
		if argPrecision ~= '' then precision = tonumber(argPrecision) or -1 end
		is_template = true
	end
	if math.abs(to) <= 1 and math.abs(to - 1) > 1e-14 then --base can not less then 1
		if not is_template then error("base can not less then 1") end 
		return default 
	end
	local sign = 1
	num = mw.text.trim(num)
	if _num == nil or num == '' then return default end
	local first_sign = mw.ustring.sub(num,1,1)
	if first_sign == '+' or first_sign == '-' or first_sign == '−' then 
		num = mw.ustring.sub(num,2,-1)
		if first_sign == '-' or first_sign == '−' then 
			sign = -1 
		end
	end
	if no_from or from == 16 then
		local chex_hex = mw.ustring.sub(num,1,2)
		if chex_hex == '0x' or chex_hex == '0X' then
			from = 16
			num = mw.ustring.sub(num,3,-1)
		end
	end
	local ori_int_digits, ori_fractional_digits = lib_calc._getNumString(num)
	if to < 0 and sign < 0 then
		local check = math.abs(to)
		if math.abs(myfloor(check)-check)>1e-14 then
			if not is_template then error(string.format("not support base %s", tostring(to))) end 
			return default
		end
		if sign < 0 then
			sign = 1
			for i=1,#ori_int_digits do ori_int_digits[i] = -ori_int_digits[i]end
			for i=1,#ori_fractional_digits do ori_fractional_digits[i] = -ori_fractional_digits[i]end
		end
	end
	local int_digits, fractional_digits = ori_int_digits, ori_fractional_digits
	if math.abs(myfloor(from) - from) > 1e-14 or math.abs(myfloor(to) - to) > 1e-14 then
		int_digits, fractional_digits = non_integer_base(int_digits, fractional_digits, from, to)
		for i = #fractional_digits, 1, -1 do
			if fractional_digits[i] ~= 0 then break
			else
				table.remove(fractional_digits, i)
			end
		end
	elseif math.abs(to - 1) < 1e-14 then
		local num = toDecimal(ori_int_digits, {}, from)
		if math.abs(num) <= 9007199254740991 then 
			local base1 = (math.abs(num) > 0) and string.rep('1', math.abs(num)) or '0'
			if math.abs(num) < digs then
				local lose_digs = digs - math.abs(num) - ((math.abs(num) > 0) and 0 or 1)
				base1 = string.rep('0', lose_digs) .. base1
			end
			return print_base_string(base1, "", ori_int_digits, {}, sign, from, to, subarg, prefix, suffix)
		end
		if not is_template then error("fail to convert to base 1") end 
		return default
	else
		int_digits = _convertBase(int_digits, from, to, false)
		fractional_digits = _convertBase(fractional_digits, from, to, true)
	end
	local int_result, fractional_result = '', ''
	local function print_digit(digit, base)
		if base <= 36 then
			local char_0 = mw.ustring.codepoint('0')
			local char_A = mw.ustring.codepoint('A') - 10
			local codepoint = digit + ((digit >= 10) and char_A or char_0)
			return mw.ustring.char(codepoint)
		else
			return tostring(digit)
		end
	end
	if #int_digits < digs then
		local lose_digs = digs - #int_digits
		for i=1,lose_digs do
			table.insert(int_digits, 1, 0)
		end
	end
	if #fractional_digits < precision then
		local lose_digs = precision - #fractional_digits
		for i=1,lose_digs do
			fractional_digits[#fractional_digits+1] = 0
		end
	end
	for i=1,#int_digits do
		if int_result ~= '' and to > 36 then int_result = int_result .. ',' end
		int_result = int_result .. print_digit(int_digits[i], to)
	end
	for i=1,#fractional_digits do
		if precision >= 0 and i == precision + 1 then break end
		if fractional_result ~= '' and to > 36 then fractional_result = fractional_result .. ',' end
		fractional_result = fractional_result .. print_digit(fractional_digits[i], to)
	end
	local result = print_base_string(int_result, fractional_result, ori_int_digits, ori_fractional_digits, sign, from, to, subarg, prefix, suffix)
	return result
end

local function _swap(x,i,y,j) local t = x[i]; x[i] = y[j]; y[j] = t end
local lib_bit=require('bit32');local bit={lS=lib_bit.lshift,rS=lib_bit.rshift,Or=lib_bit.bor,And=lib_bit.band}
function bit.rev(x,_len)
	local ans = 0
	for i=1,_len do ans=bit.lS(ans,1);ans=bit.Or(ans,bit.And(x,1));x=bit.rS(x,1) end
	return ans
end

function p._FFT(reA, inA, num, flag)
	local lgn = math.floor(math.log(num) / math.log(2))
	for i=0,num-1 do
		local j = bit.rev(i,lgn)
		if j > i then _swap(reA, i+1, reA, j+1); _swap(inA, i+1, inA, j+1) end
	end
	for s=1,lgn do
		local m = bit.lS(1,s)
		local reWm, inWm = math.cos(2*math.pi/m), math.sin(2*math.pi/m)
		if flag==true then inWm = -inWm end
		local k = 0 while k < num do
			local reW, inW = 1.0, 0.0
			for j=0,math.floor(m/2)-1 do
				local tag = k + j + math.floor(m / 2);
                local reT = reW * (reA[tag+1]or 0) - inW * (inA[tag+1]or 0);
                local inT = reW * (inA[tag+1]or 0) + inW * (reA[tag+1]or 0);
                local reU, inU = (reA[k+j+1]or 0), (inA[k+j+1]or 0);
                reA[k+j+1] = reU + reT; inA[k+j+1] = inU + inT;
                reA[tag+1] = reU - reT; inA[tag+1] = inU - inT;
                local reWt = reW * reWm - inW * inWm;
                local inWt = reW * inWm + inW * reWm;
                reW = reWt; inW = inWt;
			end
		k=k+m end
	end
end

function p.bigint(input_data, base)
	local _base_pow = 6
	local _base = 10 ^ _base_pow
	if type(input_data) == type({}) and (input_data or {})['type'] == 'bigint' then return input_data end
	local bigintMeta = {
		__add = function (op_1, op_2) 
			local op1, op2 = p.bigint(op_1), p.bigint(op_2)
			local result = p.bigint()
			if op1.point > op2.point then op2:setpoint(op1.point)
			elseif op1.point < op2.point then op1:setpoint(op2.point)end
			result.point = op1.point
			local length = math.max(op1:length(), op2:length()) + 1 
			local carry = 0
			for i = 1,length-1 do
				local digit = op1.sign * op1:atl(i) + op2.sign * op2:atl(i) + carry
				if digit >= op1.base then
					carry = 1
					digit = digit - op1.base
				elseif digit < 0 then
					carry = -1
					digit = digit + op1.base
				else
					carry = 0
				end
				result:setl(i, digit)
			end
			if carry > 0 then
				result:setl(length, carry)
			elseif carry < 0 then
				result.sign = -1
				carry = 0
				for i = 1,length-1 do
					local digit = op1.base - result:atl(i) + carry
					carry = -1
					result:setl(i, digit)
				end
			end
			if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
			result.isNaN = op1.isNaN or op2.isNaN 
			return result
		end,
		__sub = function (op_1, op_2) 
			local op1, op2 = p.bigint(op_1), p.bigint(op_2)
			op2.sign = op2.sign * -1
			return op1 + op2
		end,
		__mul = function (op_1, op_2)
			local op1, op2 = p.bigint(op_1), p.bigint(op_2)
			local result = p.bigint()
			local a_sign, b_sign = op1.sign, op2.sign
			local a_is_zero, b_is_zero = true, true
			local res,rea,ina,reb,inb,ret,intt = {0},{0},{0},{0},{0},{0},{0}
			local len1,len2,lent,lenres,_len;
			local s1, s2 = tostring(in1), tostring(in2)
			len1 = op1:length(); len2 = op2:length();
			if len1 > len2 then lent = len1 else lent = len2 end; _len=1
			while _len < lent do _len = bit.lS(_len,1) end _len = bit.lS(_len,1)
		    for i = 0,_len-1 do
				if i < len1 then rea[i+1] = op1.data[len1-i] end
				if i < len2 then reb[i+1] = op2.data[len2-i] end
				a_is_zero = a_is_zero and (rea[i+1]or 0) < 1e-14
				b_is_zero = b_is_zero and (reb[i+1]or 0) < 1e-14
				ina[i+1],inb[i+1] = 0,0;
			end
			local res_sign = a_sign * b_sign
		    if a_is_zero or b_is_zero then
		    	local _zero = p.bigint()
		    	_zero.sign = res_sign < 0 and -1 or 1
		    	return _zero
		    end
			p._FFT(rea,ina,_len,false); p._FFT(reb,inb,_len,false);
		    for i=0,_len-1 do
				local rec = rea[i+1] * reb[i+1] - ina[i+1] * inb[i+1];
				local inc = rea[i+1] * inb[i+1] + ina[i+1] * reb[i+1];
				rea[i+1] = rec; ina[i+1] = inc;
			end
			p._FFT(rea,ina,_len,true);--ifft
		    for i=0,_len-1 do rea[i+1] = rea[i+1] / _len; ina[i+1] = ina[i+1] / _len end
		
		    for i=0,_len-1 do res[i+1] = math.floor(rea[i+1] + 0.5)end
		    for i=0,_len-1 do res[i+2] = (res[i+2]or 0) + math.floor((res[i+1]or 0) / op1.base) ; res[i+1] = (res[i+1]or 0) % op1.base end
		
		    lenres = len1 + len2 + 2;
		    while (res[lenres+1]or 0) == 0 and lenres > 0 do lenres=lenres-1 end
			local j = 1
			for i=lenres,0,-1 do 
				result.data[j] = (res[i+1]or 0)
				j = j + 1
			end
			result.sign = res_sign < 0 and -1 or 1
			result.point = op1.point + op2.point
			if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
			result.isNaN = op1.isNaN or op2.isNaN 
			return result
		end,
		__div = function (op_1, op_2)
			local op1, op2 = p.bigint(op_1), p.bigint(op_2)
			local invop2 = op2:inverse(op_1:length() * 2 + 2)
			local result = op1 * invop2
			result:setpoint(op_1:length() + 1)
			local pointfix = p.bigint("1")
			pointfix.point = result.point
			pointfix:fractionalzero()
			result = result + pointfix
			result:setpoint(op_1:length())
			if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
			result.isNaN = op1.isNaN or op2.isNaN 
			return result
		end,
		__mod = function (op_1, op_2)
			local op1, op2 = p.bigint(op_1), p.bigint(op_2)
			local divided = op1 / op2
			divided:setpoint(0)
			local result = op1 - divided * op2
			if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
			result.isNaN = op1.isNaN or op2.isNaN 
			return result
		end,
		__pow = function (op_1, op_2)
			local op1, op2 = p.bigint(op_1), math.floor(tonumber(tostring(op_2)) or 1)
			if op1.isNaN then return op1:clone() end
			if op2 == 0 then return p.bigint(1) end
			if op2 == 1 then return op1:clone() end
			if op2 == 2 then return op1 * op1 end
			local loge = math.log(op2)
			local log2 = loge / math.log(2)
			if isInt(log2) then
				local result = op1:clone()
				for i=1,log2 do
					result = result * result
				end
				return result
			end
			local log3 = loge / math.log(3)
			if isInt(log3) then
				local result = op1:clone()
				for i=1,log3 do
					result = result * result * result
				end
				return result
			end
			local result = p.bigint(1)
			for i=1,op2 do
				result = result * op1
			end
			return result
		end,
		__tostring = function (this)
			local this_length = this:length()
			local result = ''
			for i = 1, this_length do
				if i == this_length - this.point + 1 then
					result = result .. '.'
				end
				result = result .. string.format(string.format("%%0%dd", _base_pow), this.data[i])
			end
			if result:find("%.") then else
				result = result .. '.'
			end
			result = mw.text.trim(result,"0")
			if result:sub(1,1) == '.' then result = '0' .. result end
			result = mw.text.trim(result,".")
			if mw.text.trim(result) == '' then result = '0' end
			if this.isNaN then result = 'nan' end
			if this.sign < 0 then result = '−' .. result end
			return result
		end,
		__unm = function (this)
			local result = this:clone()
			result.sign = result.sign * -1
			return result
		end,
		__eq = function (op_1, op_2)
			local op1, op2 = p.bigint(op_1), p.bigint(op_2)
			return op1:equal(op2)
		end,
		__lt = function (op_1, op_2)
			return op_1:less(op_2)
		end,
		__le = function (op_1, op_2)
			return op_1:lessequal(op_2)
		end,
	}
	local _bigint = {
		data = {0},
		sign = 1,
		point = 0,
		base = _base,
		['type'] = 'bigint',
		numberType = 'bigint'
	}
	function _bigint:length()
		return #(self.data)
	end
	function _bigint:atl(dig)
		local idx = self:length() - dig + 1
		if idx <= 0 then
			for i = 1,1-idx do
				table.insert(self.data, 1, 0)
			end
		end
		return self.data[self:length() - dig + 1] or 0
	end
	function _bigint:nan()
		self.isNaN = true
		return self
	end
	function _bigint:setl(dig, value)
		local idx = self:length() - dig + 1
		if idx <= 0 then
			for i = 1,1-idx do
				table.insert(self.data, 1, 0)
			end
		end
		self.data[self:length() - dig + 1] = value
		return self
	end
	function _bigint:setpoint(point)
		local point_diff = point - self.point
		if point_diff > 0 then
			for i=1,point_diff do
				self.data[self:length() + 1] = 0
			end
		elseif point_diff < 0 then
			for i=1,-point_diff do
				table.remove( self.data, self:length())
			end
		end
		self.point = point
		return self
	end
	function _bigint:fractionalzero()
		if self.point >= self:length() then
			local lost_digs = self.point - self:length()
			for i=1,lost_digs+1 do
				table.insert(self.data, 1, 0)
			end
		end
	end
	function _bigint:delzero()
		for i=1,self:length()-self.point-1 do
			if math.abs(self.data[1]) > 1e-14 then break
			else
				table.remove( self.data, 1)
			end
		end
		local self_point = self.point
		for i=1,self_point do
			if math.abs(self:atl(1)) > 1e-14 then break
			else
				table.remove( self.data, self:length())
				self.point = self.point - 1
			end
		end
		return self
	end
	function _bigint:equal(op)
		local other = p.bigint(op):clone()
		if self.isNaN or other.isNaN then return false end
		local myself = self:clone()
		myself:delzero()
		other:delzero()
		local max_point = math.max(myself.point, other.point)
		myself:setpoint(max_point + 1)
		other:setpoint(max_point + 1)
		local max_digs = math.max(myself:length(), other:length())
		for i = 1, max_digs do
			if myself:atl(i) ~= other:atl(i) then return false end
		end
		return true
	end
	function _bigint:clone()
		local result = p.bigint()
		for i=1,self:length() do result.data[i] = self.data[i]end
		for k,v in pairs(self) do
			if k~="data" and type(v) ~= type({}) and type(v) ~= type(function()end) then
				result[k] = v
			end
		end
		return result
	end
	function _bigint:intlength()
		local length = self:length() - self.point
		if length == 1 and math.abs(self.data[length]) < 1e-14 then return 0 end
		return length
	end
	function _bigint:divsmall(other)
		local num = (type(other) == type(0)) and other or (tonumber(tostring(other)) or 1)
		local result = self:clone()
		result.data = modulo_div(result.data, result.base, num)
		return result
	end
	function _bigint:inverse(_digs)
		local digs = (_digs or (self:length() * 2)) + 1
		if self:equal(p.bigint("0")) then error("divide by zero") end
		local init = p.bigint("1")
		local intlength = self:intlength()
		for i=1,digs - intlength + 1 do
			init.data[init:length() + 1] = 0
		end
		local myself = self:clone()
		myself:delzero()
		init.data = modulo_div(init.data, myself.base, myself.data[1])
		init.nodelzero = true
		for i=1,intlength-1 do
			table.insert(init.data, 1, 0)
		end
		init.point = digs
		local x0 = (2 - init * self) * init
		x0:fractionalzero()
		x0.nodelzero = true
		x0:setpoint(digs)

		local x1 = x0
		x0 = init

		local i = 0
		while not x0:equal(x1) do
			local new_x1 = (2 - x0 * self) * x0
			new_x1:fractionalzero()
			new_x1.nodelzero = true
			new_x1:setpoint(digs)
			x1 = x0
			x0 = new_x1
			if i > 20 then break end
			i = i + 1
		end
		return x0
	end
	function _bigint:less(other)
		local op1, op2 = p.bigint(self), p.bigint(other)
		if op1.point > op2.point then op2:setpoint(op1.point)
		elseif op1.point < op2.point then op1:setpoint(op2.point)end
		local total_len = math.max(op1:length(), op2:length())
		for i=1,total_len do
			local j = total_len - i + 1
			local a, b = op1:atl(j), op2:atl(j)
			if a ~= b then
				return a < b
			end
		end
		return false
	end
	function _bigint:lessequal(other)
		local op1, op2 = p.bigint(self), p.bigint(other)
		if op1.point > op2.point then op2:setpoint(op1.point)
		elseif op1.point < op2.point then op1:setpoint(op2.point)end
		local total_len = math.max(op1:length(), op2:length())
		for i=1,total_len do
			local j = total_len - i + 1
			local a, b = op1:atl(j), op2:atl(j)
			if a ~= b then
				return a < b
			end
		end
		return true
	end
	setmetatable(_bigint, bigintMeta) 
	if input_data == nil then return _bigint end
	local in_str = tostring(input_data)
	in_str = mw.text.trim(in_str)
	local first_sign = mw.ustring.sub(in_str,1,1)
	if first_sign == '-' or first_sign == '−' then _bigint.sign = -1 end
	local int_digits, fractional_digits = lib_calc._getNumString(in_str)
	local src_base = tonumber(base) or 10
	if math.abs(src_base) <= 1 then src_base = 10 end
	_bigint.data = _convertBase(int_digits, src_base, _base, false)
	fractional_digits = _convertBase(fractional_digits, src_base, _base, true)
	for i=1,#fractional_digits do
		_bigint.data[_bigint:length() + 1] = fractional_digits[i]
	end
	_bigint.point = #fractional_digits
	return _bigint
end

p.bigintmath = {
	abs=function(op)
		local num = p.bigint(op):clone()
		num.sign = 1
		return num
	end,
	floor=function(op)
		local num = p.bigint(op):clone()
		num:setpoint(0)
		return num
	end,
	ceil=function(op)
		local num = p.bigint(op):clone()
		num:delzero()
		if num.point > 0 then
			num:setpoint(0)
			num = num + 1
		end
		return num
	end,
	div=function(op1,op2)
		return op1 / op2
	end,
	re=function(z)return z end,
	nonRealPart=function(z) return 0 end,
	inverse=function(op)
		local num = p.bigint(op):clone()
		return num:inverse(16)
	end,
	digits=function(op)
		local num = p.bigint(op)
		return num:intlength()
	end,
	sqrt=function(op)
		local num = p.bigint(op)
		if num:less(0) then error('square root of negative numbers is not supported') end
		local i = 0
		
		local x0 = p.bigint(-1)
		local x1 = p.bigint(math.sqrt(tonumber(tostring(op))))
		local i = 0
		while not x0:equal(x1) and not x0:equal(x1 - 1) do
			local digits = x0.point
			x0 = x1
			x1 = ((num / x0) + x0):divsmall(2)
			if x0.point > 0 or x1.point > 0 then
				x0:setpoint(0)
				x1:setpoint(0)
			end
			i = i + 1
			if i > 20 then break end
		end
		return x0
	end,
	sgn=function(op)
		local num = p.bigint(op)
		return num.sign
	end,
	pow=function(op_1, op_2)
		local op1, op2 = p.bigint(op_1), math.floor(tonumber(tostring(op_2)) or 1)
		return op1 ^ op2
	end,
	factorial=function(op)
		local num = tonumber(tostring(op)) or 1
		local result = p.bigint(1)
		for i=1,num do
			result = result * i
		end
		return result
	end,
	bigint=function()
		return 1
	end,
	init = function()
		p.bigintmath.e = p.bigint(math.exp(1))
		p.bigintmath.pi = p.bigint(math.pi)
		p.bigintmath["π"] = p.bigint(math.pi)
		p.bigintmath["°"] = p.bigint(math.pi/180)
		p.bigintmath.nan = p.bigint():nan()
		p.bigintmath.zero = p.bigint(0) 
		p.bigintmath.one = p.bigint(1) 
		p.bigintmath[-1] = p.bigint(-1) 
		p.bigintmath[0],p.bigintmath[1] = p.bigint(0),p.bigint(1)
		p.bigintmath.elements = {p.bigint(1)}
		p.bigintmath.numberType = lib_solve._numberType
		p.bigintmath.constructor = p.bigint
		return p.bigintmath
	end
}

return p;