Categories

gleeful bash scripting: contrived GCD function

The greatest common divisor (gcd) of two natural numbers is the largest number that evenly divides both. For instance gcd(8, 12) is 4. There are many clever and efficient ways to calculate the gcd of two numbers on a Linux machine. The method presented here is not among them.

`#!/bin/bashgcd(){ comm -12 --nocheck-order <(factor \$1|sed 's/^[^ ]*/1/;s/ /\n/g') <(factor \$2|sed 's/^[^ ]*/1/;s/ /\n/g')|tr '\n' \*|sed 's/.\$/\n/'|bc;}gcd \$1 \$2 `

(Contrived) example:

`gcd.sh 24691357802469135780246913578 6172839450617283945061728394512345678901234567890123456789`

Which breaks down as:

 prime factors of24691357802469135780246913578 prime factors of61728394506172839450617283945 2 3 3 3 3 3 3 5 7 7 13 13 31 31 37 37 211 211 241 241 2161 2161 3607 3607 3803 3803 2906161 2906161

Multiply the factors common to both:

3 × 3 × 3 × 7 × 13 × 31 × 37 × 211 × 241 × 2161 × 3607 × 3803 × 2906161 = 12345678901234567890123456789

I’m sure someone else has used the output of factor and comm in this way before. The hard part was getting coprime numbers to output 1.

One reply on “gleeful bash scripting: contrived GCD function”

This doesn’t quite work: try

gcd 5652 8478

and it returns 18. Both 5652 & 8478 have 157 as a factor, so something’s wrong here.