How to solve diophantine problems?

[Cameron Laird]

In article <A3CC622F1F200C4E.B094127AFC81DF2B.B06C9B7849374CBE at lp.airnews.net>,
I apparently temporized:
>In article <abr0dq$fsm$1 at thccy25.nthu.edu.tw>,
>Joshua, Y.J. Lai <g893404 at oz.nthu.edu.tw> wrote:
			.
			.
			.
>>Thank you for your precise explanation. The problem now I suffer is how can
>>I write a new checking loop
>>instead of using two FOR LOOPs as nest loop. I am really interested in that.
>>I will be very grateful if anyone of you can give me some hints.
>>
>>
>
>Please explain the problem again.  Are you looking for
>an implementation that solves this specific diophantine
>problem (perhaps with the coefficients as variables,
>with respect to the implementation) while manifesting
>only one overt loop, or a general way to express
>a program transformation which reduces loop counts for
>diophantine problems, or ...?  At this point, you have
>complete knowledge--that is, a terminating procedure
>--about the solutions of the problems; what more can
>you want?
			.
			.
			.
Mr. Joshua and I have done a little bit privately.  I
still don't understand the question, and think there
might be benefit in doing this back out in public.

I believe he's asking either a very hard question, or
a very easy one.  Here's an answer to the easy one:
if we're searching for
  all (x,y) such that P(x, y), and 0 <= x,y <= 100
for some proposition P(), then we can exhaustively
search
  for x in range(0, 100):
      for y in range(0, 100):
	  if P(x, y):
	      print "(%s, %s) is a solution." % (x, y)
(note that several optimizations are available.  I
choose this expression for what I hope to be expository
clarity).  This is what Mr. Joshua has achieved already.

He *might* be asking for a generalization which drops
the range constraints ('cept that we're still looking for
non-negatives?), and asks merely that the program con-
tinue until it finds a solution (which can be rearranged
as a generator, of course).  How can he loop, though?
There are plenty of ways to do that; it occurs to me he
might like
  sum = 0
  while 1:
      for x in range (0, sum):
          y = sum - x
	  if P(x, y):
	      print "(%s, %s) is a solution." % (x, y)
      sum = sum + 1
(everybody see how nice generators would make this?).

It's possible, though, that Mr. Joshua is asking for
something like an algorithm to determine upper bounds
on solutions, depending on P.  That's a very hard problem,
at least for today.
-- 

Cameron Laird <Cameron at Lairds.com>
Business:  http://www.Phaseit.net
Personal:  http://starbase.neosoft.com/~claird/home.html