看代码吧
local table_concat = table.concat
local table_insert = table.insert
local string_rep = string.rep
SIGN_MINUS = "+" -- 正数
SIGN_PLUS = "-" -- 负数
NUM_FUL = 10 -- math.pow(10, 8)
NUM_MAX = NUM_FUL-1
NUM_MIN = -NUM_MAX
NUM_MAX_LEN = #tostring(NUM_MAX)
M = {}
--------------------------------------------------------
uuid = 1
function get_uuid()
uuid = uuid + 1
return uuid
end
function digitsIntToString(int, len_max)
-- 补0
len_max = len_max or NUM_MAX_LEN
local s = tostring(int)
local zero_number = len_max - #s
local s_zero = string_rep("0", zero_number)
return table_concat({ s_zero, s })
end
function getBigNumber(n, bSafe)
bSafe = bSafe or true
if isBigNumber(n) then
if bSafe then
return n:copy()
end
else
return M:create(n)
end
end
function isBigNumber(n)
if type(n) == "table" and getmetatable(n) == M then
return true
end
return false
end
function digitsUp(digits)
-- 保证进位正常
local size = #digits
for i=1, size do
if digits[i] > NUM_MAX then
digits[i] = digits[i] - NUM_MAX - 1
if not digits[i + 1] then
digits[i + 1] = 0
end
digits[i + 1] = digits[i + 1] + 1
end
end
end
--------------------------------------------------------
function div(a_in, b_in)
-- 计算结果、余数
-- 默认步长10
assert(b ~= 0, "ERROR: 0不能作为除数")
local sign
if a_in:getSign() == b_in:getSign() then
sign = SIGN_MINUS
else
sign = SIGN_PLUS
end
local a = M.createBySignDigits(SIGN_MINUS, a_in:getDigits())
local b = M.createBySignDigits(SIGN_MINUS, b_in:getDigits())
if a == 0 then
return 0, 0
end
if b == 1 then
return a, 0
end
if a < b then
return 0, a
end
--if a == b then
-- return 1, 0
--end
local function calc(a, b)
assert(b ~= 0, "ERROR: 0不能作为除数")
assert(a >= b, "ERROR:被除数不小于除数")
a = getBigNumber(a)
b = getBigNumber(b)
local factor = M:create(1) -- 倍率
for i = 1, #a._digits - #b._digits - 1 do
table_insert(b._digits, 1, 0)
table_insert(factor._digits, 1, 0)
end
if #a._digits ~= #b._digits then
local b_copy = b:copy()
table_insert(b_copy._digits, 1, 0)
if a > b_copy then
b = b_copy
table_insert(factor._digits, 1, 0)
end
end
local time = 0 -- 次数
while a >= b do
a = a - b
time = time + 1
end
factor._digits[#factor._digits] = factor._digits[#factor._digits] * time
return M.createBySignDigits(SIGN_MINUS, factor:getDigits()), M.createBySignDigits(SIGN_MINUS, a:getDigits())
end
local q = 0
local f
local a_new
while a >= b do
f, a_new = calc(a, b)
q = q + f
a = a_new
end
-- 负数除法的特殊处理(-3/2 ~= -(3/2))
if sign == SIGN_PLUS and not a:isZero() then
q = q + 1
end
q._sign = sign
return q, a
end
function M.__add(a_in, b_in)
local a = getBigNumber(a_in)
local b = getBigNumber(b_in)
local sign
local digits
local a_sign = a:getSign()
local b_sign = b:getSign()
local a_digits = a:getDigits()
local b_digits = b:getDigits()
local a_size = #a_digits
local b_size = #b_digits
local max_size = a_size > b_size and a_size or b_size
if a_sign == b_sign then
digits = {}
local sum, a_int, b_int, c_int
for i = 1, max_size do
a_int = a_digits[i] or 0
b_int = b_digits[i] or 0
c_int = digits[i] or 0
sum = a_int + b_int + c_int
if sum > NUM_MAX then
digits[i] = sum - NUM_MAX - 1
digits[i + 1] = 1
else
digits[i] = sum
end
end
sign = a_sign
else
digits = {}
local sum, a_int, b_int, c_int
if a_size > b_size then
for i = 1, a_size do
a_int = a_digits[i]
b_int = b_digits[i] or 0
if a_int >= b_int then
digits[i] = a_int - b_int
else
local flag = true
for ii = i + 1, a_size do
if flag then
if a_digits[ii] == 0 then
a_digits[ii] = NUM_MAX
else
a_digits[ii] = a_digits[ii] - 1
flag = false
end
end
end
if flag then
print("error 403")
return
end
digits[i] = a_int - b_int + NUM_MAX + 1
end
end
sign = a_sign
elseif a_size < b_size then
for i = 1, b_size do
b_int = b_digits[i]
a_int = a_digits[i] or 0
if b_int >= a_int then
digits[i] = b_int - a_int
else
local flag = true
for ii = i + 1, b_size do
if flag then
if b_digits[ii] == 0 then
b_digits[ii] = NUM_MAX
else
b_digits[ii] = b_digits[ii] - 1
flag = false
end
end
end
if flag then
print("error 403")
return
end
digits[i] = b_int - a_int + NUM_MAX + 1
end
end
sign = b_sign
else
local is_a_can = true
for i = 1, a_size do
a_int = a_digits[i]
b_int = b_digits[i]
if a_int >= b_int then
digits[i] = a_int - b_int
else
local success = false
for ii = i + 1, a_size do
if a_digits[ii] == 0 then
a_digits[ii] = NUM_MAX
else
a_digits[ii] = a_digits[ii] - 1
success = true
break
end
end
if success then
digits[i] = a_int - b_int + NUM_MAX + 1
else
is_a_can = false
break
end
end
end
if is_a_can then
sign = a_sign
else
digits = {}
local a = getBigNumber(a_in)
local a_digits = a:getDigits()
for i = 1, b_size do
b_int = b_digits[i]
a_int = a_digits[i] or 0
if b_int >= a_int then
digits[i] = b_int - a_int
else
local flag = true
for ii = i + 1, b_size do
if flag then
if b_digits[ii] == 0 then
b_digits[ii] = NUM_MAX
else
b_digits[ii] = b_digits[ii] - 1
flag = false
end
end
end
if flag then
print("error 404")
return
end
digits[i] = b_int - a_int + NUM_MAX + 1
end
end
sign = b_sign
end
end
end
return M.createBySignDigits(sign, digits)
end
function M.__sub(a, b)
return getBigNumber(a) + (-getBigNumber(b))
end
function M.__mul(a, b)
local a = getBigNumber(a)
local b = getBigNumber(b)
local a_digits = a:getDigits()
local b_digits = b:getDigits()
local a_sign = a:getSign()
local b_sign = b:getSign()
local a_size = #a_digits
local b_size = #b_digits
local int_mul
local str_mul
local height_mul
local cur_mul
local sign
local digits = {}
if a_sign == b_sign then
sign = SIGN_MINUS
else
sign = SIGN_PLUS
end
for i=1, a_size + b_size do
digits[i] = 0
end
for i = 1, a_size do
for j = 1, b_size do
int_mul = a_digits[i] * b_digits[j]
if int_mul >= NUM_FUL then
height_mul = math.floor(int_mul / NUM_FUL)
cur_mul = int_mul % NUM_FUL
else
cur_mul = int_mul
height_mul = 0
end
digits[i + j - 1] = digits[i + j - 1] + cur_mul
digitsUp(digits)
digits[i + j] = digits[i + j] + height_mul
digitsUp(digits)
end
end
return M.createBySignDigits(sign, digits)
end
function M.__div(a, b)
local m, n = div(a, b)
return m
end
function M.__mod(a, b)
local m, n = div(a, b)
return n
end
function M.__pow(a, b)
end
function M.__unm(o)
o = getBigNumber(o)
if o._sign == SIGN_MINUS then
o._sign = SIGN_PLUS
else
o._sign = SIGN_MINUS
end
return o
end
function M.__idiv(o)
end
function M.__band(o)
end
function M.__bor(o)
end
function M.__bxor(o)
end
function M.__bno(o)
end
function M.__shl(o)
end
function M.__shr(o)
end
function M.__concat(o)
end
function M.__len(o)
local digits_len = 0
local sign_len = 0
local digits = o:getDigits()
local i = #digitsl
if i == 0 then
digits_len = 0
elseif i == 1 then
digits_len = #tostring(digits[1])
elseif i > 1 then
digits_len = (i - 1) * NUM_MAX_LEN + #tostring(digits[i])
else
return -1
end
if o:getSign() == SIGN_PLUS then
sign_len = 1
end
return sign_len + digits_len
end
function M.__eq(a, b)
a = getBigNumber(a)
b = getBigNumber(b)
return a:getSign() == b:getSign() and #a:getDigits() == #b:getDigits() and tostring(a) == tostring(b)
end
function M.__lt(a, b)
a = getBigNumber(a)
b = getBigNumber(b)
local a_sign = a:getSign()
local b_sign = b:getSign()
-- 优化与0比较
local a_isZero = a:isZero()
local b_isZero = b:isZero()
if a_isZero or b_isZero then
if not a_isZero then
return a_sign == SIGN_PLUS
elseif not b_isZero then
return b_sign == SIGN_MINUS
else
return false
end
end
-- 优化与0比较
if a_sign ~= b_sign then
if a_sign == SIGN_PLUS then
return true
else
return false
end
else
if a_sign == SIGN_MINUS then
local c = a - b
if c:isZero() then
return false
end
if c:getSign() == SIGN_PLUS then
return true
else
return false
end
else
local c = (-a) - (-b)
if c:isZero() then
return false
end
if c:getSign() == SIGN_MINUS then
return true
else
return false
end
end
end
end
function M.__le(a, b)
a = getBigNumber(a)
b = getBigNumber(b)
local a_sign = a:getSign()
local b_sign = b:getSign()
-- 优化与0比较
local a_isZero = a:isZero()
local b_isZero = b:isZero()
if a_isZero or b_isZero then
if not a_isZero then
return a_sign == SIGN_PLUS
elseif not b_isZero then
return b_sign == SIGN_MINUS
else
return true
end
end
-- 优化与0比较
if a_sign ~= b_sign then
if a_sign == SIGN_PLUS then
return true
else
return false
end
else
if a_sign == SIGN_MINUS then
local c = a - b
if c:isZero() then
return true
end
if c:getSign() == SIGN_PLUS then
return true
else
return false
end
else
local c = (-a) - (-b)
if c:isZero() then
return true
end
if c:getSign() == SIGN_MINUS then
return true
else
return false
end
end
end
end
function M.__tostring(o)
if o == nil then
return "object is nil"
end
if not o._sign then
return "object is no sign"
end
if not o._digits then
return "object is no digits"
end
if o:isZero() then
return "0"
end
local result
if o._sign == SIGN_PLUS then
result = { "-", }
else
result = { "", }
end
for k, v in pairs(o._digits) do
if k == #o._digits then
table_insert(result, 2, tostring(v))
else
table_insert(result, 2, digitsIntToString(v))
end
end
return table_concat(result)
end
function M:_setString(n)
n = tostring(n)
if n:sub(1, 1) == "-" then
self._sign = SIGN_PLUS
n = n:sub(2)
elseif n:sub(1, 1) == "+" then
self._sign = SIGN_MINUS
n = n:sub(2)
else
self._sign = SIGN_MINUS
end
n = n:gsub("^0*", "")
local str;
local int;
self._digits = {}
for index = 1, #n, NUM_MAX_LEN do
str = n:sub(-index - NUM_MAX_LEN + 1, -index)
int = tonumber(str)
table_insert(self._digits, int)
end
if #self._digits == 0 then
table_insert(self._digits, 0)
end
end
function M._checkValid(n)
if not (type(n) == "number" or type(n) == "string") then
print("暂时不支持此类型参数", type(n))
return
end
n = tostring(n)
if string.match(n, " ") then
print("_checkValid error 400", n)
return
end
local tmp = n:gsub("-?+?%.?", "")
if string.match(tmp, "%D") then
print("_checkValid error 401", n)
return
end
n = n:gsub("%.%d*", "")
if n == "" then
print("_checkValid error 402", n)
return
end
return true
end
function M.createBySignDigits(sign, digits)
local o = M:create(0)
o._sign = sign or SIGN_MINUS
digits = digits or {}
local function getDigitsSize(d)
local k
for i = 1, #d do
k = #d - i + 1
if d[k] ~= 0 then
return k
end
end
return 0
end
local size = getDigitsSize(digits)
for i = 1, size do
o._digits[i] = digits[i]
end
return o
end
function M:isZero()
if #self._digits == 0 then
return true
end
local zero = true
for k, v in pairs(self._digits) do
if v ~= 0 then
zero = false
end
end
return zero
end
function M:getSign()
return self._sign
end
function M:getDigits()
return self._digits
end
function M:copy()
return M.createBySignDigits(self._sign, self._digits)
end
function M:create (n)
if self ~= M or n == nil then
return nil
end
if isBigNumber(n) then
return n:copy()
end
if not self._checkValid(n) then
return nil
end
local o = {}
setmetatable(o, self)
self.__index = self
self._ori_number = n
self._id = get_uuid()
o:_setString(n)
return o
end
CBigInt = M