Today’s problem is rather theoretical, but there will be some computation and code. Read on:
There is a rather nice extension of greatest common divisor of two integers to the set of rational numbers. Today, I will give this extension.
In order to simplify the notation, I will use \(\frac{a}{b}\wedge\frac{c}{d}\) instead of \(\gcd(\frac{a}{b},\frac{c}{d})\).
Given two rational numbers \(\frac{a}{b}\) and \(\frac{c}{d}\) define \[ \frac{a}{b}\wedge\frac{c}{d} = \frac{ad\wedge bc}{bd} \]
This definition enjoys a rather nice property: multiplication is distributive over the greatest common divisor \[ \frac{a}{b}\left(\frac{c}{d}\wedge\frac{e}{f}\right) = \frac{\gcd(acf,ade)}{bdf} = \frac{ac}{bd}\wedge\frac{ae}{bf} \] This means the set of positive rationals \(\mathbb{Q}_+\) form a semi-ring with respect to greatest common divisor and multiplication operators.
In common lisp’s numerical tower there is a specific type for fractional numbers. I will exploit that:
(defmethod rational-gcd ((x integer) (y integer))
(gcd x y))
#<STANDARD-METHOD RATIONAL-GCD (INTEGER INTEGER) {F84B181}>
(defmethod rational-gcd ((x integer) (y ratio))
(/ (gcd (* x (denominator y))
(numerator y))
(denominator y)))
#<STANDARD-METHOD RATIONAL-GCD (INTEGER RATIO) {F945EA1}>
(defmethod rational-gcd ((x ratio) (y integer))
(/ (gcd (* y (denominator x))
(numerator x))
(denominator x)))
#<STANDARD-METHOD RATIONAL-GCD (RATIO INTEGER) {F986881}>
(defmethod rational-gcd ((x ratio) (y ratio))
(/ (gcd (* (numerator x) (denominator y))
(* (denominator x) (numerator y)))
(* (denominator x) (denominator y))))
#<STANDARD-METHOD RATIONAL-GCD (RATIO RATIO) {F9D1DF9}>And, let us test:
(let ((x (1+ (random 1229)))
(y (1+ (random 19123))))
(list x y (rational-gcd x y)))
(6 12258 6)
(let ((x (/ (1+ (random 1229)) (1+ (random 1230))))
(y (1+ (random 19123))))
(list x y (rational-gcd x y) (rational-gcd y x)))
(191/60 9766 1/60 1/60)
(let ((x (/ (1+ (random 8912)) (1+ (random 280))))
(y (/ (1+ (random 422)) (1+ (random 8810)))))
(list x y (rational-gcd x y)))
(3355/17 232/5861 1/99637)