
Boost Users : 
Subject: Re: [Boostusers] [rational] proposed gcd and lcm for rational
From: Thomas Taylor (thomas.taylor_at_[hidden])
Date: 20110721 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
>>
>> _______________________________________________
>> Boostusers mailing list
>> Boostusers_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>>
Boostusers 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