Name

number_gcd — Computes the greatest common divisor.

Calling Sequence

   result = number_gcd ( m , n )
   result = number_gcd ( m , n , method )
   
   

Parameters

m :

a 1x1 matrix of floating point integers

n :

a 1x1 matrix of floating point integers

method :

a 1x1 matrix of strings, the algorithm to use (default method=euclidian)

result :

a 1x1 matrix of floating point integers, the least common multiple

Description

Returns the greatest common divisor of m and n.

The following values of method are availble.

method="euclidian"

Uses a naive Euclid's recursive algorithm.

method="brute"

Uses a brute-force method, based on systematic search for divisors.

method="binary"

Uses a naive binary recursive method. This is similar to Algorithm B in section 4.5.2 of TAO.

method="euclidianiterative"

Uses Euclid's algorithm with a loop (instead of recursive).

method="binaryiterative"

Uses binary algorithm with a loop (instead of recursive).

Examples

number_gcd ( 84 , 18 ) // 6
number_gcd ( 18 , 84 ) // 6

// With negative integers
computed = number_gcd ( 18 , -84 ) // 6

// Test all algos
algos = [
"euclidian"
"brute"
"binary"
"euclidianiterative"
"binaryiterative"
];
mprintf("  %s\n", strcat(algos," "));
for m = 1 : 20
for n = 1 : 20
msg="";
msg=msg+msprintf("gcd(%d,%d) = ",m, n);
for method = algos'
d = number_gcd (m,n,method);
msg=msg+msprintf("%s ",string(d));
end
msg=msg+msprintf("\n");
mprintf("%s\n",msg);
end
end

   

Bibliography

"The Art of Computer Programming", Volume 2, Seminumerical Algorithms, Donald Knuth, Addison-Wesley

Authors

Copyright (C) 2009 - 2010 - DIGITEO - Michael Baudin
Copyright (C) INRIA - Farid BELAHCENE