SML ：大整数表示模块

Question

这是一道作业题。在 SML 中，整数大小有一个限制，即 Int.maxInt，因此我必须设计一个包来表示大整数以及执行加法、乘法等操作。现在，显而易见的选择是拆分到一个列表或数组中，其中每个元素都有一个可接受大小的整数。但是如果定义一个函数假设，

IntToLargeInt(x, base) = (x mod base) :: IntToLargeInt(x div base , base)

现在，对于小于最大大小的整数，它会转换为列表中另一个基数的数字。但是对于大整数，在它甚至可以将其拆分之前，它会引发溢出异常。因此，关于如何直接从函数参数解析的任何提示，如标准输入流或类似的东西。基本上，任何可以帮助我使函数适用于大整数的东西。

是不是应该先用IntInf等类型存储，再转为其他基数？

或者如果我走错了方向，一些关于从哪里开始的提示会很好。

Answer 1

如果您担心效率，使用 IntInf.fromString 可能有意义。但是 - 如果您真的担心效率，那么您只需对所有内容使用 IntInf，而不是尝试自己实现大量库。

一种更天真的方法是将一串数字分解为一个反转的数字列表，然后将这个数字列表转换为您的一个 int 列表。您可以尽快执行此操作：

1) 将单个数字转换为 LargeInts

2) 将 LargeInt 乘以 10

3) 添加 LargeInts

为了了解这是如何工作的，这里是一个将字符串转换为普通整数的函数的实现：

fun digitToInt d = Char.ord d - Char.ord #"0";

fun digitsToInt [] = 0
|   digitsToInt (d::ds) = digitToInt d + 10 * digitsToInt ds;

请注意，上面的 + 和 * 需要替换为您的自定义函数。以上适用于最低有效数字在列表中排在第一位的数字，唉，这与数字表示的标准方式相反。我们可以使用内置函数 rev 来解决这个问题：

val stringToInt = digitsToInt o rev o explode;

（这完全等同于

fun stringToInt s = digitsToInt(rev(explode s));

但可读性稍强。）

例如，

- stringToInt "12345";
val it = 12345 : int

不是很令人兴奋，但您应该能够修改此方法以适应您的情况。

SML : module for large integer representation