[ Marquette | MSCS | Corliss | Vladik's Intervals ]
Interval FAQ: [ Entry page | Contents | Search ]
About Sun's f95 with Interval Support

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

From Eugene Zak (zak@majiq.com):

Is there an efficient algorithm for finding the GCD or LCM of fuzzy numbers?

I am looking for an efficient algorithm for finding GCD or LCM of fuzzy numbers. I define a fuzzy number "a" as a = [a_min, a_max], and GCD(a,b) as the greatest among GCD(x,y), where x belongs to [a_min, a_max] and y belongs to [b_min, b_max]. LCM(a,b) is the least among LCM(x,y) accordingly.


     a = [9, 11]
     b = [14, 16]
     GCD(a,b) = 5
     LCM( a, b) = 30
A trivial enumeration is not acceptable.

Thanks a lot. Eugene

Response by Vladik Kreinovich:

(vladik@cs.utep.edu), University of Texas at El Paso:

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).


More from Eugene Zak:


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

Response by George Corliss:

(georgec@mscs.mu.edu), Marquette University.

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.

[ Marquette | MSCS | Corliss | Vladik's Intervals ]
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

This page URL: http://www.mscs.mu.edu/~georgec/IFAQ/zak1.html
Last modified February 27, 19100. Send comments to (georgec@mscs.mu.edu)
Access count since 20 Apr 1999 : Graphical counter