CSL102: Introduction to Computer Science
II semester 2004-05

Assignment: Large Integers

The factorial function that we wrote does not allow us to compute any thing more than the factorial of 12 (= 479001600). It gives an overflow exception as soon as the value of factorial crosses the maximum permissible integer on a word. It would be nice if one could confidently assert¹ that the factorial of 1000 is

4023872600770937735437024339230039857193748642107146325437999104299385123
9862902059204420848696940480047998861019719605863166687299480855890132382
9669944590997424504087073759918823627727188732519779505950995276120874975
4624970436014182780946464962910563938874378864873371191810458257836478499
7701247663288983595573543251318532395846307555740911426241747434934755342
8646576611667797396668820291207379143853719588249808126867838374559731746
1360853795345242215865932019280908782973084313928444032812315586110369768
0135730421616874760967587134831202547858932076716913244842623613141250878
0208000261683151027341827977704784635868170164365024153691398281264810213
0927612448963599287051149649754199093422215668325720808213331861168115536
1583654698404670897560290095053761647584772842188967964624494516076535340
8198901385442487984959953319101723355556602139450399736280750137837615307
1277619268490343526252000158885351473316117021039681759215109077880193931
7811419454525722386554146106289218796022383897147608850627686296714667469
7562911234082439208160153780889893964518263243671616762179168909779911903
7540312746222899880051954444142820121873617459926429565817466283029555702
9902432415318161721046583203678690611726015878352075151628422554026517048
3304226143974286933061690897968482590125458327168226458066526769958652682
2728070757813918581788896522081643483448259932660433676601769996128318607
8838615027946595513115655203609398818061213855860030143569452722420634463
1797460594682573103790084024432438465657245014402821885252470935190620929
0231364932734975655139587205596542287497740114133469627154228458623773875
3823048386568897646192738381490014076731044664025989949022222176590433990
1886018566526485061799702356193897017860040811889729918311021171229845901
6419210688843871218556461249607987229085192968193723886426148396573822911
2312502418664935314397013742853192664987533721894069428143411852015801412
3344828015051399694290153483077644569099073152433278288269864602789864321
1390835062170950025973898635542771967428222487575867657523442202075736305
6949882508796892816275384886339690995982628095612145099487170124451646126
0379029309120889086942028510640182154399457156805941872748998094254742173
5824010636774045957417851608292301353580818400969963725242305608559037006
2427124341690900415369010593398383577793941097002775347200000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000

Hence it is necessary to be able to deal with large integers if the computer has to be a useful tool.

Program the following library to perform operations on integers of arbitrary size (including the usual integers are the representable on the machine). In particular use this signature to compute large numbers such as the factorial of 10000. To be consistent with ML notation make sure you call your structure ``Bigint''.

signature BIGINT =
   sig
       type bigint
       exception InvalidString
       exception DivisionByZero
       val fromString : string -> bigint
       val fromInt    : int -> bigint
       val compare    : bigint * bigint -> order  
       val add        : bigint * bigint -> unit
       val mult       : bigint * bigint -> unit
       val sub        : bigint * bigint -> unit
       val div        : bigint * bigint -> bigint
       val mod        : bigint * bigint -> bigint
       val toString   : bigint -> string
   end;

All the functions in the signature are self-explanatory. In particular since it may be necessary to perform operations between large integers and smaller integers, it is necessary to write the function fromInt which transforms a standard element of type int in SML to the representation you use for type bigint. Note:

1. You are not allowed to change any of the names given in the signature. You are not even allowed to change upper-case letters to lower-case letters or vice-versa.
2. You may define any new functions you like in the structure besides those mentioned in the signature.
3. Your program should work with the given signature.
4. You need to think of the most efficient way of implementing the various functions given in the signature so that the function results satisfy their definitions and properties.
5. Since the evaluator is going to look at your source code before evaluating it, you must explain your algorithms in the form of ML comments, so that the evaluator can understand what you have implemented.
6. Do not add any more decorations or functions or user-interfaces in order to impress the evaluator of the program. Nobody is going to be impressed by it.
7. There is a serious penalty for copying. If it is felt that there is too much similarity in the code between any two persons, then both are going to be penalized equally. So please set permissions on your directories, so that others cannot copy your programs.