SML : module for large integer representation

Question

This is a homework question. In SML, there's a limit to integer size that is Int.maxInt, so I have to design a package that can represent large integers as well as perform operations such as add, multiplication etc. Now, the obvious choice is to split up into a list or array where each element has an integer of acceptable size. But if define a function suppose,

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

Now, for integers less than the max size, it does convert to a number of another base in a list. But with large integers, before it can even split it up, it raises overflow exception. So, any hint to how to parse from the function argument directly like a stdin stream or something like that. Basically, anything to help me make the function work for large integers.

Should I use types such as IntInf to store it first and then convert to another base?

Or perhaps if i'm going in the wrong direction, some hints about where to start would be good.

John Coleman John Coleman · Accepted Answer · 2016-03-30T02:34:45

If you are worried about efficiency it might make sense to use IntInf.fromString. But -- if you were really worried about efficiency then you would just use IntInf for everything and not try to implement a large number library on your own.

A more naïve approach is to explode a string of digits into a reversed list of digits, and then convert this list of digits into one of your int lists. You can do this as soon as you can:

1) Convert individual digits into LargeInts

2) Multiply your LargeInts by 10

3) Add LargeInts

to get an idea how this could work, here is an implementation of a function which converts a string into an ordinary integer:

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

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

Note that the + and * in the above would need to be replaced by your custom functions. The above applies to digits in which the least significant digit is first in the list, which is, alas, the opposite of the standard way that numbers are represented. We can use the built-in function rev to fix this:

val stringToInt = digitsToInt o rev o explode;

(This is completely equivalent to

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

but slightly more readable.)

For example,

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

Not very exciting, but you should be able to modify this approach to match your situation.

SML : module for large integer representation

1 Answers