[m-dev.] for review: big ints

[Fergus Henderson]

On 03-Apr-1998, Bert Thompson <aet at cs.mu.OZ.AU> wrote:
> Implementation of an arbitrary precision integer type and
> operations on it.
> 
> library/integer.m
...
> % Implements an arbitrary precision integer type and basic 
> % operations on it.
> %
> % (For comments on possible improvements, see the end of this file.)

When that parenthetical comment gets included in the library reference
manual, "this file" will be a dangling reference.  So I think that it
would be better to put that comment at the start of the implementation
section.

Also, for novices it would be helpful to briefly explain what an
"arbitrary precision integer type" is.

> :- func integer:'/'(integer, integer) = integer.

For consistency with `int', the truncating integer division function
should be called `//' or `div' (depending on how it rounds towards
zero or towards minus infinity).  `/' should be reserved for

	:- func integer:'/'(integer, integer) = float.

or perhaps

	:- func integer:'/'(integer, integer) = rational.

Also you should document the behaviour of this function and
`rem' for negative numbers.

> 	% We choose base=10000 since 10000^2+10000 < maxint.
> 	% XXX: We should check this. 
> :- func base = int.
> base = 10000.

Choosing base=16384 would also have the property, and would be
more efficient.

> integer__from_string(S) =
> 	Big :-
> 	string__to_char_list(S,Cs),
> 	string_to_integer(Cs) = Big.
> 
> :- func string_to_integer(list(char)) = integer.
> string_to_integer(CCs) =
> 	Result :-
> 	( CCs = [] ->
> 		error("string_to_integer: unreachable"),
> 		Result = zero
> 	; CCs = [C|Cs] ->
> 		% Note: '-' must be in parentheses.
> 		( C = ('-') ->
> 			Result = big_neg(string_to_integer(Cs))
> 		; char__is_digit(C) ->
> 			Result = i(1,Digs),
> 			Digs = string_to_integer_acc(CCs,[])
> 		;
> 			Result = zero,
> 			error("string_to_integer: can't parse string")
> 		)
> 	;
> 		Result = zero,
> 		error("string_to_integer: impossible value")
> 	).

The error("string_to_integer: unreachable") case is not unreachable.

It would be better, I think, to make integer__from_string semidet,
and have it fail if the string can't be parsed,
rather than calling error/1 in that case.

The last call to error/1 could be avoided by using a disjunction
rather than an if-then-else:

 	( CCs = [],
 		...
 		
 	; CCs = [C|Cs],
		...
	).

The recursive call for negative numbers means that it allows
strings of the form "-------42", which is probably not a good idea.

> pos_mul([],_Ys) = [].
> pos_mul([X|Xs], Ys) =
> 	Sum :-
>	...

I think that it would be clearer if you used a slightly different
indentation style, where the function result is on the same line as
the rest of the head:

	pos_mul([],_Ys) = [].
	pos_mul([X|Xs], Ys) = Sum :-
		...

Also a global search and replace to insert spaces after commas
would be a good idea.

> :- pred digit_to_string(digit,string).
> :- mode digit_to_string(in,out) is det.
> digit_to_string(D,S) :-
> 	string__int_to_string(D,S1),
> 	Width = 4,	% = log10(base)
> 	string__pad_left(S1,'0',Width,S).

It's probably worth defining a separate constant `log10base'
at the same place that `base' is defined.

		% returns log10(base).
	:- func log10base = int.
	log10base = 4.

Finally, some test cases would be a good idea.

(tests/general/arithmetic.m would be a good thing to start with.)

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.