[rational] proposed gcd and lcm for rational
Dear boost users and maintainers, As I needed these functions myself I have added a gcd and an lcm for the rational type. Feel free to do with the code whatever you want, if suitable add it to rational.hpp. Presumably this could be reworked as partial specialisation of boost::math::gcd and boost::math::lcm respectively (if there is a trait like is_rational). HTH, Thomas
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. Regards, Júlio. 2011/7/21 Thomas Taylor <thomas.taylor@univie.ac.at>
Dear boost users and maintainers,
As I needed these functions myself I have added a gcd and an lcm for the rational type. Feel free to do with the code whatever you want, if suitable add it to rational.hpp. Presumably this could be reworked as partial specialisation of boost::math::gcd and boost::math::lcm respectively (if there is a trait like is_rational).
HTH, Thomas
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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. 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.
Regards, Júlio.
2011/7/21 Thomas Taylor <thomas.taylor@univie.ac.at> Dear boost users and maintainers,
As I needed these functions myself I have added a gcd and an lcm for the rational type. Feel free to do with the code whatever you want, if suitable add it to rational.hpp. Presumably this could be reworked as partial specialisation of boost::math::gcd and boost::math::lcm respectively (if there is a trait like is_rational).
HTH, Thomas
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Christopher Henrich chenrich@monmouth.com mathinteract.com
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. Regards, Júlio. 2011/7/21 Christopher Henrich <chenrich@monmouth.com>
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.
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.
Regards, Júlio.
2011/7/21 Thomas Taylor <thomas.taylor@univie.ac.at>
Dear boost users and maintainers,
As I needed these functions myself I have added a gcd and an lcm for the rational type. Feel free to do with the code whatever you want, if suitable add it to rational.hpp. Presumably this could be reworked as partial specialisation of boost::math::gcd and boost::math::lcm respectively (if there is a trait like is_rational).
HTH, Thomas
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Christopher Henrich chenrich@monmouth.com mathinteract.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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@monmouth.com>
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_Zah... - 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Thomas, hi all, Interesting approach. :) I'm just saying that these concepts are not what most people think as GCD/LCM. If Boost.Rational developers wants to add this feature to the library, they should make clear what is happening in Boost.Rational documentation. ;) Best Regards, Júlio. 2011/7/21 Thomas Taylor <thomas.taylor@univie.ac.at>
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@monmouth.com>
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_Zah... - 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Thu, Jul 21, 2011 at 17:29, Thomas Taylor <thomas.taylor@univie.ac.at> wrote:
Especially a lcm makes sense in my opinion, [...]
The gcd is certainly trickier as it appears to me to be less intuitive.
I think that once you have one, you don't have to think about the other. I'd be very confused if the implementation didn't always satisfy GCD(a, b) * LCM(a, b) = a * b ~ Scott
There is one use case for gcd of rationals in C++11: [time.traits.specializations]/p1-2: --- template <class Rep1, class Period1, class Rep2, class Period2> struct common_type<chrono::duration<Rep1, Period1>, chrono::duration<Rep2, Period2>> { typedef chrono::duration<typename common_type<Rep1, Rep2>::type, see below> type; }; 1 The period of the duration indicated by this specialization of common_type shall be the greatest common divisor of Period1 and Period2. [Note: This can be computed by forming a ratio of the greatest common divisor of Period1::num and Period2::num and the least common multiple of Period1::den and Period2::den. —endnote] 2 [ Note: The typedef name type is a synonym for the duration with the largest tick period possible where both duration arguments will convert to it without requiring a division operation. The representation of this type is intended to be able to hold any value resulting from this conversion with no truncation error, although floating-point durations may have round-off errors. — end note ] --- The "Period" is a std::ratio, a compile-time rational class. Howard On Jul 21, 2011, at 10:44 AM, Christopher Henrich wrote:
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.
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.
Regards, Júlio.
2011/7/21 Thomas Taylor <thomas.taylor@univie.ac.at> Dear boost users and maintainers,
As I needed these functions myself I have added a gcd and an lcm for the rational type. Feel free to do with the code whatever you want, if suitable add it to rational.hpp. Presumably this could be reworked as partial specialisation of boost::math::gcd and boost::math::lcm respectively (if there is a trait like is_rational).
HTH, Thomas
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Christopher Henrich chenrich@monmouth.com mathinteract.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (4)
-
Christopher Henrich -
Howard Hinnant -
Júlio Hoffimann -
Scott McMurray -
Thomas Taylor