Example:
a = [9, 11]
b = [14, 16]
GCD(a,b) = 5
LCM( a, b) = 30
A trivial enumeration is not acceptable.
Thanks a lot. Eugene
It looks like your question was sent to the wrong list, because it has nothing to do with fuzzy and all to do with intervals. I am forwarding it to the interval computations mailing list, maybe someone knows a good algorithm for that.
It may not happen, because we are normally dealing with intervals of real numbers, and for interval of integers, usually, all the problems become much computationally harder.
In my experience, it may help if you elaborate some on the practical problem (if there is any) which you are trying to solve.
You may also want to try to consult someone working in number theory, maybe they have a good algorithm already known (or some negative result, like NP-hardness).
The only close practical problem which I could think of is a problem useful in celestial mecahnics where we have, e.g., two interval [p1-,p1+] and [p2-,p2+] for periods of two planets, and we are trying to find the ratio p1/p2 where p1 and p2 are from the corresponding intervals which is rational with, say, the smallest possible sum of the absolute values of numerator and denominator (this problem is useful for detecting resonances which behave differently in terms of stability (we had a small paper on that some time ago).
Vladik
Hello, Vladik:
Many thanks for you detailed letter. As a matter fact I do not insist on
integrality of the numbers. I used integers for illustration purpose only.
As for the practical problem you have a good example. Mine is not from the
sky but from the paper industry. A paper customer may accept a paper roll of a
certain diameter but with some say 4%
tolerance. So the diameter tolerance bring the "fuzziness". That roll is
rewound from a larger roll. It would be nice
to rewind an integer number of finished rolls out of a large parent roll.
Diameter is certainly being translated to linear footage. The general case of the problem stems from a special equipment- biwinder where rolls of several different diameters can be wound from one parent.
I agree that intervals is not a full scale fuzzy number case. I appreciate forwarding my letter to the appropriate news group.
Thanks. Eugene
In a paper:
Paulina Chin, Robert M. Corless, and George F. Corliss,
Optimization Strategies for the Floating-Point GCD,
in Proceedings of the 1998 International Symposium on Symbolic and
Algebraic Computation (ISAAC '98),
Oliver Gloor (ed.), ACM Press, New York, 1998, pp. 228-235.
See www.mscs.mu.edu/~georgec/Pubs/chapt.html#1998a
we attacked a vaguely similar problem. The idea in your context is to formulate the question as an optimization problem
min -GCD
subject to
GCD * p = a in [a]
GCD * q = b in [b]
If your GCD is an integer, this is an integer
programming problem. a in [a] and b in [b] are probably expressed
to your integer programming software as bound constraints.
Actually, I guess this is an integer LP problem? I'm an interval person, so I'd probably use an interval tool, GlobSol from Baker Kearfott, but that is almost surely overkill. Surely a point integer (or floating point, if you prefer) LP solver will do fine.
If you have a question related to validated computing, interval analysis, or related matters, I recommend