模組:BigNumber

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 lib_bit=require('bit32');
local bit={lS=lib_bit.lshift,rS=lib_bit.rshift,Or=lib_bit.bor,And=lib_bit.band}
local utils = {}

p.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 result.point > result:length() then result:fractionalzero()end
		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)
		local this = op1
		if this.isNaN then return this:clone() end
		if op2 < 0 then 
			this = this:inverse(this:length() + 1) 
			op2 = -op2
		end
		if op2 == 0 then 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
			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
			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))
		local lose_time = op2 - two_time
		local to_times = this:clone()
		local zero_flag = 0
		repeat
			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)
			two_time = math.pow(2, math.floor(log2))
			lose_time = lose_time - two_time
			to_times = this:clone()
			if lose_time <= 0 then zero_flag = zero_flag + 1 end
		until zero_flag > 1

		local result = p.bigint(1)
		--for i=1,op2 do
		--	result = result * this
		--end
		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
		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,
}

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,
		base_pow = _base_pow,
		['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 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.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)
		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()
		local first_non_zero, pre_point = myself.data[1], 0
		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
		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 * 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) * 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.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 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 = 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 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 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
		
		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: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()
			i = i + 1
			if i > 20 then break end
		end
		if x0.point > 0 then x0:setpoint(digits)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(base)
		p.bigintmath.base = tonumber(base) or 10
		p.bigintmath.e  = p.bigint("2.718281828459045235360287471352662497")
		p.bigintmath.pi = p.bigint("3.141592653589793238462643383279502884")
		p.bigintmath["π"] = p.bigintmath.pi
		p.bigintmath["°"] = p.bigint(p.bigintmath.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 = 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 utils._convertBase(n, original_base, _destination_base, fractional_flag)
	local digits = {}
	local destination_base = utils.getInitValue(_destination_base, 0)
	local dn, digit = n
	local max_digit = #n + 1
	local i = 0
	while not utils.is_zero(dn) do
		dn, digit = utils.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
		destination_base = utils.getBaseValue(_destination_base, destination_base)
		i = i + 1
	end
	return digits
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 = utils.checkSpecialBase(arg1) or 10
		elseif argTo ~= '' then 
			to = utils.checkSpecialBase(argTo) or 10 
		end
		if arg2 ~= '' then num = tostring(arg2)end
		if arg3 ~= '' then digs = tonumber(arg3) or 0 end
		if argFrom ~= '' then 
			from = utils.checkSpecialBase(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
	local special_base_data_from = utils.specialBaseData[from]
	local special_base_data_to = utils.specialBaseData[to]
	local to_num = tonumber(to) or 10
	local from_num = tonumber(from) or 10
	if math.abs(to_num) < 1 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 from_num < -1 or math.abs(utils.myfloor(from_num) - from_num) > 1e-14 or (special_base_data_from or{}).needtoDecimal then
		mw.log("=")
		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))
		from = 10
	end
	if to_num < 0 and sign < 0 then
		local check = math.abs(to_num)
		if math.abs(utils.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(utils.myfloor(to_num) - to_num) > 1e-14 or math.abs(from_num + 1) < 1e-14 then
		int_digits, fractional_digits, sign = utils.non_integer_base(int_digits, fractional_digits, from, to, sign)
		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
		local num = utils.toDecimal(ori_int_digits, {}, from)
		if math.abs(num) <= 9007199254740991 then 
			local base1 = (math.abs(num) > 0) 
				and ((to_num < 0) 
					and ((num < 0) 
						and string.rep('10', math.abs(num)) 
						or ('1' .. ((math.abs(num - 1) < 1e-14) and '' or string.rep('01', num - 1) )) )
					or string.rep('1', math.abs(num)))
				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("fail to convert to base 1") 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)
	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)
	fractional_result = utils.printAllDigit(fractional_digits, to, precision)

	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 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 utils.is_zero(n)
	for _,d in ipairs(n) do
		if d ~= 0 then return false end
	end
	return true
end

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

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

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

function utils._swap(x,i,y,j) local t = x[i]; x[i] = y[j]; y[j] = t 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.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 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

function utils.factorial(n)
	local result = 1
	for i=1,n do result = result * i end
	if n<0 then for i=1,-n do result = result / i end end
	return result
end

utils.specialBaseData = {
	['!']={
		name = "!",
		page = "阶乘进制",
		digitsplit = ":",
		digitValue = function(digit_id) return utils.factorial(digit_id)end,
		baseValue = function(last)return last + 1 end,
		initbase = function(last)return 1 end,
		printDigit = function(digit)return tostring(digit) end,
		needtoDecimal = true,
		convertBase = utils._convertBase,
	}
}
utils.specialBaseData['！'] = utils.specialBaseData['!']
utils.specialBaseData['阶乘'] = utils.specialBaseData['!']
utils.specialBaseData['阶乘进制'] = utils.specialBaseData['!']
utils.specialBaseData['階乘'] = utils.specialBaseData['!']
utils.specialBaseData['階乘進制'] = utils.specialBaseData['!']
utils.specialBaseData['階乘進位'] = utils.specialBaseData['!']

function utils.getDigitValue(base, digit_id)
	local special_base_data = utils.specialBaseData[base]
	if special_base_data then
		return special_base_data.digitValue(digit_id)
	else
		return math.pow(base, digit_id)
	end
end

function utils.getInitValue(base, last)
	local special_base_data = utils.specialBaseData[base]
	if special_base_data then
		return special_base_data.initbase(last)
	else
		return base
	end
end

function utils.getBaseValue(base, last)
	local special_base_data = utils.specialBaseData[base]
	if special_base_data then
		return special_base_data.baseValue(last)
	else
		return base
	end
end

function utils.checkSpecialBase(base)
	local base_string = mw.text.trim(tostring(base))
	local num_base = tonumber(base_string)
	if num_base then return num_base end
	local special_base_data = utils.specialBaseData[base]
	if special_base_data then return special_base_data.name end
	return nil
end

function utils.print_digit(digit, base)
	local special_base_data = utils.specialBaseData[base]
	if special_base_data then
		return special_base_data.printDigit(digit)
	elseif (tonumber(base)or 10) <= 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

function utils.printAllDigit(digits, base, precision)
	local special_base_data = utils.specialBaseData[base]
	local result, digitcomma = '', ''
	if special_base_data then
		digitcomma = special_base_data.digitsplit
	elseif (tonumber(base) or 10) > 36 then
		digitcomma = ','
	end
	for i=1,#digits do
		if precision >= 0 and i == precision + 1 then break end
		if result ~= '' then result = result .. digitcomma end
		result = result .. utils.print_digit(digits[i], base)
	end
	return result
end

function utils.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] * utils.getDigitValue(base, j)
		j = j + 1
	end
	for i = 1, #fractional_digits do
		n = n + fractional_digits[i] * utils.getDigitValue(base, -i)
	end
	return n
end

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

function utils.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

function utils.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 = ((tonumber(to) or 10) > 36) and ';' or '.'
	local special_base_data_from = utils.specialBaseData[from]
	local special_base_data_to = utils.specialBaseData[to]
	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>(%s)</sub>", result, tostring(to))
	elseif subarg == 2 then
		result = string.format("(%s)<sub>%s</sub>", result, tostring(to))
	elseif subarg == 3 then
		local lib_num2zh = require('Module:NumberToChinese')
		local num = utils.toDecimal(ori_int_digits, ori_fractional_digits, from)
		result = mw.ustring.format("[[%s|%s]]<sub>[[%s|(%s)]]</sub>", 
			tostring(num), result, 
			special_base_data_to and (special_base_data_to.page) or (lib_num2zh._numberToChinese(to)..'進制'), 
			tostring(to))
	end
	return result
end

return p;
模組:BigNumber

使用方法

Lua

模板

注意事項

參見
