标准 ML/NJ 的 BigInt
标准 ML 是否有等效的 Java BigInt？ 普通的int类型在溢出时会抛出异常。
Is there a Java BigInt equivalent for Standard ML? The normal int type throws an exception when it overflows.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
是的，请参阅 IntInf 结构。
Yes, see the IntInf structure.
官方 SML'97 标准 基础库 引入了一系列结构，例如 Int、IntInf、Int32、Int64、 LargeInt 等。
要在实践中实际使用它们以使事情按预期工作并使其高效工作，您需要仔细查看手头的 SML 实现。
一系列实现模仿了 C 和 Java 的内存布局，因此 Int32 实际上是一个 32 位机器字（但带有溢出检查），而 Int64 则是一个 64 位机器字。 SML/NJ 就是一个著名的例子，它的小整型运算很快，但大整型运算很慢。
另一个实现系列来自符号计算（LISP 或计算机代数）的背景，其中 Poly/ML 是一个著名的例子。 默认情况下，这里 Int = IntInf = LargeInt，并且实现首先使用（部分）本机机器字作为近似值，直到它溢出，然后切换到在堆上分配的真正大整数（作为装箱值）。 Poly/ML 使用 GNU MP 库来完成这一重要部分。
因此，只要您的应用程序涉及整数，而不是特定大小的机器字，Int/IntInf 就非常高效：由于需要额外的标记位，符号模型中的 Int32 不适合 32 位硬件上的单个字。 因此，一些实际上与字算术有关的算法会降级，例如 32 位硬件上的 SHA1。
另一方面，将短于字长的 int 隐式升级为堆分配的 big int 为您提供了比 Java 中的 BigInt 更好的功能，因为您不需要小值的完整对象开销：42 只是一点点寄存器中的模式（带有附加标记位），但不是堆上的重框。
The official SML'97 standard basis library introduces a zoo of structures like Int, IntInf, Int32, Int64, LargeInt etc.
To actually use them in practice to make things work as expected, and make them work efficiently, you need to look closely at the SML implementation at hand.
One family of implementations imitates the memory layout of C and Java, so Int32 will be really a 32bit machine word (but with overflow checking), and Int64 a 64bit machine word. SML/NJ is a notable example for that, and its small int arithmentic is fast, but its big int arithmentic slow.
Another family of implementations come from the background of symbolic computation (LISP or Computer Algebra), where Poly/ML is a notable example. Here you have Int = IntInf = LargeInt by default, and the implementation first uses (part of) the native machine word as approximation, until it overflows and then switches to really big integers that are allocated on the heap (as boxed values). Poly/ML uses the GNU MP library for that big part.
Thus Int/IntInf is very efficient as long as your application is about integers, not machine words of a specific size: Int32 in the symbolic model won't fit into a single word on 32bit hardware due to the extra tag bits that are required. So some algorithms that are actually about word arithmetic will degrade, for example SHA1 on 32bit hardware.
On the other hand, the implicit upgrade of shorter-than-wordsize int to heap-allocated big int gives you something better than BigInt in Java, because you won't need the full object overhead for small values: 42 will be just some bit pattern in a register (with additional tag bit), but not a heavy box on the heap.
BigInt 的等效项称为 LargeInt。 请参阅这些讲义查看一些有关如何在 int（又名 Int）和 LargeInt 之间转换的函数。
The BigInt-equivalent is called LargeInt. See these lecture notes to see some functions on how to convert between int (aka Int) and LargeInt.
虽然这并不完全是您所要求的，但您实际上并不需要与 Java BigInt 类等效的类。 Java 的 BigInt 类实现了 O(n^2) 乘法时间（本质上是小学中教授的乘法方式），而不是 O(n log n)，这是可能的。 这非常重要，因为许多琐碎的 BigInt 编程根本不适用于 n^2 版本。
While this isn't exactly what you were asking, you don't actually want an equivalent to the Java BigInt class. Java's BigInt class implements O(n^2) time for multiplication (essentially multiplying the way it's taught in elementary school), instead of O(n log n), which is possible. This is really important, as a lot of trivial BigInt programming simply doesn't work with the n^2 version.
好吧， int 对计算排列之类的东西设置了令人讨厌的限制。 SML 需要一个使用起来更自然的大型数字数据类型。
Well, int puts a nasty limit on stuff like calculating permutations. SML needs a large numeric datatype thats more natural to use.