Interval FAQ: [ Entry page | Contents | Search ]

About Sun's f95 with Interval Support

Eugene Zak -- Finding the GCD or LCM of fuzzy numbers?

Example:

a = [9, 11] b = [14, 16] GCD(a,b) = 5 LCM( a, b) = 30A 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.

Interval FAQ: [ Entry page | Contents | Search ]

About Sun's f95 with Interval Support

If *you* have a question related to validated computing, interval
analysis, or related matters, I recommend

- Vladik Kreinovich's Interval Computation web site, or
- Submit it to the interval computations listserv: reliable_computing@interval.louisiana.edu

Last modified February 27, 19100. Send comments to (

Access count since 20 Apr 1999 :