CODEWITHSUNDEEP
prolognumbersclpfdnumber-theorylogical-purity
Kevin
Kevin

Reputation: 745

Prolog program to get an (integer) number as the sum of two integer squares, why does it not work?

I'm starting learning Prolog and I want a program that given a integer P gives to integers A and B such that P = A² + B². If there aren't values of A and B that satisfy this equation, false should be returned

For example: if P = 5, it should give A = 1 and B = 2 (or A = 2 and B = 1) because 1² + 2² = 5.

I was thinking this should work:

giveSum(P, A, B) :- integer(A), integer(B), integer(P), P is A*A + B*B.

with the query:

giveSum(5, A, B).

However, it does not. What should I do? I'm very new to Prolog so I'm still making lot of mistakes.

Thanks in advance!

Upvotes: 5

Views: 1081

Answers (2)

CapelliC
CapelliC

Reputation: 60034

For efficiency sake, Prolog implementers have choosen - many,many years ago - some compromise. Now, there are chances your Prolog implements advanced integer arithmetic, like CLP(FD) does. If this is the case, mat' answer is perfect. But some Prologs (maybe a naive ISO Prolog compliant processor), could complain about missing label/1, and (#=)/2. So, a traditional Prolog solution: the technique is called generate and test:

giveSum(P, A, B) :-
  ( integer(P) -> between(1,P,A), between(1,P,B) ; integer(A),integer(B) ),
  P is A*A + B*B.

between/3 it's not an ISO builtin, but it's rather easier than (#=)/2 and label/1 to write :)

Anyway, please follow mat' advice and avoid 'imperative' naming. Often a description of the relation is better, because Prolog it's just that: a relational language.

Upvotes: 1

mat
mat

Reputation: 40768

integer/1 is a non-monotonic predicate. It is not a relation that allows the reasoning you expect to apply in this case. To exemplify this:

?- integer(I).
false.

No integer exists, yes? Colour me surprised, to say the least!

Instead of such non-relational constructs, use your Prolog system's CLP(FD) constraints to reason about integers.

For example:

?- 5 #= A*A + B*B.
A in -2..-1\/1..2,
A^2#=_G1025,
_G1025 in 1..4,
_G1025+_G1052#=5,
_G1052 in 1..4,
B^2#=_G406,
B in -2..-1\/1..2

And for concrete solutions:

?- 5 #= A*A + B*B, label([A,B]).
A = -2,
B = -1 ;
A = -2,
B = 1 ;
A = -1,
B = -2 ;
etc.

CLP(FD) constraints are completely pure relations that can be used in the way you expect. See for more information.

Other things I noticed:

  • use_underscores_for_readability_as_is_the_convention_in_prolog instead ofMixingTheCasesToMakePredicatesHardToRead.
  • use declarative names, avoid imperatives. For example, why call it give_sum? This predicate also makes perfect sense if the sum is already given. So, what about sum_of_squares/3, for example?

Upvotes: 6

Related Questions