Version 0 of Greatest common denominator

Updated 2002-01-23 07:24:01

(moved out of the Bag of algorithms) - RS started this with:

  proc gcd {p q} {
     while {1} {
        if {$p==$q} {
            # Termination case
            return $p
        } elseif {$p>$q} {
            # Swap p and q
            set t $p
            set p $q
            set q $t
        }
        # Work out q%p ('cos we're looping...)
        incr q [expr {-$p}]
     }
  } ;#RS, with recursion removed by DKF

It is simpler and faster to use % (reminder) instead of decrementing. (Consider what happens when the above tries to compute the GCD of 1000 and 10.) Furthermore the above control structures can be greatly simplified:

  proc gcd {p q} {
     set p [expr {abs($p)}]
     set q [expr {abs($q)}]
     while {$q != 0} {
        set r [expr {$p % $q}]
        set p $q
        set q $r
     }
     set p
  }

There is however an even shorter way of doing it:

  proc gcd {p q} {
     set p [expr {abs($p)}]
     set q [expr {abs($q)}]
     while {$q != 0} {set q [expr {$p % [set p $q]}]}
     set p
  }

/Lars Hellstr�m

---

Cameron Laird wrote in the comp.lang.tcl newsgroup: Simpler:

  proc gcd {a b} {
     if {$b==0} {
        return $a
     }
     gcd $b [expr {$a % $b}]
  }

You can also do it iteratively, with arbitrary-precision integers, ...

Tom Poindexter added: ... e.g., by using Mpexpr, it's a one-liner:

 % package require Mpexpr
 1.0
 % mpformat %r [mpexpr 60/100.0]
 3/5

Mpexpr: http://www.NeoSoft.com/tcl/ftparchive/sorted/math/Mpexpr-1.0/

---

Category Mathematics - Arts and crafts of Tcl-Tk programming