模块:BigNumber

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

以百万进制运作的大数运算系统（或称高精度计算）。当中也包含了大数运算进制变换系统。目前支持加法、减法、乘法、除法与整数幂次。

使用方法

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

local p={}
local getArgs = require('Module:Arguments').getArgs
local yesno = require('Module:Yesno')
local lib_calc = require('Module:Complex_Number/Calculate')
local lib_solve = require("Module:Complex_Number/Solver")
local lib_fact = {} --Module:Factorization
local lib_bit=require('bit32');
local bit={lS=lib_bit.lshift,rS=lib_bit.rshift,Or=lib_bit.bor,And=lib_bit.band}
local utils = require('Module:BigNumber/utils')

--大數運算的Metatable
p.bigintMeta = {
	__add = function (op_1, op_2) --大數加法。如被加數或加數有負值則為大數減法
		local op1, op2 = p.bigint(op_1):clone(), p.bigint(op_2):clone()
		--處理NaN及Inf
		if op1.isNaN or op2.isNaN then return op1.isNaN and op1:clone() or op2:clone() end
		if op1.isInf or op2.isInf then
			if op1.isInf and op2.isInf and (op1.sign ~= op2.sign) then return p.bigint():nan() end
			local result = p.bigint():inf()
			result.sign = op1.isInf and op1.sign or op2.sign
			return result
		end
		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
		--計算位數為原始位數+1 (如果進位的話)
		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
			--低於0則需借位
			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):clone(), p.bigint(op_2):clone()
		op2.sign = op2.sign * -1 --減數取相反數
		return op1 + op2
	end,
	__mul = function (op_1, op_2) --大數乘法 使用FFT加速
		local op1, op2 = p.bigint(op_1), p.bigint(op_2)
		--處理NaN及Inf
		if op1.isNaN or op2.isNaN then return op1.isNaN and op1:clone() or op2:clone() end
		if op1.isInf or op2.isInf then
			local result = p.bigint():inf()
			result.sign = op1.sign * op2.sign
			return result
		end
		local op1_iszero, op2_iszero = op1:equal(0), op2:equal(0)
		local result = p.bigint()
		if op1.isInf or op2.isInf then 
			result:inf()
			result.sing = op1.sing * op2.sing
			return result
		end
		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)
		--填入FFT序列
	    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
	    --執行FFT
		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
		--執行逆FFT
		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 result.point > result:length() then result:fractionalzero()end
		if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
		return result
	end,
	__div = function (op_1, op_2) --大數除法 轉為乘法 (除數取倒數)
		local op1, op2 = p.bigint(op_1), p.bigint(op_2)
		--處理NaN及Inf
		if op1.isNaN or op2.isNaN then return op1.isNaN and op1:clone() or op2:clone() end
		if op1.isInf or op2.isInf then
			if op1.isInf and op2.isInf then return p.bigint():nan() end
			if op1.isInf then return op1:clone() end
			if op2.isInf then return p.bigint(0) end
		end
		--處理零
		local op1_iszero, op2_iszero = op1:equal(0), op2:equal(0)
		if op1_iszero or op2_iszero then
			--被除數和除數皆為零無意義
			if op1_iszero and op2_iszero then return p.bigint():nan() end
			local result = p.bigint():inf()
			result.sign = op1.sign * op2.sign
			--被除數為零結果為零不必計算；除數為零無法計算
			return op2_iszero and result or p.bigint(0)
		end
		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
		return result
	end,
	__mod = function (op_1, op_2)
		local op1, op2 = p.bigint(op_1), p.bigint(op_2)
		--處理NaN及Inf
		if op1.isNaN or op2.isNaN then return op1.isNaN and op1:clone() or op2:clone() end
		if op1.isInf or op2.isInf then
			if op1.isInf or (op1.isInf and op2.isInf) then return p.bigint(0):nan() end
			return op2:clone()
		end
		--處理零
		local op1_iszero, op2_iszero = op1:equal(0), op2:equal(0)
		if op1_iszero or op2_iszero then
			--被除數和除數皆為零餘數為0
			if op1_iszero and op2_iszero then return p.bigint(0) end
			local result = p.bigint():nan()
			result.sign = op1.sign * op2.sign
			--被除數為零結果為零不必計算；除數為零無法計算
			return op2_iszero and result or p.bigint(0)
		end
		if op1:equal(op2) then return p.bigint(0) end
		if p.bigintmath.abs(op1) < p.bigintmath.abs(op2) then 
			if op1.sign == op2.sign then return op1 end
			return op1 + op2
		end
		local divided = op1 / op2
		if divided.sign < 0 and divided.point > 0 then divided = divided - 1 end
		divided:setpoint(0)
		local result = op1 - divided * op2
		if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
		return result
	end,
	__pow = function (op_1, op_2)
		local op1, op2 = p.bigint(op_1), tonumber(tostring(op_2)) or 1
		local this = op1
		--處理NaN及Inf
		if this.isNaN then return this:clone() end
		if this.isInf then 
			if op2 < 0 then return p.bigint(0) end
			if op2 == 0 then return p.bigint(1) end
			return this:clone()
		end
		--非整數的指數不支援，目前僅能計算某數的整數次方。使用一般非高精度的math.pow運算
		local is_op2_exp = tostring(op2):find("[eE][+-]?%d")
		if math.abs(utils.myfloor(op2) - op2) > 1e-14 or is_op2_exp then return p.bigint(math.pow(tonumber(tostring(op_1)) or 1, op2)) end
		if op2 < 0 then --負的次方為倒數自乘
			this = this:inverse(this:length() + 1) 
			op2 = -op2
		end
		--零次方
		if op2 == 0 then 
			--零的零次方無意義
			if op1:equal(0) then return op1:equal():nan() end
			return p.bigint(1) --任意數的零次方為一
		end
		if op2 == 1 then return this:clone() end --任意數一次方為本身
		if op2 == 2 then return this * this end
		local loge = math.log(op2)
		local log2 = loge / math.log(2)
		if utils.isInt(log2) then --次方為2的冪 直接連續自乘，以減少乘法運算的次數
			local result = this:clone()
			for i=1,log2 do
				result = result * result
			end
			return result
		end
		local log3 = loge / math.log(3)
		if utils.isInt(log3) then --次方為3的冪 直接連續的3次自乘，以減少乘法運算的次數
			local result = this:clone()
			for i=1,log3 do
				result = result * result * result
			end
			return result
		end

		local times_data = {}
		local times_times = {}
		
		local two_time = math.pow(2, math.floor(log2)) --其餘情況轉換成2的冪的組合，以減少乘法運算的次數
		local lose_time = op2 - two_time
		local to_times = this:clone()
		local zero_flag = 0
		repeat --重複分成2的冪的組合
			for i=1,log2 do --連續自乘
				to_times = to_times * to_times
			end
			times_data[#times_data+1] = to_times --紀錄本次自乘次數的結果
			times_times[#times_times+1] = two_time
			log2 = math.log(lose_time) / math.log(2) --計算剩餘數字的2的冪的組合
			two_time = math.pow(2, math.floor(log2))
			lose_time = lose_time - two_time --計算扣除本次的2的冪的次數後剩下多少次要乘
			to_times = this:clone()
			if lose_time <= 0 then zero_flag = zero_flag + 1 end --剩餘次數為0為迴圈結束條件
		until zero_flag > 1

		local result = p.bigint(1)
		for i=1,#times_data do --將所有自乘次數的結果相乘
			result = result * times_data[i]
		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", this.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 --將 .XXX 補成 0.XXX
		result = mw.text.trim(result,".") --移除多餘的小數點
		if mw.text.trim(result) == '' then result = '0' end --若整體為空字串，則結果為零
		if this.isInf then result = 'inf' 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,
}

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 _bigint = { --大數資料結構
		data = {0}, --大數的各個位數
		sign = 1, --大數的正負號
		point = 0, --小數位數數量
		base = _base, --運算的底數 (必須是10的次方)
		base_pow = _base_pow, --該底數是10的多少次方，用於處理輸出
		['type'] = 'bigint', --標記type為bigint
		numberType = 'bigint'
	}
	function _bigint:length() --取得大數的位數
		return #(self.data)
	end
	function _bigint:atl(dig) --取得從右起算的第n位數
		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:setl(dig, value) --設定從右起算的第n位數
		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:nan() --標記為NaN
		self.isNaN = true
		return self
	end
	function _bigint:inf() --標記為Inf
		self.isInf = true
		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 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
		if self.isInf or other.isInf then 
			return (self.isInf and other.isInf) and (self.sing == other.sing) or (self.isInf == other.isInf)
		end
		if self.sign ~= other.sign then
			if utils.is_zero(self.data) and utils.is_zero(other.data) then
				return true
			end
			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 = utils.modulo_div(result.data, result.base, num)
		return result
	end
	function _bigint:divdigits(op_2, digit) --大數除法指定計算位數
		local op1, op2 = self, p.bigint(op_2)
		local invop2 = op2:inverse(digit * 2 + 2)
		local result = op1 * invop2
		result:setpoint(digit + 1)
		local pointfix = p.bigint("1")
		pointfix.point = result.point
		pointfix:fractionalzero()
		result = result + pointfix
		result:setpoint(digit)
		if not (op1.nodelzero or op2.nodelzero) then result:delzero() end
		result.isNaN = op1.isNaN or op2.isNaN 
		return result
	end
	function _bigint:inverse(_digs) --大數倒數 (牛頓法)
		if self.isNaN then return p.bigint():nan() end
		if self.isInf then return p.bigint(0) end
		local digs = (_digs or (self:length() * 2)) + 1
		if self:equal(p.bigint("0")) then error("嘗試除以零",2) 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()
		local to_div = self:clone()
		to_div.sign = 1
		myself:delzero()
		local first_non_zero, pre_point = myself.data[1], 0
		--若要計算的數絕對值小於1需要補齊位數
		for i = 2, myself:length() do
			if math.abs(first_non_zero) > 1e-14 then break end
			pre_point = pre_point + 1
			first_non_zero = myself.data[i]
		end
		--以1除以最高位數作為起始值，使用長除法
		init.data = utils.modulo_div(init.data, myself.base, first_non_zero)
		init.nodelzero = true
		for i=1,intlength - pre_point - 1 do
			table.insert(init.data, 1, 0)
		end
		for i=1,pre_point do
			init.data[#init.data + 1] = 0
		end
		init.point = digs
		--設定牛頓法起始值
		local x0 = (2 - init * to_div) * init
		x0:fractionalzero()
		x0.nodelzero = true
		x0:setpoint(digs)

		local x1 = x0
		x0 = init

		local i = 0
		--迭代，當各個位數值不再改變則結束計算
		while not x0:equal(x1) do
			--x1 = (2 - x0 * num) * x0
			local new_x1 = (2 - x0 * to_div) * 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
		x0.sign = self.sign
		return x0
	end
	function _bigint:less(other)
		local op1, op2 = p.bigint(self), p.bigint(other)
		if op1.isNaN or op2.isNaN then return false end
		if op1.isInf or op2.isInf then
			if op1.isInf and op2.isInf then return op1.sign < op2.sign end
			if op1.isInf then return op1.sign < 0 end
			return op2.sign > 0
		end
		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) * op1.sign, op2:atl(j) * op2.sign
			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.isNaN or op2.isNaN then return false end
		if op1.isInf or op2.isInf then
			if op1.isInf and op2.isInf then return op1.sign <= op2.sign end
			if op1.isInf then return op1.sign < 0 end
			return op2.sign > 0
		end
		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) * op1.sign, op2:atl(j) * op2.sign
			if a ~= b then
				return a < b
			end
		end
		return true
	end
	setmetatable(_bigint, p.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 src_base = tonumber(base) or 10
	if src_base < 24 then 
		if utils.isInf(in_str) then return _bigint:inf()  end
		if utils.isNaN(in_str) then return _bigint:nan() end
	end
	--特殊底數的進制先轉成十進制
	if ((base ~= nil) and not tonumber(base)) or (src_base < 0) or (not (utils.isInt(src_base))) or (mw.ustring.match(in_str,"^[+-−]?0[xX]")) then
		first_sign = mw.ustring.sub(in_str,1,1) --先前已記錄正負號，故先移除正負號
		if first_sign == '+' or first_sign == '-' or first_sign == '−' then in_str = mw.ustring.sub(in_str,2,-1)end
		in_str = p.convertBase(in_str .. ((math.abs(src_base) > 36) and ';' or ''), 10, base) --轉成十進制
		first_sign = mw.ustring.sub(in_str,1,1) --若轉換完畢仍有正負號，更新正負號
		if first_sign == '-' or first_sign == '−' then _bigint.sign = _bigint.sign * -1 end
		src_base = 10 --已經轉成十進制
		if in_str:find('i') then _bigint:nan() end
	end
	--從字串讀取位數
	local int_digits, fractional_digits = lib_calc._getNumString(in_str .. ((math.abs(src_base) > 36) and ';' or ''), src_base>14)
	if math.abs(src_base) <= 1 then src_base = 10 end
	--轉換為大數運算的目標進位制
	_bigint.data = utils._convertBase(int_digits, src_base, _base, false)
	fractional_digits = utils._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()
		if num.sign < 0 then
			num.sign = 1
			num = p.bigintmath.ceil(num)
			num.sign = -1
			return num
		end
		num:setpoint(0)
		return num
	end,
	ceil=function(op)
		local num = p.bigint(op):clone()
		if num.sign < 0 then
			num.sign = 1
			num = p.bigintmath.floor(num)
			num.sign = -1
			return num
		end
		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 p.bigint(z) end,
	nonRealPart=function(z) return p.bigint(0) end,
	inverse=function(op)
		local num = p.bigint(op):clone()
		return num:inverse(16)
	end,
	digits=function(op)
		local num = p.bigint(op)
		if num.isInf or num.isNaN then return num:clone() end
		return p.bigint(num:intlength())
	end,
	sqrt=function(op) --計算平方根，牛頓法
		local num = p.bigint(op)
		if num.isInf or num.isNaN then return num:clone() end
		if num:less(0) then error('不支援計算負值的平方根',2) end
		local i = 0
		
		--先用一般的math.sqrt計算
		local init_sqrt = math.sqrt(tonumber(tostring(op)))
		local x0 = p.bigint(-1)
		local x1 = p.bigint(init_sqrt)
		local check_sqrt = tostring(init_sqrt)
		if check_sqrt:find("[Ee]") then else
			local strlen = check_sqrt:gsub("%.",''):len()
			--若結果位於有效數字內，則直接回傳運算結果
			if strlen < 13 then
				return x1
			end
		end
		--若計算的數字大小超過math.sqrt能計算的範圍及精度，則開始調用牛頓法
		local i = 0
		local digits = x1:length()+num:length()
		--計算至各個位數不變時則停止
		while not x0:equal(x1) and not x0:equal(x1 - 1) do
			x0 = x1
			--牛頓法迭代
			-- x1 = (num / x0 + x0) / 2
			x1 = (num:divdigits(x0,digits+3) + x0):divsmall(2)
			if x0.point > 0 or x1.point > 0 then
				x0:setpoint(digits+2)
				x1:setpoint(digits+2)
			end
			x0:delzero()
			x1:delzero()
			--避免無窮迴圈，設定最高迭代次數
			if i > 20 then break end
			i = i + 1
		end
		if x0.point > 0 then x0:setpoint(digits)end
		return x0
	end,
	modf = function (op_1)
		local op1 = p.bigint(op_1):clone()
		local sign = op1.sign
		local int_part = p.bigint(op_1):clone()
		op1.sign = 1
		int_part.sign = 1
		int_part:setpoint(0)
		local frac_part = op1 - int_part
		int_part.sign = sign
		frac_part.sign = sign
		return int_part, frac_part
	end,
	fmod = function (op_1, op_2)
		local op1, op2 = p.bigint(op_1), p.bigint(op_2)
		--處理NaN及Inf
		if op1.isNaN or op2.isNaN then return op1.isNaN and op1:clone() or op2:clone() end
		if op1.isInf or op2.isInf then
			if op1.isInf or (op1.isInf and op2.isInf) then return p.bigint(0):nan() end
			return op2:clone()
		end
		--處理零
		local op1_iszero, op2_iszero = op1:equal(0), op2:equal(0)
		if op1_iszero or op2_iszero then
			--被除數和除數皆為零餘數為0
			if op1_iszero and op2_iszero then return p.bigint(0) end
			local result = p.bigint():nan()
			result.sign = op1.sign * op2.sign
			--被除數為零結果為零不必計算；除數為零無法計算
			return op2_iszero and result or p.bigint(0)
		end
		if op1:equal(op2) then return p.bigint(0) end
		if p.bigintmath.abs(op1) < p.bigintmath.abs(op2) then return op1 end
		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,
	frexp=function(op)
		local num = tostring(op)
		local bignum = p.bigint(op)
		local result = p.bigint()
		--處理NaN及Inf
		if utils.isNaN(num) then return p.bigint(op), p.bigint(0)end
		if utils.isInf(num) then return p.bigint(op), p.bigint(0)end
		--計算目標數是2的多少次方
		local log2 = math.log(math.abs(tonumber(num) or 1)) / math.log(2)
		--為了避免精度丟失，當是2的負數次方時，乘到正數次方
		if log2 < 0 then
			log2 = utils.myceil(log2)
			bignum = bignum * (p.bigint(2)^math.abs(log2))
			num = tostring(bignum)
		else log2 = 0 end
		--轉換為二進制
		local result_str = p.convertBase(num, 2, 10, 0, 192) --使用比double高3倍的精度以便處理無窮小數 (64 * 3 = 192)
		local sign_text = mw.ustring.sub(result_str,1,1)
		local sign = 1
		--讀取正負號
		if sign_text == '+' or sign_text == '-' or sign_text == '−' then
			result_str = mw.ustring.sub(result_str,2,-1)
			sign = (sign_text == '-' or sign_text == '−') and -1 or 1
		end
		--frexp當x為零，則回傳兩個零
		if result_str=='0' then 
			result.sign = sign
			return result, p.bigint(0)
		end
		--當數值為0.XXX時
		if result_str:sub(1,2) == '0.' then
			if result_str:match("0%.[1-9]")then
				return p.bigint(num), p.bigint(0 + log2)
			else --當數值為0.00...00XXX
				result_str = result_str:sub(3,-1) --去除 "0."
				local find_num = result_str:find("[1-9]") --找到第一個有效數字
				if not find_num then --找不到意味著數字為0
					result.sign = sign
					return result, p.bigint(0)
				end
				result_str = '0.'..result_str:sub(find_num,-1) --處理成0.XXX
				result_str = p.convertBase(result_str, 10, 2, 0, result.base_pow * 9) --轉回十進制
				result = p.bigint(result_str) --超出的精度處理
				local pointfix = p.bigint("1") --準備一個極小的數值相加，讓諸如 0.999999....的可以進位
				pointfix.point = result.point
				pointfix:fractionalzero()
				result.sign = 1
				result = result + pointfix
				result:setpoint(8)
				result:delzero()
				result.sign = sign
				return result, p.bigint(log2 - find_num + 1)
			end
		else --當數值為 XX.XXX 時
			local find_point = (result_str..'.'):find("%.")
			local turn_str = result_str:gsub("%.",'')
			turn_str = '0.'..turn_str
			result = p.bigint(turn_str,2)
			result.sign = sign
			return result, p.bigint(find_point-1)
		end
	end,
	max=function(...)
		local nums = {...}
		local max_val = -p.bigint():inf()
		for i=1,#nums do
			local value = p.bigint(nums[i])
			if not utils.isNaN(value) then
				if max_val < value then
					max_val = value
				end
			end
		end
		return max_val
	end,
	min=function(...)
		local nums = {...}
		local min_val = p.bigint():inf()
		for i=1,#nums do
			local value = p.bigint(nums[i])
			if not utils.isNaN(value) then
				if value < min_val then
					min_val = value
				end
			end
		end
		return min_val
	end,
	random=function(op_1, op_2)
		if (not op_1) and (not op_2) then
			local random_number = '0.'
			for i=1,36 do random_number=string.format("%s%d", random_number, math.random(0,9))end
			return p.bigint(random_number)
		end
		--計算op1到op2之間的亂數
		local op1, op2 = p.bigint(op_1), p.bigint(op_2)
		if not op_2 then --若只輸入op1，則計算1到op1之間的亂數
			op2 = op1
			op1 = p.bigint(1)
		end
		if op2 < op1 then --若op1較大，則計算op2到op1之間的亂數
			local tmp = op1
			op1 = op2
			op2 = tmp
		end
		op1:setpoint(0)--取整
		op2:setpoint(0)
		if op1:equal(op2) then return op1:clone() end --若op1==op2則直接回傳
		local all_digit = op2 - op1
		local random_number = ''
		local all_digit_number = tonumber(tostring(all_digit))
		if all_digit_number < 2147483647 then --若落在math.random可計算的範圍內則直接計算
			random_number = p.bigint(math.random(0, all_digit_number))
		else
			all_digit:delzero()
			local all_digit_length = all_digit:length()
			for i=1,all_digit_length do random_number=string.format(string.format("%%s%%0%dd", all_digit.base_pow), random_number, math.random(0,all_digit.base))end
			random_number = p.bigint(random_number)
			random_number = random_number % (all_digit + 1)
		end
		return random_number + op1
	end,
	coterminal_angle=function(op)
		if not p.bigintmath.isinit then p.bigintmath.init() end
		local num = p.bigint(op)
		local twopi = p.bigintmath.pi * 2
		return num - p.bigintmath.floor(num / twopi) * twopi
	end,
	deg=function(op)
		if not p.bigintmath.isinit then p.bigintmath.init() end
		local num = p.bigint(op)
		return num * 180 / p.bigintmath.pi
	end,
	rad=function(op)
		if not p.bigintmath.isinit then p.bigintmath.init() end
		local num = p.bigint(op)
		return num * p.bigintmath["°"]
	end,
	sin=function(op_1)
		local op1 = tonumber(tostring(p.bigintmath.coterminal_angle(p.bigint(op_1)))) or 0
		return p.bigint(math.sin(op1))
	end,
	cos=function(op_1)
		if not p.bigintmath.isinit then p.bigintmath.init() end
		local op1 = tonumber(tostring(p.bigintmath.coterminal_angle(p.bigint(op_1)))) or p.bigintmath.pi
		return p.bigint(math.cos(op1))
	end,
	tan=function(op_1)
		local op1 = tonumber(tostring(p.bigintmath.coterminal_angle(p.bigint(op_1)))) or 0
		return p.bigint(math.tan(op1))
	end,
	cot=function(op_1)
		local op1 = tonumber(tostring(p.bigintmath.coterminal_angle(p.bigint(op_1)))) or 0
		return p.bigint(1/math.tan(op1))
	end,
	asin=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 0
		return p.bigint(math.asin(op1))
	end,
	acos=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.acos(op1))
	end,
	atan=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.atan(op1))
	end,
	atan2=function(op_1, op_2)
		local op1, op2 = tonumber(tostring(op_1)) or 1, tonumber(tostring(op_2)) or 1
		return p.bigint(math.atan2(op1, op2))
	end,
	acot=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.atan(1/op1))
	end,
	sinh=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 0
		return p.bigint(math.sinh(op1))
	end,
	cosh=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.cosh(op1))
	end,
	tanh=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.tanh(op1))
	end,
	coth=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.cosh(op1) / math.sinh(op1))
	end,
	asinh=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 0
		return p.bigint(math.log( op1 + math.sqrt( op1 * op1 + 1 ) ))
	end,
	acosh=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(math.log( op1 + math.sqrt( op1 * op1 - 1 ) ))
	end,
	atanh=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(0.5 * math.log((1+op1)/(1-op1)))
	end,
	acoth=function(op_1)
		local op1 = tonumber(tostring(op_1)) or 1
		return p.bigint(0.5 * math.log((op1+1)/(op1-1)))
	end,
	dot=function (op_1, op_2)
		local op1, op2 = p.bigint(op_1), p.bigint(op_2)
		return op1 * op2
	end,
	sgn=function(op)
		local num = p.bigint(op)
		return p.bigint(num.sign)
	end,
	exp=function(op)
		if not p.bigintmath.isinit then p.bigintmath.init() end
		local result = p.bigintmath.e ^ tonumber(tostring(op))
		result:setpoint(p.bigintmath.e.point)
		return result
	end,
	ldexp=function(op1, op2)
		return p.bigint(op1) * (p.bigint(2) ^ tonumber(tostring(op2)))
	end,
	pow=function(op_1, op_2)
		local op1, op2 = p.bigint(op_1), tonumber(tostring(op_2)) or 1
		return op1 ^ op2
	end,
	elog=function(op_1)
		local invlog10e = p.bigint("2.30258509299404568401799145468436420760110148862877297603332790096757260967735248023599720508960")--1/log10(e)
		local result = p.bigintmath.log10(op_1) * invlog10e--1/log10(e)
		result:setpoint(invlog10e.point)
		return result
	end,
	["log10"]=function(op)
		local num_str = tostring(op)
		--處理NaN及Inf
		if utils.isNaN(num_str) then return p.bigint():nan() end
		if utils.isInf(num_str) then return p.bigint(op) end
		local result_str = num_str
		local sign_text = result_str:sub(1,1)
		local sign = 1
		if sign_text == '+' or sign_text == '-' or sign_text == '−' then
			result_str = mw.ustring.sub(result_str,2,-1)
			sign = (sign_text == '-' or sign_text == '−') and -1 or 1
		end
		if sign < 0 then return -p.bigint():nan() end
		local result_str_len = result_str:len()
		local digits = 0
		if result_str:match("^[0.]+$") then --零
			return -p.bigint():inf() --log(0) = -inf
		end
		--當數值為0.XXX時
		if result_str:sub(1,2) == '0.' then
			result_str = result_str:sub(3,-1) --去除 "0."
			local find_num = result_str:find("[1-9]") --找到第一個有效數字
			if not find_num then --找不到意味著數字為0
				return -p.bigint():inf()
			end
			--處理成X.XXX
			result_str = result_str:sub(find_num,find_num)..((find_num >= result_str_len)and''or('.'..result_str:sub(find_num+1,-1)))
			digits = -find_num
		else --當數值為 XX.XXX 時
			local find_point = (result_str..'.'):find("%.")
			local turn_str = result_str:gsub("%.",'')
			--處理成X.XXX
			result_str = (turn_str:len()==1) and turn_str or (turn_str:sub(1,1)..'.'..turn_str:sub(2,-1))
			digits = find_point-2
		end
		--計算X.XXX的常用對數
		local log_value = p.bigint(math.log10(tonumber(result_str)))
		--將結果與位數相加
		log_value = log_value + digits
		return log_value
	end,
	log=function(_z,_basez)
		local z = tonumber(tostring(_z)) or 1
		local basez = tonumber(tostring(_basez))
		if basez~=nil then return math.log(basez) / math.log(z) end
		return p.bigint(math.log(z))
	end,

	factorial=function(op)
		local num = math.floor(tonumber(tostring(op)) or 1)
		if num < 0 then return p.bigint():inf() end
		local result = p.bigint(1)
		for i=1,num do
			result = result * i
		end
		return result
	end,
	bigint=function()
		return 1
	end,
	init = function(base)
		p.bigintmath.base = tonumber(base) or 10
		p.bigintmath.e  = p.bigint("2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852517")
		p.bigintmath.pi = p.bigint("3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534212")
		p.bigintmath["π"] = p.bigintmath.pi
		p.bigintmath["°"] = p.bigint(p.bigintmath.pi/180)
		p.bigintmath.nan = p.bigint():nan()
		p.bigintmath.inf = p.bigint():inf()
		p.bigintmath.huge = p.bigintmath.inf
		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.isinit = true
		p.bigintmath.constructor = function(x)
			if type(x) == type({}) and (x or {})['type'] == 'bigint' then return x end
			if tonumber(tostring(x), p.bigintmath.base) then
				return p.bigint(x)
			end
			return nil
		end
		return p.bigintmath
	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 utils._swap(reA, i+1, reA, j+1); utils._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 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.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 from_str, to_str = tostring(_from or ''), tostring(_to or '')
	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
		is_template = true
		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 
			success, to = pcall(utils.checkSpecialBase, arg1)
			to = to or arg1
			to_str = tostring(arg1)
		elseif argTo ~= '' then 
			success, to = pcall(utils.checkSpecialBase, argTo)
			to = to or argTo
			to_str = tostring(argTo)
		end
		num = tostring(arg2)
		if arg3 ~= '' then digs = tonumber(arg3) or 0 end
		if argFrom ~= '' then 
			success, from = pcall(utils.checkSpecialBase, argFrom)
			no_from = not from
			from = from or argFrom
			from_str = tostring(argFrom)
		else no_from = true end
		if argSub ~= '' then subarg = tonumber(argSub) or 0 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
		if yesno(args.error or args.Error or '') then is_template = false end
	end
	
	---------------- 例外處理 ----------------
	--無限大判斷 (若放任無限大進去計算會無窮迴圈而超時)
	if utils.isInf(from) then
		if mw.ustring.find(num, "[,:]") then --判斷是否為多個位數的字串
			check_digits = lib_calc._getNumString(num..';')
			for i=1,#check_digits do if check_digits[1] == 0 then table.remove(check_digits, 1) end end
			if #check_digits > 1 then --不只一個位數的無限大進制無法轉換
				if not is_template then error(string.format("底數不能為 '%s'", from_str),2) end
				return utils.print_base_string('∞', --硬要說的話其值就是無限大
					"", {tonumber("inf")}, {},({mw.ustring.find(num, "[-−]")})[1] and -1 or 1, from, to, subarg, prefix, suffix)
			end
		end
		--只有一個位數的無限大進制就原數輸出
		local find_point = mw.ustring.find(num, "%.")
		local targen_decimal = find_point and mw.ustring.sub(num, 1, find_point-1) or num
		return p.convertBase({to,targen_decimal,digs,from=10,sub=subarg,default=default,precision=precision,prefix=prefix,error=not is_template})
	end
	if mw.ustring.match(num,"^%s*[+-−]?%s*∞%s*$")then--本身是無限大就不用算了，因為無法計算
		return utils.print_base_string(num, "", {tonumber("inf")}, {},({mw.ustring.find(num, "[-−]")})[1] and -1 or 1, from, to, subarg, prefix, suffix)
	end
	
	--NaN判斷 (若放任NaN進去計算會無窮迴圈而超時)
	if utils.isNaN(from) then --並非有效的底數，無法轉換
		if not is_template then error(string.format("底數不能為 '%s'", from_str),2) end
		return default
	end
	if utils.isNaN(to) then --並非有效的底數，無法轉換
		if not is_template then error(string.format("底數不能為 '%s'", to_str),2) end
		return default
	end
	
	--大過整數運算範圍的底數無法計算 (誤差導致運算結果不準確)
	if math.abs(utils.tonumber(from)or 0) > 9007199254740991 and not utils.isInf(from) then
		if not is_template then error(string.format("底數 '%s' 過大", from_str),2) end
		return default
	end
	if math.abs(utils.tonumber(to)or 0) > 9007199254740991 and not utils.isInf(to) then
		if not is_template then error(string.format("底數 '%s' 過大", to_str),2) end
		return default
	end
	
	--判斷是否為特殊進制
	local special_base_data_from, from_error = utils.getSpecialBase(from)
	local special_base_data_to, to_error = utils.getSpecialBase(to)
	
	if from_error then
		if not is_template then error(from_error,2) end
		return default
	end
	if to_error then
		if not is_template then error(to_error,2) end
		return default
	end
	
	if (not utils.tonumber(from) and not special_base_data_from) or (not utils.tonumber(to) and not special_base_data_to) then
		--複數進位制
		local success, int_string, frac_string = pcall(utils.complexBaseConvert, num, to, from, digs, precision)
		if success and int_string then
			return utils.print_base_string(int_string, frac_string, {}, {}, 1, from, to, subarg, prefix, suffix)
		elseif not success then
			local error_result = mw.ustring.match(tostring(int_string or ''), '轉換失敗：(.-)。')
			if error_result then
				if not is_template then error(error_result, 2) end
				return default
			end
		end
	end
	--並非能夠運算的底數
	if not utils.tonumber(from) and not special_base_data_from then
		if not is_template then error(string.format("'%s' 不是有效的底數", from_str),2) end
		return default
	end
	if not utils.tonumber(to) and not special_base_data_to then
		if not is_template then error(string.format("'%s' 不是有效的底數", to_str),2) end
		return default
	end
	---------------- 例外處理結束，開始轉換進制 ----------------
	local to_num = utils.tonumber(to) or 10
	local from_num = utils.tonumber(from) or 10
	if math.abs(to_num) < 1 then --base can not less then 1
		if not is_template then error("底數的絕對值不能小於1",2) 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
	--當輸入開頭為'0x'時視為16進制
	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
	--Fibonacci code word是反向排列的
	if (special_base_data_from or {}).name=="fibcode" then
		local find_point = mw.ustring.find(num, "%.")
		if find_point then num = mw.ustring.sub(num, 1, find_point-1)end
		local fibcode2fibbase = ''
		for i=1,#num-1 do fibcode2fibbase = mw.ustring.sub(num, i, i) .. fibcode2fibbase end
		num = fibcode2fibbase..'0'
	end
	
	local ori_int_digits, ori_fractional_digits = lib_calc._getNumString(num, math.abs(from_num) > 14)
	--負進制、非整數進制等無法經由長除法整數進制轉整數進制的Case先轉為十進制再做處理
	if from_num < -1 or math.abs(utils.myfloor(from_num) - from_num) > 1e-14 or (special_base_data_from or{}).needtoDecimal then
		if (special_base_data_from or{}).name == 'ContinuedFraction' then
			local dec_string = tostring(utils.fromContinuedFraction(ori_int_digits, ori_fractional_digits))
			ori_int_digits, ori_fractional_digits = lib_calc._getNumString(dec_string, math.abs(from_num) > 14)
		else
			local dec_number = utils.toDecimal(ori_int_digits, ori_fractional_digits, from) * sign
			if dec_number < 0 then
				sign = -1
				dec_number = -dec_number
			else
				sign = 1
			end
			ori_int_digits, ori_fractional_digits = lib_calc._getNumString(tostring(dec_number), math.abs(from_num) > 14)
		end
		from = 10
	end
	local ori_sign = sign
	if to_num < 0 then
		local check = math.abs(to_num)
		--負底數進制在轉換過程中要連正負號一同考量
		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(utils.myfloor(to_num) - to_num) > 1e-14 or math.abs(from_num + 1) < 1e-14 then --非整數進制的處理
		if to_num > 0 then
			int_digits, fractional_digits, sign = utils.non_integer_base(int_digits, fractional_digits, from, to, sign)
		else
			int_digits, fractional_digits, sign = utils.real_negabase(int_digits, fractional_digits, from, to, sign)
		end
		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(math.abs(to_num) - 1) < 1e-14 then --一進制，自然數中最簡單的進制，輸出跟數字相同數量的1即可
		local number = utils.myfloor(utils.toDecimal(ori_int_digits, {}, from))
		if math.abs(number) <= 9007199254740991 then --Lua整數運算上限
			local base1 = (math.abs(number) > 0) 
				and ((to_num < 0) 
					and ((number < 0) 
						and string.rep('10', math.abs(number)) 
						or ('1' .. ((math.abs(number - 1) < 1e-14) and '' or string.rep('01', number - 1) )) )
					or string.rep('1', math.abs(number)))
				or '0'
			if base1:len() < digs then --補齊位數
				local lose_digs = digs - base1:len()
				base1 = string.rep('0', lose_digs) .. base1
			end
			return utils.print_base_string(base1, "", ori_int_digits, {},(to_num < 0) and 1 or sign, from, to, subarg, prefix, suffix)
		end
		if not is_template then error(string.format("無法將 '%s' 轉換為底數 '%s' 的進制", num, to_str),2) end 
		return default
	else --其餘情況即一般情況，使用整數進制轉整數進制的長除法演算法
		int_digits = ((special_base_data_to or{}).convertBase or utils._convertBase)(int_digits, from, to, false)
		fractional_digits = ((special_base_data_to or{}).convertBase or utils._convertBase)(fractional_digits, from, to, true, tonumber(precision<0 and '' or precision))
		if to_num < 0 then int_digits, fractional_digits = utils.negabaseCarry(int_digits, fractional_digits, to_num, ori_sign)end
	end
	---------------- 進制轉換完成，準備輸出數字 ----------------
	local int_result, fractional_result = '', ''

	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
	
	int_result = utils.printAllDigit(int_digits, to, -1, subarg, false)
	fractional_result = utils.printAllDigit(fractional_digits, to, precision, subarg, true)

	local result = utils.print_base_string(int_result, fractional_result, ori_int_digits, ori_fractional_digits, sign, from, to, subarg, prefix, suffix)
	return result
end

function utils.fromContinuedFraction(int_digits, fractional_digits)
	local result = p.bigint(0)
	local calclen = math.floor(#fractional_digits / 6) + 1
	for i=#fractional_digits,1,-1 do
		result = (result + fractional_digits[i]):inverse(calclen + 2)
	end
	result:setpoint(calclen)
	local result = ''..(int_digits[1] or 0)..'.'..tostring(result):gsub("^%d+%.","")
	return result
end

function utils.ContinuedFraction(digits, original_base, _destination_base, fractional_flag, total_digit)
	local result_digits, zero_digits = {}, {}
	local decimal_string = ''
	if not fractional_flag then
		result_digits = utils._convertBase(digits, original_base, 10, false)
		for i=1,#result_digits do
			if math.abs(tonumber(result_digits[1]) or 1) < 1e-14 then
				table.remove(result_digits, 1)
			end
		end
		decimal_string = table.concat(result_digits, "")
		if decimal_string == '' then decimal_string = 0 end
		return {decimal_string}
	end
	result_digits = utils._convertBase(digits, original_base, 10, true)
	decimal_string = '0.'..table.concat(result_digits, "")
	zero_digits, result_digits = p.ContinuedFraction(decimal_string, math.ceil(total_digit or (decimal_string:len() * 0.8)))
	return result_digits
end

--以大數運算計算連分數
function p.ContinuedFraction(input_str, _length)
	local num = input_str
	local length = tonumber(_length) or 10
	local is_template = false
	local suffix = _suffix or ''
	if type(input_str) == type({"table"}) then
		num = (input_str.args or {})[1] or input_str[1] or ''
		length = tonumber((input_str.args or {})[2] or input_str[2] or '') or 4
		if input_str.args then is_template = true end
	elseif type(input_str) ~= type("string") then
		num = tostring(input_str)
	end

	local input_num = p.bigint(num)
	local sign = input_num.sign
	input_num.sign = 1
	local calclen = (input_num:length() < 4) and (input_num:length() * 2) or (input_num:length() + 2)
	local int_part = input_num:clone():setpoint(0)
	local int_digits, fractional_digits = {tonumber(tostring(int_part))}, {}
	local it = input_num - int_part
	local i = 1
	while not it:equal(0) do
		it = it:inverse(calclen)
		int_part = it:clone():setpoint(0)
		fractional_digits[#fractional_digits + 1] = tonumber(tostring(int_part))
		it = it - int_part
		if i >= length then break end
		i = i + 1
	end
	if is_template then
		return table.concat(int_digits,',') .. ';' .. table.concat(fractional_digits,',')
	end
	return int_digits, fractional_digits
end

return p