Greatest Common Divisor of Two Rational Numbers

Description of the problem

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.

The definition

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.

Computations

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)