Lua大整数的实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› LUA›LUA教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

大整数

程序中基础的数据类型，如double、int64_t之类的，其大小都是有上限的，假如有一个数10000000000...(后面接10000个0)，那么现在的数据类型是表示不了的，这时候就需要可以无限增长的整数，即大整数。作为一个游戏开发的程序员，我怎么也没想到需要用到大整数。虽然这几年游戏的数值比之前大幅提升（小时候玩的游戏，攻击、防御这些基本都是三位数以下，现在轻松达到十几亿），但是用个64位的类型还是可以应付的。然而策划脑洞大开，要求游戏中的货币上限提高到10000个数字大小。

实现

一开始，我并没有觉得这个事情有多麻烦，毕竟一个int类型表示不了，我就用两个，两个表示不了，我就用三个。。。这样就用一个int数组实现了一个大整数，用模拟竖式运算，简单实现了加减法。竖式运算即平时我们手工运算时用的方式

   99           198
+  99         -  32
------        ------
  198           166

由于我用的是int数组，当然是不会涉及到每一个数字的加减（也没有必要），只是模拟了这种方式的进位和退位，例如加法的lua实现(仅示例，没处理异常和边界)

local bigint = {0}

-- 实现大整数和一个普通数字相加
local function add(bigint, num)
    bigint[1] = bigint[1] + num

    -- 数组中每个数字最大为uint32上限，超过即向数组前一位进位
    local i = 1
    while bigint[i] > 0xFFFFFFFF do
        bigint[i] = bigint[i] - 0xFFFFFFFF
        bigint[i +1] = 1 + (bigint[i +1] or 0)

        i = i + 1
    end
end

不过当我实现了加减法后，棘手的事来了，乘法、除法怎么实现？怎么转换为10进制字符串？我一开始并没有想到要实现这些功能，但是随着开发的推进，策划的需求里需要计算货币N倍加成，调试时需要输出10进制字符串，这显然超出我的知识范畴了。乘除法虽然用得多，但如果需要我去实现，这个我还真不知道是如何实现的，只得硬着头皮查资料学习。所幸kedixa的博客里有比较详细的C++实现，也有示例代码，最终顺利地在lua实现了大整数的四则运算及10进制字符串转换。

到这里，本来就结束了，然而后期在使用这个大整数的时候，偶尔会出现10进制字符串转换、乘除法运算出错的问题。仔细排查后，没有发现算法的实现问题，而且只有数字比较大的时候才能重现，不得不把kedixa的C++版本拿下来交叉对比，最终发现是lua 5.3的一些实现和C++是有区别的，比如-2251624706 >> 32 在C++中是-1，在lua中是4294967295，而C++中两个整数相除，直接得到一个整数，而lua只能用math.floor来转换，math.floor(253923710799999577 / 100000000) = 2539237107 偶尔返回2539237108，最终不得不把一部分算法实现放到C++去。

另一个严重的问题是性能非常不理想。在数字非常大时（10000个10进制字符串），每秒只能运算1000次不到。转换为10进制字符串更是需要数秒，原因是lua中的字符串是immutable的，每一次拼接字符串都需要产生一个新的字符串，而10000个10进制字符串就需要拼接10000次，这个完全无法接受。

之所以用lua实现，是因为游戏服务器业务逻辑都是用lua实现的，一开始并不想给大整数开这个特例。竟然没法满足需求，就不得不寻找替代方案。

其他实现方案

faheel
std::string保存10进制字符串的实现，即数字123456在内部实现里就是保存为字符串123456，可以预估这种实现的运算会比较慢，而且占用内存比较大，最大的优点是不需要转换成10进制字符串。不过这个实现居然是github上搜索big int结果中C++实现得星最多的，实在出乎我的意料。毕竟一开始我没查任何资料，第一想到的方案是用int数组来实现。
kasparsklavins
std::vector<int>保存10进制数字的实现，即数字123456在内部实现里就是用一个数字分别保存了1、2、3、4、5、6这几个数字，其实和上面的实现差不多。这个库并没有实现除法，我把它单独拿出来对比是因为它的实现数据结构和其他的不一样。
kedixa
std::vector<uint32_t>按位保存的实现，即上面数组中一个数字满0xFFFFFFFF即向前进1的实现，这是我认为比较正常的一个实现。
boost
没错，这个就是大名鼎鼎的boost库的实现，其内部实现其实和kedixa差不多，不过默认使用的是std::vector<uint64>，编译时可配置

// cpp_int_config.hpp line 63
typedef detail::largest_unsigned_type<64>::type limb_type;

gmp
GMP是The GNU Multiple Precision Arithmetic Library的简称，由GNU维护，号称Arithmetic without limitations。这个库原本为科学研究设计的，包含大整数、大有理数、大浮点数三个库，并且对性能进行了极致的优化，采用了大量的汇编和特定的CPU指令。不过也正因为如此，这个库的要移植到win下是比较有难度的，因为其中很大一部分是汇编实现的，并且编译这个库的时候，会检测CPU的类型，根据不同的CPU指令集采用不同的汇编。而且其开源协议是GNU LGPL v3和GNU GPL v2，不太适合商用。

针对这些库，我做了一些简单的测试，其中循环10次的测试结果如下

optimize=O2 TIMES=10

# make libperf
g++ -std=c++11 -I../boost_1_74_0 -Wall -g3 -O2 -o test_lib_perf \
        ./lib_perf/kedixa/unsigned_bigint.cpp \
        ./lib_perf/kasparsklavins/bigint.cpp \
        ./lib_perf/lib_perf.cpp \
        -lgmpxx -lgmp
./test_lib_perf
faheel create time elapsed 98us
faheel add time elapsed 38256us
faheel dec time elapsed 43456us
faheel mul time elapsed 12309486us
faheel div time elapsed 191761534us
faheel to_string time elapsed 96us
kasparsklavins create time elapsed 232us
kasparsklavins add time elapsed 325us
kasparsklavins dec time elapsed 119us
kasparsklavins mul time elapsed 71310us
kasparsklavins to_string time elapsed 2100us
kedixa create time elapsed 5383us
kedixa add time elapsed 8us
kedixa dec time elapsed 11us
kedixa mul time elapsed 6604us
kedixa div time elapsed 6813us
kedixa to_string time elapsed 14514us
boost create time elapsed 1914us
boost add time elapsed 203us
boost dec time elapsed 12us
boost mul time elapsed 2625us
boost div time elapsed 10304us
boost to_string time elapsed 137713us
gmp create time elapsed 909us
gmp add time elapsed 9us
gmp dec time elapsed 6us
gmp mul time elapsed 1294us
gmp div time elapsed 1176us
gmp to_string time elapsed 1564us
test done, TIMES = 10, BASE BIT = 10000, MUL BIT = 1000

可以看到，前两个库的效率相当差，都不在一个量级的，甚至在循环1000次的测试中，faheel因耗时太长无法完成测试。kedixa和boost接近，毕竟实现方式基本一致。而采用了汇编和CPU指令优化的gmp一骑绝尘，性能比boost都要高出一个数量级。

最终，在考虑了代码质量、性能、可移植性后，我基于boost写了一个lua库，编译后可直接在lua使用。