'"Optimize 3-fold nested loop given set of comparision-conditions between loop-variables" or "optimize lower-/upper bounds"
For a mathematical problem I want to find solutions which involve 3 loop-variables, say (e,h,i). I have a set of lower/greater-conditions on the loop-variables, so there is a real chance to reduce the search-space from -say [1..100,1..100,1..100] radically, if -say- e is given.
The basic condition is, that in fact I work with a set of 6 linear combinations of e²,h²,i² taken as polynomials which should as well result in a square value, thus a positive value. For instance the first condition is 2e² - i² = a² and the second is 2e²-h²=b²
----------------------
*ee *hh *ii
----------------------
2 0 -1 = aa
2 -1 0 = bb
-1 1 1 = cc
-2 1 2 = dd
1 0 0 = ee // shown just for completeness
4 -1 -2 = ff
3 -1 -1 = gg
0 1 0 = hh // shown just for completeness
0 0 1 = ii // shown just for completeness
I write ee,hh,ii for ease of notation. From the first condition, to get a positive value a² I must thus have 2ee > ii so for a value in loop-variable e I know the upper bound for the loop-variable i is an integer near sqrt(2ee).
Here are the 6 relevant conditions:
2ee > ii
2ee > hh
-ee > -hh- ii
-2ee > -hh-2ii
4ee > hh+2ii
3ee > hh+ ii
The loop-construct shall finally be like this and the upper bound for e as large as possible to run in acceptable time (this is actually pseudocode!)
for e=1 to 1000; ee=e^2 ; hlb=<some-lower-bound>; hub=<some-upper-bound>;
for h=hlb to hub; hh=h^2 ; ilb=<some-lower-bound>; iub=<some-upper-bound>;
for i=ilb to iub; ii=i^2;
aa=2*ee-ii; if !issquare(aa) then next;
bb=2*ee-hh; if !issquare(bb) then next;
cc= -ee+hh+ii; if !issquare(cc) then next;
<and so on; I expext at least 4 squares in aa,bb,cc,dd,ff,gg>
if condition-is-met then print("one solution:",e,h,i);
next i;
next h;
next e;
My questions is: what are the tightest bounds for the loop-variables h and i given e. I'd most like to have a general ansatz to solve such a problem.
What I've found so far by combination and aggregation of the conditions
2ee > ii,hh
hh+ ii > ee
hh+2ii > 2ee
4ee > hh+2ii
3ee > hh+ ii
then
12ee > 6ii,6hh
12hh+12ii > 12ee
6hh+12ii > 12ee
12ee > 3hh+6ii
12ee > 4hh+4ii
using the smallest upper bounds (on lhs) resp largest lower bounds (on rhs) I think I can simplify
24ee > 6hh+12ii > 12ee > 6hh,6ii, 4hh+4ii
But then I do not see how I could simplify this more and actually formulate hlb,hub,ilb,iub ...
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
