On 12/23/13 11:25, Georgi Guninski wrote:
On Mon, Dec 23, 2013 at 09:16:40AM +0100, Sven Verdoolaege wrote:
On Sun, Dec 22, 2013 at 02:06:06PM +0200, Georgi Guninski wrote:
Many thanks for the prolog solution!
If I remove the last constraint (comment it in the code):
//cs.insert(Coefficient(A0)*A - Coefficient(B0)*B <= Coefficient(L) );//XXX
Then try with: A0=654013667618 B0=654013667619 L= 654013667617
I again run out of memory, why so? (swipl finds solutions even to the original problem for these values).
Last time I checked glpk and lp-solve they don't support large integers - work modulo 2^32 or 2^64 and don't give correct solutions over the integers
PPL is the only free solver I know of supporting large integers.
Didn't you just say that SWI-Prolog works for you?
In any case, there is also isl:
$ ./isl_polyhedron_sample { [A,B] : 1 <= A and A <= 808711 and 1 <= B and 1 <= 654013667618 * A - 654013667619 * B <= 808711 } [] $ ./isl_polyhedron_sample { [A,B] : 1 <= A and A <= 808711 and 1 <= B and 1 <= 654013667618 * A - 654013667619 * B <= 654013667617 } [1,404356,404355] $ ./isl_polyhedron_sample { [A,B] : 1 <= A and A <= 808711 and 1 <= B and 1 <= 654013667618 * A - 654013667619 * B } [1,808711,1](The first "1" in the output is the denominator and is always "1", if there is a solution.)
skimo
Thank you for the isl solution Sven!
isl solves in seconds a minor modification for L ~ 2^70 while swi-prolog couldn't solve it in 3 hours.
Neither the PPL, nor SWI-Prolog, nor isl are the right tools for this problem. What you need is the extended Euclidean algorithm. PPL contributor Alessandro Zaccagnini can tell you more about this. Kind regards,
Roberto