为了乐趣而优化一个大整数库

主要观点:作者在学习大整数(bignum)的工作原理,先实现了一个任意精度数字库,后对数字存储方式进行改进,提高乘法算法效率并进行基准测试,还介绍了更快的乘法算法(Karatsuba 算法)及测试结果,最后提出若继续该项目将专注于增加实用性。
关键信息

  • 用字符串表示数字,逐位进行加法和乘法运算。
  • 优化数字存储方式,使用 30 位数字可更高效利用内存,减少运算步骤。
  • 实现 30 位数字的加法和乘法函数,加法逐位进行,乘法通过多个循环计算。
  • 基准测试显示,使用 30 位数字进行加法比原 base-10 数字快 83%,乘法快 99%;Karatsuba 算法在 10000 位数字时比传统乘法快 59%。
    重要细节
  • bignum_init函数将 base-10 数字字符串转换为 30 位数字数组。
  • bignum_print函数处理 30 位数字的打印,包括处理零的情况。
  • 基准测试代码生成随机大整数并进行加法和乘法运算,记录时间。
  • Karatsuba 算法通过将两个 n 位数字拆分为三个 n/2 位数字进行乘法运算。
  • 目前的大整数库缺少负数字、减法、除法等核心功能,且可能存在 bug。
阅读 12
0 条评论