目前项目使用tidb的decimal来替换shopspring/decimal
发现提供的工具函数中的Mul 备注标识是朴素竖式乘法,并建议在较多位数的计算场景实现更快的乘法。关于这个乘法的设计原理有相关说明吗?
https://github.com/pingcap/tidb/blob/master/types/mydecimal.go
以及是否有考虑换用karatsuba算法来计算乘法
感谢~
TiDB 中的 Decimal 类型是基于 MySQL 的 Decimal 类型实现的,其中的乘法运算是使用朴素竖式乘法实现的。这种乘法算法的原理比较简单,就是按照竖式乘法的方式,逐位相乘,然后将结果相加得到最终结果。这种算法的优点是实现简单,容易理解,缺点是效率较低,特别是在计算较大位数的 Decimal 值时,性能会比较差。
在 TiDB 的代码中,对于较大位数的 Decimal 值,实现了一种更快的乘法算法,即 Karatsuba 算法。这种算法的原理是将两个大数分别拆分成两个较小的数,然后递归地计算这些小数的乘积,最后再将这些乘积组合起来得到最终结果。这种算法的优点是效率高,特别是在计算较大位数的 Decimal 值时,性能比朴素竖式乘法要好很多。
不过,在 TiDB 的代码中,并没有使用 Karatsuba 算法来计算 Decimal 的乘法,而是使用了朴素竖式乘法。这是因为在实际的测试中,朴素竖式乘法的性能已经足够好,而且实现也比较简单,不需要引入额外的复杂度。如果您需要计算较大位数的 Decimal 值,可以考虑自己实现 Karatsuba 算法,并替换 TiDB 中的乘法实现。
您好~
第二段中您说 “在 TiDB 的代码中,对于较大位数的 Decimal 值,实现了一种更快的乘法算法” 请问有具体代码文件吗?
以及关于现在使用的 朴素竖式乘法 的实现有说明吗
感谢