Boost logo

Boost Users :

Subject: Re: [Boost-users] [rational] proposed gcd and lcm for rational
From: Thomas Taylor (thomas.taylor_at_[hidden])
Date: 2011-07-21 20:29:07


Topposting gets me confused :-S so I reordered this a bit

>> On Jul 21, 2011, at 7:44 AM, Júlio Hoffimann wrote:
>>
>> Hi Thomas,
>>
>> Thank you for the intention, but as far as i know, GCD and LCM makes no
>> sense in the rational field. Any rational number is divisible by all
>> rationals. For instance, given two rationals b, r in Q, r != 0, you can
>> write:
>>
>> b = (b * r^-1) * r
>>
>> and then b is divisible by r.

> 2011/7/21 Christopher Henrich <chenrich_at_[hidden]>
>
>> GCD and LCM can be defined for rationals, if one takes "divisible" to
>> mean "divisible with an integer quotient" and, similarly, "multiple" to
>> mean "multiple by an integer." Then, for example, GCD(1/2, 1/3) = 1/6 and
>> LCM(1/2, 1/3) = 1.

> Hi Christopher,
>
> This is the first time i heard about this interpretation. For me, still
> makes no sense, but if people thinks is useful, ok.

Basically I used the approach desribed by Christopher. (see also
http://en.wikipedia.org/wiki/Least_common_multiple#Rational unfortunately it
does not cite anything for this paragraph (there even is a similar approach
for modulo calculation
http://de.wikipedia.org/wiki/Division_mit_Rest#Verallgemeinerung:_Reelle_Zahlen
- sorry German only))

Especially a lcm makes sense in my opinion, as any two numbers have a lcm;
the question only is what base set [Zahlenraum] one uses. (the posted
implementation gives rational lcms (base set = R), but it could be modified
to only give integer lcms (base set = Z)).

The gcd is certainly trickier as it appears to me to be less intuitive.
However the best way to describe what it does is probably what I am using it
for: Consider a 2d vector v=(a,b). Now we don't care about the length |v|
but only for the direction, which is defined by the factor between a and b.
Lets further assume that both a and b are rational. Multiplying both a and b
with gcd(a,b) [c=a*gcd(a,b) and d=b*gcd(a,b)] will give v'=(c,d), where both
c and d are integers and furthermore the smallest integers that represent
the direction (or factor between a and b).

HTH,
Thomas

>>
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net