算法记录-大数相乘

本文代码使用golang实现

前言

这篇文章主要记录下如何实现大数相乘。讲道理作为一个正式工作两年的程序员，不应该对这一块不了解，可能是因为工作中基本没有这个场景，所以也没考虑到。

这个问题是因为前段时间和朋友吃饭，忽然谈论到了，所以写下这篇文章记录下。

正文

问题为：

如何用程序实现1到100的阶乘(1乘以2乘以3乘以...直到100)，并用变量保存且打印出来。

这个问题其实可以简化成大数相乘。难点是大部分编程语言很少有数字类型的变量可以正确且高效地存储最终结果。

初步算法

第一版是先最简单，具体是循环1到100，每次循环相乘：

1
2
3
4
5


var result uint64 = 1
for i := 2; i <= 100; i++ {
	result *= uint64(i)
}
fmt.Println("result:", result)

最终控制台打印的结果为:

1

result: 0

这个明显不正确，因为最终的结果远远超过了uint64支持的最大值。故普通的方法不可行。

第二步算法

第二版想到的是用分段的思想:

分段计算结果

分多个变量，每个变量保存分段的结果集，最终结果相加就是答案。但是仍然有一个问题，每个分段的变量可以保存结果集，相加起来还是会超过。

可以使用第三方包decimal来解决这个数值问题。(虽然我没试过，但感觉应该没问题0-0)。但如果这样的话，我们不如直接用decimal类型再基于第一版的算法去实现，省去了分段的操作，更加简便。

最终算法

这里我们考虑，是否可以不借助外部库(只用golang标准库)去实现大数相乘。

答案是肯定的，这里使用切片或者字符串。代码实现:

1
2
3
4
5
6
7


var res string
for i := 1; i < 100; i++ {
	temp := strconv.Itoa(i * (i + 1))
	res += temp
}

fmt.Println("res:", res)

输出结果:

1

res: 261220304256729011013215618221024027230634238042046250655260065070275681287093099210561122119012601332140614821560164017221806189219802070216222562352245025502652275628622970308031923306342235403660378239064032416042904422455646924830497051125256540255505700585260066162632064806642680669727140731074827656783280108190837285568742893091209312950697029900

tips: 好久没写博客了，就当我水了篇文章。