计算预定义数字类型之外的大量数字

Question

作为家庭作业的一部分，我正在研究斐波那契数发生器。用预定义的数字类型（例如 Go 中的 int32）表示这些斐波那契数的输出变得不可能，您必须使用类似这样的东西来处理大量数字： https ://golang.org/pkg/math/big/如果我们稍微改变问题的询问，而不是询问第 1,000 个斐波那契数的结果，而是询问相同数字的最后一位，Go 可以毫无问题地处理这个问题。我的问题是：Go 是否能够计算非常大的数字，因为当数字开始变得非常大时需要更多内存时，语言能够扩展堆栈大小？当这些数字开始变得如此之大以至于无法放入内存中的 32 或 64 位整数类型时，它们在哪里/如何存储它们？如果 Go 能够对不适合 int32 等基本类型的大量数字进行计算，为什么该语言会强制您将这些数字存储在一个太小而无法处理的基本类型中？例如，如果 Go 能够将两个非常大的数字相加并确定一个看似没有问题的结果，为什么我不能存储这个值以供将来使用或不使用另一个库将其打印到屏幕上呢？我想我不确定为什么如果在幕后 Go 能够很好地对它们进行操作，那么在尝试执行诸如将它们打印到屏幕之类的操作时，为什么数字必须适合预定义的大小。这是一些示例代码，我在其中存储并打印第 n 个斐波那契数的最后一位，而不是打印出第 n 个项的实际值，因为数字变得如此之大。请注意，我仍然如何在 append 语句中添加这些大量数字，但只存储最后一个数字。似乎 Go 使用“ascii”排序。您可以collate "C"在 Postgres 中使用：SELECT wordfrom unnest(ARRAY['Go', '[Bravo]', 'Gopher', '[Alpha]', 'Grin', 'Delta']) as t(word) ORDER BY word collate "C" ;package mainimport "fmt"func main() {    var n int    var fibNums = []int{0, 1}    var i int    fmt.Scanln(&n)    for i = 0; i < n; i++ {        fibNums = append(fibNums, (fibNums[i]+fibNums[i+1])%10)    }    fmt.Println(fibNums[len(fibNums)-2])}

Answer 1

Go 是否能够计算非常大的数字，因为当数字开始变得非常大时需要更多内存时，语言能够扩展堆栈大小？当这些数字开始变得如此之大以至于无法放入内存中的 32 或 64 位整数类型时，它们在哪里/如何存储它们？

有点 - 它能够做到这一点，因为当您使用 时math.Big，它本质上是将每个数字存储为 的切片uint，以及一些额外的字段（例如数字的符号），其中切片中的每个项目代表单个数字数字。

如果 Go 能够对不适合 int32 等基本类型的大量数字进行计算，为什么该语言会强制您将这些数字存储在一个太小而无法处理的基本类型中？

该语言不会强迫您将它们存储在该类型中 - 您可以自由使用math.Big所有数字。但一般来说，我们希望我们的代码能够快速运行，并且需要做的工作量是：

x := 21

y := 29

z := x + y

很少，而且会跑的很快。但这是一种折衷——你只需要意识到像这样简单的事情，当将每个数字存储在一个切片中时，会变成更多的步骤。作为一个快速演示：（https://play.golang.org/p/rFWKbKy4FeQ）：

x := []uint{2,1}

y := []uint{2,9}

result := []uint{}

xIndex := len(x) - 1

yIndex := len(y) - 1

carry := 0

for ; xIndex >= 0 || yIndex >= 0; {

    z := uint(0)

    if xIndex >= 0 && yIndex >= 0 {

        z = x[xIndex] + y[yIndex]

    } else if xIndex >= 0 {

        z = x[xIndex]

    } else {

        z = y[yIndex]

    }

    if carry != 0 {

        z++

    }

    if z >= 10 {

        carry = 1

        z = z % 10

    }

    xIndex--

    yIndex--

    result = append([]uint{z}, result...)

}

fmt.Println(result)

我仍然会得到正确的答案（在这种情况下，我什至还没有担心任何边缘情况），但还有很多工作要做。如果每个数学运算都需要这么多的工作，那么 Go 就不会被认为是一种快速语言。

Answer 2

Go 是否能够计算非常大的数字，因为当数字开始变得非常大时需要更多内存时，语言能够扩展堆栈大小？

不，堆栈和数学/大是完全无关的。

当这些数字开始变得如此之大以至于无法放入内存中的 32 或 64 位整数类型时，它们在哪里/如何存储它们？

“哪里”：没人知道。去吧，该语言不对事物的“存储位置”做出任何声明/保证。普通计算机有一个堆栈和一个堆，两个最常见的 Go 编译器决定将 math/big.Int 放在哪里。这个决定是针对每个变量单独做出的。请注意，不同的编译器版本可能会做出不同的决定。（谷歌“逃逸分析”了解详情）。您可以假设 math/big.Int 存储在堆中。

“如何”：阅读 math/big.Int 的来源 :-) 基本上是几个原始整数。请参阅https://golang.org/src/math/big/nat.go#L23（大致就像您以十进制编码 > 9 的数字）。

如果 Go 能够对不适合 int32 等基本类型的大量数字进行计算，为什么该语言会强制您将这些数字存储在一个太小而无法处理的基本类型中？

这个问题假设“语言迫使您将这些数字存储在一个太小而无法处理它们的基本类型中”，这是错误的。Go 中的“最大”整数类型是 uint64，如果这还不够，您可以使用 math/big.Int 并且没有人强迫您将 math/big.Int 存储在其中一种原始类型中。

例如，如果 Go 能够将两个非常大的数字相加并确定一个看似没有问题的结果，为什么我不能存储这个值以供将来使用或不使用另一个库将其打印到屏幕上呢？

假设“Go”是指原始内置类型：不，此 Go 无法对不适合使用的原始类型的数字进行计算。要对“大量数字”进行正确计算，您必须使用包 math/big。

请注意，一旦一个数字溢出 int（通常为 9223372036854775807），您的“斐波那契数的最后一位是完全错误的。Go over-/underflow 中的原始类型（在规范中查找确切的详细信息）在这种情况下，结果定义明确但没有比你期望的更长。

（旁注：Go 对常量的处理是不同的。）