diff: lpQ - new module for linear programming over Q

[Bert Thompson]

Vanessa Joy TEAGUE <vjteag at students.cs.mu.oz.au> writes:


|Add some functions to lp and change number representation to rationals.

|compiler/rat.m:

|	Implement a rational number type, predicates for comparison
|	of rats, functions for arithmetic operations on rats and 
|	simplification of rats using greatest common divisor.


| :- func ratnorm(rat) = rat.

|rat(Num, Den) = ratnorm(r(Num, Den)).

|rat:'='(r(An, Ad), r(Bn, Bd)) :-
|	ratnorm(r(An, Ad)) = ratnorm(r(Bn, Bd)).

|rat:float(r(Num, Den)) = float:'/'(float:float(Num), float:float(Den)).

|one = r(1, 1).

|zero = r(0, 1).

|rat:'+'(Rat) = Rat.

|rat:'-'(r(Num, Den)) = r(-Num, Den).

|rat:'+'(r(An, Ad), r(Bn, Bd)) = ratnorm(r(int:'+'(An*Bd, Bn*Ad), Ad*Bd)).

Hi Vanessa,

Firstly, let me point out that I'm not competent to judge your algorithms.
I suspect moreover few people here have the necessary knowledge to.
That said, the code was impressively lucid and well-engineered.

Anyways, some specific suggestions...

There's a better way of adding rationals that results in smaller
numbers in the denominator before normalisation. Hence
	a) there's less chance of hitting MAXINT when using
	   finite precision ints.
	b) calculations are faster when using big ints.
	
Here's an example:

Old way:

	3/16 + 5/12 = norm ( (3*12 + 5*16)/(16*12) )

New way:

	3/16 + 5/12 = (3*3)/(16*3) + (5*4)/(12*4)
		    = (3*3 + 5*4)/48

	Or algebraically:

	n1/d1 + n2/d2 = norm ((n1*a1 + n2*a2)/(d1*a1))
			where
			a1 = int:'/' d1 m
			a2 = int:'/' d2 m
			m = lcm d1 d2

You can do similar sorts of tricks with multiplication, division,
and subtraction. Given that you're using finite precision ints,
it's probably worth doing, otherwise some poor sod will spend
half a day looking for a bug that's just code hitting its head on MAXINT.

Also, you might consider giving better references for the techniques
used in the code. There was no reference for the Fourier-Motzkin
method. There was "Benoy and King" for the convex hull stuff, but
a little more info would make it easier to find the book.

Hope this is useful,
Bert


------
This is a Cc: of an article on USENET sent to you for your convenience.
------