Editing Module:BigNumber/utils

local main_module = "Module:BigNumber"
local utils = {}
local cmath = {}
local bignum = {}
local lib_calc = {}

--大數帶餘長除法 / 可作為進制轉換用的帶餘長除法
function utils.modulo_div(n, _original_base, destination_base, fractional_flag)
	local original_base = tonumber(_original_base)
	local non_number_base = not original_base --確認是否為非數字進制
	if non_number_base then original_base = 1 end
	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
		if non_number_base then 
			original_base = utils.getBaseValue(_original_base, fractional_flag and (-i) or (#n - i))
			if utils.isInf(original_base) then original_base = 10 end --若混合底數出現無限大作為十進制計算
		end
		local d = n[i]
		if fractional_flag then --進制轉換時，小數點以後用乘的
			d = d * math.abs(destination_base) + carry
			carry = math.floor(d / original_base)
			d = utils.mod(d, original_base)
			if destination_base < 0 then d = -d end
		else --對每個位數進行帶餘長除法
			d = d + original_base * carry --上一位的餘數，取下一位
			carry = utils.mod(d, destination_base) --新的餘數 
			d = math.floor(d / destination_base) --商
		end
		result[i] = math.floor(d) --紀錄商
	end
	if fractional_flag and destination_base < 0 then carry = -carry end
	return result, carry --回傳商, 餘數
end

function utils._convertBase(n, _original_base, _destination_base, fractional_flag, total_digit)
	local digits = {}
	if utils.isInf(_original_base) then
		error(string.format("底數不能為 '%s'", tostring(_original_base)),2)
	end
	if fractional_flag and utils.isInf(_destination_base) then --無限大進制的小數位數位置值為 1/無限大 是零，無法表示小數
		return {}
	end
	local original_base = utils.getBaseValue(_original_base, 0)
	local destination_base = utils.getBaseValue(_destination_base, 0)
	local dn, digit = n
	local max_digit = total_digit or math.max(#n+1, 20) --未指定時不超過20位
	local i = 0
	local src_max_digit = #dn

	--進位轉換為不斷帶餘除法直到商為0
	while not utils.is_zero(dn) do
		destination_base = utils.getBaseValue(_destination_base, fractional_flag and (-i - 1) or i)
		--以帶餘長除法計算各個位數 (回傳值 => 商, 位數)
		dn, digit = utils.modulo_div(dn, _original_base, destination_base, fractional_flag)
		if digit < 0 then --負底數進位會遇到餘數小於0的情況
			digit = digit + math.abs(destination_base) --加成正的
			if fractional_flag then
			else --商+1 (因為等於多減一次除數)
				dn[#dn] = dn[#dn] + 1
			end
		end
		--計算小數時，位數加在末尾
		if fractional_flag then
			if utils.isNaN(digit) then break end
			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

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.round(n)
	return utils.myfloor(n + 0.5)
end

function utils.mod(n, m)
	if utils.isInf(m) then return n end
	return n % m
end

function utils.loop_mod(n, m)
	if utils.isInf(m) then return n end
	local result = n % m
	return (result == 0) and m or result
end

function utils.tonumber(n)
	local check = tostring(n)
	check = mw.ustring.gsub(check, '∞', 'inf')
	return tonumber(check)
end

function utils.tostring(n)
	local result = tostring(n)
	result = mw.ustring.gsub(result, '^%s*([+-]?)inf%s*$', '%1∞')
	result = mw.ustring.gsub(result, '%-', '−')
	return result
end

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

function utils.isInf(num)
	local num_str = tostring(num):lower()
	return num_str=='inf' or num_str=='-inf' or num_str=='−inf' or num_str=='+inf'
end

function utils.isNaN(num)
	local num_str = tostring(num):lower()
	return num_str=='nan' or num_str=='-nan' or num_str=='−nan' or num_str=='+nan'
end

function utils.cintpow(num, power)
	if type(cmath.constructor) ~= type(tostring) then cmath = require("Module:Complex Number").cmath.init()end
	power = utils.round(power)
	local this = cmath[0] + cmath.constructor(num)
	if power < 0 then --負的次方為倒數自乘
		this = cmath.inverse(this) 
		power = -power
	end
	if power == 0 then return cmath[0] + 1 end
	if power == 1 then return cmath[0] + this end
	if power == 2 then return this * this end
	local loge = math.log(power)
	local log2 = loge / math.log(2)
	if utils.isInt(log2) then --次方為2的冪 直接連續自乘，以減少乘法運算的次數
		local result = this
		for i=1,log2 do result = result * result end
		return result
	end
	local times_data = {}
	local times_times = {}
	local two_time = utils.round(math.pow(2, math.floor(log2))) --其餘情況轉換成2的冪的組合，以減少乘法運算的次數
	local lose_time = power - two_time
	local to_times = cmath[0] + this
	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 = cmath[0] + this
		if lose_time <= 0 then zero_flag = zero_flag + 1 end --剩餘次數為0為迴圈結束條件
	until zero_flag > 1
	local result = cmath[1]
	for i=1,#times_data do result = result * times_data[i]end --將所有自乘次數的結果相乘
	return result
end

function utils._swap(x,i,y,j) local t = x[i]; x[i] = y[j]; y[j] = t end

function utils.fibonacci_coding(int_digits, original_base, _destination_base, fractional_flag, total_digit, fib_code)
	local sqrt5 = math.sqrt(5)
	local phi = (sqrt5 + 1) * 0.5
	local logphi = math.log(phi)
	local function fibonacciId(x)return utils.myceil(math.log(x*sqrt5-0.5)/logphi)end
	local function fibonacci(an)return math.floor(math.pow(phi, an) / sqrt5 + 0.5)end
	if fractional_flag then 
		if fib_code then return {} end
		local number = utils.toDecimal({0}, int_digits, original_base)
		if number == 0 then return {} end
		local max_digs = total_digit or math.max(#int_digits + 1,20)
		local result = {}
		for i=1,max_digs do
			local place_value = 1 / fibonacci(i+2)
			if place_value > number then
				result[#result + 1] = 0
			else
				result[#result + 1] = 1
				number = number - place_value
			end
			if number == 0 then break end
		end
		return result 
	end
	local n = utils.myfloor(utils.toDecimal(int_digits, {}, original_base))
	if math.abs(tonumber(table.concat(int_digits,''))-1)<1e-14 then 
		return fib_code and {1,1} or {1,0} 
	end

	local k = utils.myceil(math.log(n*sqrt5-0.5)/logphi)
	local vaild_fib = {}
	local max_id = 0
	local x0 = n
	while x0 > 0 do
		local id = fibonacciId(x0)
		local digval = fibonacci(id)
		if digval > x0 then 
			id = id - 1
			digval = fibonacci(id)
		end
		x0 = x0 - digval
		if id > max_id then max_id = id end
		vaild_fib[id] = 1
	end
	local result = {}
	for i=max_id,(fib_code and 2 or 1),-1 do
		result[#result + 1] = vaild_fib[i] or 0
	end
	if fib_code then
		local the_code = {1}
		for i=1,#result do
			table.insert(the_code, 1, result[i])
		end
		return the_code
	end
	return result
end

function utils.real_negabase(int_digits, fractional_digits, original_base, destination_base, _sign)
	local num = utils.toDecimal(int_digits, fractional_digits, original_base)
	local sign = _sign
	if _sign < 0 then 
		sign = sign * -1
		num = -num
	end
	local b = destination_base
	local sb = math.abs(b)
	local mb, pb = -sb / (sb + 1), 1 / (sb + 1)
	local lb, rb = mb, pb
	if lb > rb then lb, rb = pb, mb end
	local p_chack = math.log((num/lb > 0) and num/lb or num/rb)/math.log(sb)
	local fp, cp = math.floor(p_chack), math.ceil(p_chack)
	local lp, rp = fp, cp
	if lp > rp then lp, rp = cp, fp end
	local p_list = {lp-1, lp, rp, rp+1}
	local p = lp
	local min_x = math.huge
	for i=1,#p_list do
		local p0 = num / math.pow(b, p_list[i])
		if p0 >= lb and p0 <= rb then
			if p0 < min_x then
				min_x = p0
				p = p_list[i]
			end
		end
	end
	local Tb = function(x) return b*x - math.floor(b*x-lb) end
	local Tbj = min_x
	if p<0 then Tbj = num end
	local k = p
	local int_result, fractional_result = {}, {}
	for i=k-1,0,-1 do
		local digit = math.floor(b * Tbj - lb)
		Tbj = Tb(Tbj)
		int_result[#int_result + 1] = digit
	end
	if #int_result == 0 then int_result[1] = 0 end
	if math.abs(Tbj) > 0 then
		for i=1,20 do
			local digit = math.floor(b * Tbj - lb)
			Tbj = Tb(Tbj)
			fractional_result[#fractional_result + 1] = digit
			if math.abs(Tbj) <= 0 then break end
		end
	end
	return int_result, fractional_result, sign
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.getPlaceValue(destination_base, i)) % destination_base)
		n = n - digit * utils.getPlaceValue(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.getPlaceValue(destination_base, -i)) % destination_base)
			n = n - digit * utils.getPlaceValue(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.negabaseCarry(int_digits, fractional_digits, destination_base, sign)
	if math.abs(fractional_digits[1]or 0) > 0 and (sign or 0) > 0 then
		int_digits[#int_digits] = int_digits[#int_digits] + 1
	end
	local carry = 0
	local abs_base = utils.round(math.abs(destination_base))
	for i=#fractional_digits,1,-1 do
		local d = utils.round(fractional_digits[i]) + carry
		carry = 0
		if d >= abs_base then
			carry = i%2 and -1 or 1
			d = d - abs_base
		end
		if d < 0 then
			carry = i%2 and 1 or -1
			d = d + abs_base
		end
		fractional_digits[i] = utils.round(d)
	end
	local j = 0
	for i=#int_digits,1,-1 do
		j = #int_digits - i
		local d = utils.round(int_digits[i]) + carry
		carry = 0
		if d >= abs_base then
			carry = j%2 and -1 or 1
			d = d - abs_base
		end
		if d < 0 then
			carry = j%2 and 1 or -1
			d = d + abs_base
		end
		int_digits[i] = utils.round(d)
	end
	while math.abs(carry) > 0 do
		j = j + 1
		local d = utils.round(carry)
		carry = 0
		if d >= abs_base then
			carry = j%2 and -1 or 1
			d = d - abs_base
		end
		if d < 0 then
			carry = j%2 and 1 or -1
			d = d + abs_base
		end
		table.insert(int_digits, 1, utils.round(d))
	end
	for i=1,#int_digits-1 do if int_digits[1] == 0 then table.remove(int_digits, 1) end end
	return int_digits, fractional_digits
end

local function complexBase2Decimal(num, imag, base)
	if type(cmath.constructor) ~= type(tostring) then cmath = require("Module:Complex Number").cmath.init()end
	local base = cmath.constructor(base)
	if not base then return nil end
	num = mw.text.trim(num)
	local sign = 1
	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 type(lib_calc._getNumString) ~= type(tostring) then lib_calc = require('Module:Complex_Number/Calculate')end
	local int_digits, fractional_digits = lib_calc._getNumString(num, true)
	local result = cmath.constructor(utils.toDecimalComplex(int_digits, fractional_digits, imag, base))
	if sign < 0 then result = result * -1 end
	return result
end

function utils.complexBaseConvert(num, to, from, digs, precision)
	if mw.ustring.find(to..' '..from, "[%+%-−%d]i") then
		if type(cmath.constructor) ~= type(tostring) then cmath = require("Module:Complex Number").cmath.init()end
		num = mw.ustring.gsub(num, '−', '-')
		to = mw.ustring.gsub(to, '−', '-')
		from = mw.ustring.gsub(from, '−', '-')
		local cto, cfrom = cmath.constructor(tostring(to)), cmath.constructor(tostring(from))
		cfrom = cfrom or cmath.constructor(10)
		
		if cto and cfrom then
			local number = tostring(num)
			number = mw.text.trim(number)
			--轉換為十進制
			if cmath.abs(cmath.im(cfrom)) < 1e-14 and cmath.abs(cmath.re(cfrom)) > 0 then
				local check_number = num
				if not mw.ustring.find(check_number,"^[%+%-−]") then check_number = '+'..num end
				number = mw.ustring.gsub(check_number, "[%+%-−][%a%d%.,;:]+", function(number_part)
					if type(bignum.convertBase) ~= type(tostring)then bignum = require(main_module)end
					local is_imag = (mw.ustring.sub(number_part,-1,-1) == 'i')
					local convert_number = is_imag and mw.ustring.sub(number_part,1,-2) or number_part
					if convert_number == '' or convert_number == '+' or convert_number == '-' or convert_number == '−' then convert_number = convert_number..'1' end
					convert_number = bignum.convertBase(convert_number, 10, from)..(is_imag and 'i' or '')
					if not mw.ustring.find(convert_number,"^[%+%-−]") then convert_number = '+'..convert_number end
					return mw.ustring.gsub(convert_number, '−', '-')
				end)
			else
				local check_number = num
				if not mw.ustring.find(check_number,"^[%+%-−]") then check_number = '+'..num end
				number = mw.ustring.gsub(check_number, "[%+%-−][%a%d%.,;:]+", function(number_part)
					if type(lib_calc.scientific2number) ~= type(tostring) then lib_calc = require('Module:Complex_Number/Calculate')end
					local is_imag = (mw.ustring.sub(number_part,-1,-1) == 'i')
					local convert_number = is_imag and mw.ustring.sub(number_part,1,-2) or number_part
					convert_number = mw.ustring.gsub(convert_number, '−', '-')
					if convert_number == '' or convert_number == '+' or convert_number == '-' or convert_number == '−' then convert_number = convert_number..'1' end
					convert_number = complexBase2Decimal(convert_number, is_imag, cfrom)
					convert_number = tostring(convert_number)
					--跳脫科學記號，避免加與減和科學記號混淆
					convert_number = mw.ustring.gsub(convert_number, "[Ee]%+?(%d)", "F%1")
					convert_number = mw.ustring.gsub(convert_number, "[Ee]%-(%d)", "D%1")
					if not mw.ustring.find(convert_number,"^[%+%-−]") then convert_number = '+'..convert_number end
					--還原科學記號為一般數字
					convert_number = mw.ustring.gsub(convert_number, "([%+%-−])([%a%d%.,;:]+)", function(number_sign_part,number_value_part)
						local is_part_imag = (mw.ustring.sub(number_value_part,-1,-1) == 'i')
						local number_value_part_real = is_part_imag and mw.ustring.sub(number_value_part,1,-2) or number_value_part
						number_value_part_real = mw.ustring.gsub(number_value_part_real, "[DdFf]", function(Evalue) return ({D='e-',d='e-',F='e+',f='e+'})[Evalue] end)
						return number_sign_part..lib_calc.scientific2number(number_value_part_real, true)..(is_part_imag and 'i' or '')
					end)
					return mw.ustring.gsub(convert_number, '−', '-')
				end)
			end
			number = cmath.constructor(number)
			if not number then
				error(mw.ustring.format("轉換失敗：'%s' 不是有效的數字。",tostring(num)), 2)
				return nil
			end
			local int_digits, fractional_digits = {}, {}
			if cmath.abs(cto) <= 1 then
				return nil
			elseif cmath.abs(cmath.re(cto)) < 1e-14 then
				local to_im = cmath.im(cto)
				local to_im_sq = to_im * to_im
				if to_im_sq > 1 then
					local real, imag = cmath.re(number), cmath.i * cmath.im(number)
					imag = imag * cmath.i * to_im
					local function convert_part(num_val, base, frac_precision)
						local num_str = tostring(num_val)
						local sign = 1
						local first_sign = mw.ustring.sub(num_str,1,1)
						--讀取正負號
						if first_sign == '+' or first_sign == '-' or first_sign == '−' then 
							num_str = mw.ustring.sub(num_str,2,-1)
							if first_sign == '-' or first_sign == '−' then 
								sign = -1 
							end
						end
						if type(lib_calc._getNumString) ~= type(tostring) then lib_calc = require('Module:Complex_Number/Calculate')end
						local int_digits, fractional_digits = lib_calc._getNumString(num_str, true)
						if base < 0 and sign < 0 then
							for i=1,#int_digits do int_digits[i] = -int_digits[i]end
							for i=1,#fractional_digits do fractional_digits[i] = -fractional_digits[i]end
						end
						if utils.isInt(base) then
							int_digits = utils._convertBase(int_digits, 10, base, false)
							fractional_digits = utils._convertBase(fractional_digits, 10, base, true, tonumber(frac_precision<0 and '' or frac_precision))
							if #int_digits == 0 then int_digits[1] = 0 end
							if base < 0 then int_digits, fractional_digits = utils.negabaseCarry(int_digits, fractional_digits, base, sign)end
						else
							int_digits, fractional_digits = utils.real_negabase(int_digits, fractional_digits, 10, base, 1)
						end
						return int_digits, fractional_digits
					end
					local function revert(x)
						rev = {}
						for i=#x, 1, -1 do table.insert(rev, x[i])end
						return rev
					end
					local real_int, real_frac = convert_part(cmath.re(real), -to_im_sq, precision)
					local imag_int, imag_frac = convert_part(cmath.re(imag), -to_im_sq, precision)
					table.insert(imag_frac, 1, imag_int[#imag_int])
					table.remove(imag_int, #imag_int)
					if utils.is_zero(imag_frac) then imag_frac = {} end
					real_int, imag_int = revert(real_int), revert(imag_int)
					for i=1,math.max(#real_int, #imag_int) do
						table.insert(int_digits,1,real_int[i] or 0)
						table.insert(int_digits,1,imag_int[i] or 0)
					end
					if int_digits[1] == 0 then table.remove(int_digits,1) end
					for i=1,math.max(#real_frac, #imag_frac) do
						table.insert(fractional_digits,imag_frac[i] or 0)
						table.insert(fractional_digits,real_frac[i] or 0)
					end
					if fractional_digits[#fractional_digits] == 0 then table.remove(fractional_digits,#fractional_digits) end
				end
			elseif cmath.abs(cmath.re(cto)) >= 1 and cmath.abs(cmath.im(cto)) < 1e-14 then
				local real, imag = cmath.re(number), cmath.im(number)
				if type(bignum.convertBase) ~= type(tostring)then bignum = require(main_module)end
				local real_result, imag_result = bignum.convertBase(real, cmath.re(cto), 10, digs, precision), bignum.convertBase(imag, cmath.re(cto), 10, digs, precision)
				local real_is0, imag_is0 = ((tonumber(real_result)or 1) == 0), ((tonumber(imag_result)or 1) == 0)
				if imag_is0 then return real_result, '' 
				elseif real_is0 and not imag_is0 then return ((math.abs(tonumber(({mw.ustring.gsub(imag_result, '−', '-')})[1]) or 0) ~= 1) and imag_result or ({mw.ustring.gsub(imag_result,'1','')})[1])..'i', ''end
				local check_sign = mw.ustring.sub(imag_result,1,1)
				return real_result .. ((check_sign == '+' or check_sign == '-' or check_sign == '−') and '' or '+') .. ((math.abs(tonumber(({mw.ustring.gsub(imag_result, '−', '-')})[1]) or 0) ~= 1) and imag_result or ({mw.ustring.gsub(imag_result,'1','')})[1]) ..'i', ''
			elseif utils.isInt(cmath.re(cto)) and utils.isInt(cmath.im(cto)) and cmath.abs(cto) > 1 then
				--尚不知道其他高斯整數底數的非整數轉換演算法。部分高斯整數底數無法轉換
				local real, imag = cmath.re(number), cmath.im(number)
				local function complex_div_quotient_remainder(input_number, base)
					local base_real, base_imag = cmath.re(base), cmath.im(base)
					local max_remainder = base_real * base_real + base_imag * base_imag
					for i=0,max_remainder-1 do
						local check_quotient = (input_number-i) / base
						if utils.isInt(cmath.re(check_quotient)) and utils.isInt(cmath.im(check_quotient)) then
							return check_quotient, i
						end
					end
				end
				local int_number = cmath.ceil(number)
				local frac_number = number - int_number
				if cmath.abs(frac_number) > 1e-14 then --阻止非高斯整數進行轉換，因為目前演算法不支援
					error(mw.ustring.format("轉換失敗：底數 '%s' 不支援非高斯整數 '%s' 的轉換。",tostring(to), tostring(num)), 2)
					return nil 
				end
				local tk = (utils.myceil(math.log(cmath.abs(number))/math.log(cmath.abs(cto))) + 1) * 4 + 4
				local do_number = int_number
				local counter = 0
				while cmath.abs(do_number) > 0 do
					local quotient, remainder = complex_div_quotient_remainder(do_number, cto)
					do_number = quotient
					table.insert(int_digits,1,remainder)
					
					counter = counter + 1
					if counter > tk then --轉換到變成無窮迴圈，視為失敗
						error(mw.ustring.format("轉換失敗：無法將 '%s' 轉換為底數 '%s' 的進制。", tostring(num), tostring(to)), 2)
						return nil 
					end
				end
				if #int_digits == 0 then int_digits[1] = 0 end
			else
				return nil 
			end
			local max_digs = 0
			for i=1,#int_digits do if int_digits[i] > max_digs then max_digs = int_digits[i] end end
			for i=1,#fractional_digits do if fractional_digits[i] > max_digs then max_digs = fractional_digits[i] 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
			local int_result, fractional_result = utils.printAllDigit(int_digits, max_digs + 1, -1, 0, false), utils.printAllDigit(fractional_digits, max_digs + 1, precision, 0, true)
			return int_result, fractional_result
		end
	end
	return nil
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 = "!",
		display = "!",
		page = "阶乘进制",
		digitsplit = ":",
		point = ".",
		placeValue = function(this, digit_id) return utils.factorial(digit_id)end,
		baseValue = function(this, digit_id) return (digit_id < 0) and -digit_id or (digit_id + 1) end,
		printDigit = function(this, digit)return tostring(digit) end,
		needtoDecimal = false,
		convertBase = utils._convertBase,
	},
	['#']={
		name = "#",
		display = "#",
		page = "质数阶乘进制",
		digitsplit = ":",
		point = ".",
		placeValue = function(this, digit_id) 
			if not lib_fact.primeIndex then lib_fact = require("Module:Factorization") end
			local result = 1
			for i=1,digit_id do result = result * ((i-1<=0) and 1 or lib_fact.primeIndex(i-1)) end
			if digit_id<0 then for i=1,-digit_id do result = result / ((i-1<=0) and 1 or lib_fact.primeIndex(i-1)) end end
			return result
		end,
		baseValue = function(this, digit_id)
			if not lib_fact.primeIndex then lib_fact = require("Module:Factorization") end
			return (digit_id < 0) and ((-digit_id<=1) and 1 or lib_fact.primeIndex(-digit_id-1)) or ((digit_id<=0) and 1 or lib_fact.primeIndex(digit_id))
		end,
		printDigit = function(this, digit)return tostring(digit) end,
		needtoDecimal = false,
		convertBase = utils._convertBase,
	},
	['!0']={ --以0-9A-Z表達的阶乘进制 (遇到超過36位數可能會出現亂碼)
		name = "!0",
		display = "!",
		page = "阶乘进制",
		digitsplit = "",
		point = ".",
		placeValue = function(this, digit_id) return utils.factorial(digit_id)end,
		baseValue = function(this, digit_id)return (digit_id < 0) and -digit_id or (digit_id + 1) end,
		printDigit = function(this, digit)
			return utils.printAZ(digit)
		end,
		needtoDecimal = false,
		convertBase = utils._convertBase,
	},
	['!-']={ --以0-9A-Z表達的阶乘进制並省略個位數 (遇到超過36位數可能會出現亂碼)
		name = "!-", --[[oeis:A007623]]
		display = "!",
		page = "阶乘进制",
		digitsplit = "",
		point = ".",
		placeValue = function(this, digit_id) return utils.factorial((digit_id < 0) and digit_id or (digit_id + 1))end,
		baseValue = function(this, digit_id)return (digit_id < 0) and -digit_id or (digit_id + 2) end,
		printDigit = function(this, digit)
			return utils.printAZ(digit)
		end,
		needtoDecimal = false,
		convertBase = utils._convertBase,
	},
	fib={
		name = "fib",
		display = "fib",
		page = "斐波那契进制",
		digitsplit = "",
		point = ".",
		placeValue = function(this, an)
			local sqrt5 = math.sqrt(5)
			local phi = (sqrt5 + 1) * 0.5
			local fib_val = math.floor(math.pow(phi, math.abs(an)+((an < 0) and 2 or 1)) / sqrt5 + 0.5)
			return (an < 0) and (1/fib_val) or fib_val
		end,
		baseValue = function(this, digit_id)return 1 end,
		printDigit = function(this, digit)return tostring(digit) end,
		needtoDecimal = true,
		convertBase = utils.fibonacci_coding,
	},
	["fib-"]={
		name = "fib-",
		display = "fib",
		page = "斐波那契进制",
		digitsplit = "",
		point = ".",
		placeValue = function(this, an)
			local sqrt5 = math.sqrt(5)
			local phi = (sqrt5 + 1) * 0.5
			local fib_val = math.floor(math.pow(phi, math.abs(an)+2) / sqrt5 + 0.5)
			return (an < 0) and (1/fib_val) or fib_val
		end,
		baseValue = function(this, digit_id)return 1 end,
		printDigit = function(this, digit)return tostring(digit) end,
		needtoDecimal = true,
		convertBase = function(int_digits, original_base, _destination_base, fractional_flag, total_digit)
			local result = utils.fibonacci_coding(int_digits, original_base, _destination_base, fractional_flag, total_digit)
			if fractional_flag then return result end
			table.remove(result,#result)
			return result
		end,
	},
	fibcode={
		name = "fibcode",
		display = "fib code",
		page = "斐波那契编码",
		digitsplit = "",
		point = ".",
		placeValue = function(this, an)
			local sqrt5 = math.sqrt(5)
			local phi = (sqrt5 + 1) * 0.5
			return math.floor(math.pow(phi, an+1) / sqrt5 + 0.5)
		end,
		baseValue = function(this, digit_id)return 1 end,
		printDigit = function(this, digit)return tostring(digit) end,
		needtoDecimal = true,
		convertBase = function(int_digits, original_base, _destination_base, fractional_flag, total_digit)
			return utils.fibonacci_coding(int_digits, original_base, _destination_base, fractional_flag, total_digit, true)
		end,
	},
	ContinuedFraction={
		name = "ContinuedFraction",
		display = "ContinuedFraction",
		page = "连分数",
		digitsplit = ",",
		point = ";",
		placeValue = function(this, an)return 1 end,
		baseValue = function(this, digit_id)return 1 end,
		printDigit = function(this, digit)return tostring(digit) end,
		needtoDecimal = true,
		convertBase = utils.ContinuedFraction,
	},
}
utils.specialBaseData['！'] = utils.specialBaseData['!']
utils.specialBaseData['阶乘'] = utils.specialBaseData['!']
utils.specialBaseData['阶乘进制'] = utils.specialBaseData['!']
utils.specialBaseData['階乘'] = utils.specialBaseData['!']
utils.specialBaseData['階乘進制'] = utils.specialBaseData['!']
utils.specialBaseData['階乘進位'] = utils.specialBaseData['!']
utils.specialBaseData['斐波那契进制'] = utils.specialBaseData.fib
utils.specialBaseData['斐波那契進制'] = utils.specialBaseData.fib
utils.specialBaseData['斐波那契编码'] = utils.specialBaseData.fibcode
utils.specialBaseData['斐波那契編碼'] = utils.specialBaseData.fibcode
utils.specialBaseData['fib code'] = utils.specialBaseData.fibcode
utils.specialBaseData['斐波那契'] = utils.specialBaseData.fib
utils.specialBaseData['連分數'] = utils.specialBaseData.ContinuedFraction
utils.specialBaseData['连分数'] = utils.specialBaseData.ContinuedFraction
utils.specialBaseData['continued fraction'] = utils.specialBaseData.ContinuedFraction
utils.specialBaseData['Continued Fraction'] = utils.specialBaseData.ContinuedFraction

function utils.getPlaceValue(base, digit_id)
	local special_base_data = utils.getSpecialBase(base)
	if special_base_data then
		return special_base_data:placeValue(digit_id)
	else
		return math.pow(base, digit_id)
	end
end

function utils.getBaseValue(base, digit_id)
	local special_base_data = utils.getSpecialBase(base)
	if special_base_data then
		return special_base_data:baseValue(digit_id)
	else
		return base
	end
end

function utils.getSpecialBase(base)
	local base_string = mw.text.trim(tostring(base))
	if utils.isNaN(base) then error(string.format("底數不能為 '%s'", base_string),2) end
	local num_base = utils.tonumber(base_string)
	if num_base then return nil end
	local special_base_data = utils.specialBaseData[base]
	if special_base_data then return special_base_data end
	if mw.ustring.find(base_string, '[,;]') then
		local point, split = '.', ''
		local point_loaded = false
		base_string = mw.ustring.gsub(base_string, ' +', '')
		local base_name = base_string
		local az_digits = false
		if not mw.ustring.match(mw.ustring.sub(base_string, -2),'[%d∞]+') then
			split = mw.ustring.sub(base_string, -2, -2)
			point = mw.ustring.sub(base_string, -1, -1)
			base_name = mw.ustring.sub(base_string, 1, -3)
			if split == point and split == '.' then
				split = ''
				az_digits = true
			end
			point_loaded = true
		end
		local int_frac, int_base = mw.text.split(base_name..';', ';')
		int_base = mw.text.split(int_frac[1], ',')
		local int_base_count = #int_base
		local load_bases = mw.text.split(base_name, '[,;]')
		local bases, frac_bases = {}, {}
		local max_base = 0
		local repeat_base = false
		for i=1,#load_bases do
			local unit_base = utils.tonumber(load_bases[i])
			if not unit_base then return nil end
			if (i > 1 and unit_base == 0) or unit_base < 0 or (not utils.isInf(unit_base) and not utils.isInt(unit_base)) then return nil, string.format("不支援非正整數的混合底數 '%s' 進制", base_name) end
			if math.abs(unit_base) > 36 and not point_loaded then
				point, split = ';', ','
			end
			if unit_base > max_base then max_base = unit_base end
			if i==1 and math.abs(unit_base) < 1e-14 then
				repeat_base = true
			else
				if i > int_base_count then
					frac_bases[#frac_bases + 1] = unit_base
				else
					table.insert(bases, 1, unit_base)
				end
			end
		end
		if #bases <= 0 then bases[1] = frac_bases[1]end
		if #frac_bases <= 0 then
			frac_bases = mw.clone(bases)
			if repeat_base and #frac_bases > 1 then 
				frac_bases[#frac_bases + 1] = frac_bases[1]
				table.remove(frac_bases, 1)
			end
		end
		local new_base_data = {
			name = base_string,
			display = base_name,
			page = "混合进制",
			digitsplit = split,
			point = point,
			base_list = bases,
			frac_base_list = frac_bases,
			max_base = max_base,
			repeat_base = repeat_base,
			point_loaded = point_loaded,
			az_digits = az_digits,
			placeValue = function(this, digit_id)
				local result = 1
				for i=1,math.abs(digit_id) do
					local using_list = digit_id < 0 and this.frac_base_list or this.base_list
					local doing_index = this.repeat_base and utils.loop_mod(i, #using_list) or i
					result = result * (using_list[doing_index] or using_list[#using_list] or 10)
				end
				return digit_id < 0 and (1/result) or result
			end,
			baseValue = function(this, digit_id)
				return (digit_id < 0)
					and (this.frac_base_list[this.repeat_base and utils.loop_mod(-digit_id, #(this.frac_base_list)) or (-digit_id)] or this.frac_base_list[#(this.frac_base_list)] or 10) 
					or (this.base_list[this.repeat_base and utils.loop_mod(digit_id + 1, #(this.base_list)) or (digit_id + 1)] or this.base_list[#(this.base_list)] or 10) 
			end,
			printDigit = function(this, digit)
				if (this.point_loaded or (math.abs(max_base) > 36)) and (not this.az_digits) then
					return utils.tostring(digit)
				else
					return utils.printAZ(digit)
				end
			end,
			needtoDecimal = false,
			convertBase = utils._convertBase,
		}
		return new_base_data
	end
	return nil
end

function utils.checkSpecialBase(base)
	local base_string = mw.text.trim(tostring(base))
	if utils.isNaN(base) then error(string.format("底數不能為 '%s'", base_string),2) end
	local num_base = utils.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
	if mw.ustring.find(base_string, '[,;]') then
		base_string = mw.ustring.gsub(base_string, ' +', '')
		local check_string = base_string
		if not mw.ustring.match(mw.ustring.sub(check_string, -2),'[%d∞]+') then
			check_string = mw.ustring.sub(check_string, 1, -3)
		end
		local load_bases = mw.text.split(check_string, '[,;]')
		for i=1,#load_bases do 
			local check_number = utils.tonumber(load_bases[i])
			if not check_number then return nil end
			if (i > 1 and check_number == 0) or check_number < 0 or (not utils.isInf(unit_base) and not utils.isInt(check_number)) then return nil end
		end
		return base_string
	end
	return nil
end

function utils.printAZ(digit)
	local char_0 = mw.ustring.codepoint('0')
	local char_A = mw.ustring.codepoint('A') - 10
	local char_a = mw.ustring.codepoint('a') - 36
	local char_100 = mw.ustring.codepoint('¡') - 62
	local codepoint = digit + ((digit >= 10) and ((digit >= 36) and ((digit >= 62) and char_100 or char_a) or char_A) or char_0)
	return mw.ustring.char(codepoint)
end

function utils.print_digit(digit, base)
	local digit = utils.round(digit)
	local special_base_data = utils.getSpecialBase(base)
	if special_base_data then
		return special_base_data:printDigit(digit)
	elseif math.abs(tonumber(base)or 10) <= 36 then
		return utils.printAZ(digit)
	else
		return tostring(digit)
	end
end

function utils.printAllDigit(digits, base, precision, _subarg, fractional_flag)
	local subarg = tonumber(_subarg) or 0
	local special_base_data = utils.getSpecialBase(base)
	local result, digitcomma = '', ''
	if special_base_data then
		digitcomma = special_base_data.digitsplit
	elseif math.abs(tonumber(base) or 10) > 36 then
		digitcomma = ','
	end
	for i=1,#digits do
		if precision >= 0 and i == precision + 1 then break end
		if subarg < 6 then
			if result ~= '' then result = result .. digitcomma end
		end
		result = result .. utils.print_digit(digits[i], base)
		if subarg >= 6 and subarg < 12 then
			result = string.format("%s<sub>%s</sub>", result, 
				utils.tostring(special_base_data and special_base_data:baseValue(fractional_flag and -i or (#digits-i)) or base)
			)
		elseif subarg >= 12 and subarg < 18 then
			result = string.format("%s<sub>%s</sub>", result, 
				utils.tostring(((not fractional_flag) and (#digits-i == 0)) and ((tostring(base):sub(1,1)=='!')and 0 or 1)
				or (special_base_data and special_base_data:baseValue(fractional_flag and -i or (#digits-i-1))) or base)
			)
		end
	end
	return result
end

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

function utils.toDecimalComplex(int_digits, fractional_digits, imag, base)
	if type(cmath.constructor) ~= type(tostring) then cmath = require("Module:Complex Number").cmath.init()end
	base = cmath.constructor(base)
	if not base then return nil end
	local n = cmath.constructor(int_digits[#int_digits])
	local j = 1
	for i = #int_digits-1, 1, -1 do
		n = n + int_digits[i] * utils.cintpow(base, j)
		j = j + 1
	end
	for i = 1, #fractional_digits do
		n = n + fractional_digits[i] * utils.cintpow(base, -i)
	end
	n = (imag and cmath.i or cmath[1]) * n
	n:clean()
	return n
end

function utils.print_base_string(int_result, fractional_result, ori_int_digits, ori_fractional_digits, sign, from, to, _subarg, prefix, suffix)
	local subarg = tonumber(_subarg) or 0
	local special_base_data_from = utils.getSpecialBase(from)
	local special_base_data_to = utils.getSpecialBase(to)
	local point_string = (math.abs(tonumber(to) or 10) > 36) and ';' or ((special_base_data_to or{}).point or '.')
	if tostring(to):sub(-1,-1) == 'i' and (int_result:find(',') or (fractional_result or''):find(',')) then point_string = ';'end
	local number_result = ((sign < 0) and '−' or '') .. (int_result == '' and '0' or int_result) .. (fractional_result == '' and '' or (point_string..fractional_result))
	local result = (prefix or '') .. number_result .. (suffix or '') 
	if subarg % 6 == 1 then
		result = string.format("%s<sub>(%s)</sub>", result, utils.tostring((special_base_data_to or{}).display or to))
	elseif subarg % 6 == 2 then
		result = string.format("(%s)<sub>%s</sub>", result, utils.tostring((special_base_data_to or{}).display or to))
	elseif subarg % 6 == 3 or subarg % 6 == 5 then
		local lib_num2zh = require('Module:NumberToChinese')
		local success, num = pcall(utils.toDecimal, ori_int_digits, ori_fractional_digits, from)
		if not success then
			--轉換失敗時
			if type(bignum.convertBase) ~= type(tostring)then bignum = require(main_module)end
			if tonumber(to) then
				num = (tonumber(to) == 10) and number_result or "數字" --不支援的部分
			else
				success, num = pcall(bignum.convertBase, number_result, 10, to)
				if not success then num = "數字" end --不支援的部分
			end
		end
		local base_name = lib_num2zh._numberToChinese(utils.tostring(to))
		if base_name == lib_num2zh.NotANumber() then base_name = utils.tostring(to) end
		result = mw.ustring.format("[[%s|%s]]<sub>[[%s|%s%s%s]]</sub>", 
			utils.tostring(num), result,
			special_base_data_to and (special_base_data_to.page) or (base_name..'進制'), 
			(subarg % 6 == 5) and '' or '(',
			utils.tostring((special_base_data_to or{}).display or to),
			(subarg % 6 == 5) and '' or ')')
	elseif subarg % 6 == 4 then
		result = string.format("%s<sub>%s</sub>", result, utils.tostring((special_base_data_to or{}).display or to))
	end
	return result
end

return utils