大数相乘 golang

发布时间:2024-07-04 23:06:55

大数相乘算法在golang中的实现

对于计算机程序员来说，大数相乘是一项非常重要的任务。由于计算机在处理大数时会出现精度问题，因此需要设计高效的算法来解决这个问题。

在golang中，我们可以使用字符串来表示大数，然后通过遍历字符串的每位数字，并进行逐位相乘的方式来实现大数相乘。

1. 代码实现

下面是一个简单的大数相乘算法的实现：

``` func multiply(num1 string, num2 string) string { if num1 == "0" || num2 == "0" { return "0" } m, n := len(num1), len(num2) result := make([]int, m+n) for i := m - 1; i >= 0; i-- { for j := n - 1; j >= 0; j-- { mul := (num1[i] - '0') * (num2[j] - '0') p1, p2 := i+j, i+j+1 sum := mul + result[p2] result[p1] += sum / 10 result[p2] = sum % 10 } } res := "" for i := 0; i < len(result); i++ { if i == 0 && result[i] == 0 { continue } res += strconv.Itoa(result[i]) } return res } ```

2. 测试案例

下面是一些测试案例，用于验证大数相乘算法的正确性：

``` func TestMultiply(t *testing.T) { testCases := []struct { num1 string num2 string want string }{ {"2", "3", "6"}, {"123", "456", "56088"}, {"999", "999", "998001"}, {"123456789", "987654321", "121932631137021795"}, {"1234567890987654321", "9876543210123456789", "121932631137021795394029671244054118410263"}, } for _, tc := range testCases { result := multiply(tc.num1, tc.num2) if result != tc.want { t.Errorf("multiply(%s, %s) = %s; want %s", tc.num1, tc.num2, result, tc.want) } } } ```

3. 性能优化

在上述的代码实现中，我们采用了两层循环来计算每一位的相乘结果，并将结果存储在一个数组中。然后再将数组中的元素拼接成一个字符串返回。

但是，如果要计算非常长的数字相乘，上述方法可能会导致性能问题。此时，我们可以考虑使用类似于分治法的思想，将大数划分为更小的部分进行计算，然后再将结果合并。

具体代码实现如下：

``` func multiply(num1 string, num2 string) string { m, n := len(num1), len(num2) result := make([]int, m+n) for i := m - 1; i >= 0; i-- { for j := n - 1; j >= 0; j-- { mul := (num1[i] - '0') * (num2[j] - '0') p1, p2 := i+j, i+j+1 sum := mul + result[p2] result[p1] += sum / 10 result[p2] = sum % 10 } } // 去除前导0 i := 0 for i < len(result) && result[i] == 0 { i++ } res := "" for ; i < len(result); i++ { res += strconv.Itoa(result[i]) } return res } ```

4. 总结

通过上述代码实现，我们可以在golang中实现大数相乘算法。无论是简单的遍历相乘方法，还是优化后的分治法思想，都可以帮助我们高效地处理大数相乘问题。