Peter Larsson Blog

Patron Saint of Lost Yaks

Greatest Common Divisor function

by Peter Larsson in  , , ,

This approach is not dependent on the 32-level recursion as most other algorithms are for this problem.

CREATE FUNCTION dbo.fnGCD
(
            @a INT,
            @b INT
)
RETURNS INT
AS
BEGIN
            DECLARE     @c INT
 
            IF @a IS NULL OR @b IS NULL OR (@a = 0 AND @b = 0)
                         RETURN NULL
 
            IF @a = 0 OR @b = 0
                         RETURN ABS(@a) + ABS(@b)
 
            IF ABS(@a) < ABS(@b)
                         SELECT      @c = ABS(@a),
                                     @a = ABS(@b),
                                     @b = @c
            ELSE
                         SELECT      @a = ABS(@a),
                                     @b = ABS(@b)
 
            SET         @c = @a % @b
 
            WHILE @c > 0
                         SELECT      @a = @b,
                                     @b = @c,
                                     @c = @a % @b
 
            RETURN      @b
END

Legacy Comments
RBarryYoung
2009-04-15		 re: Greatest Common Divisor function
That's the iterative version of the chinese remainder algorithim, isn't it Peso?
Peso
2009-04-15		 re: Greatest Common Divisor function
I think it's commonly called Eucliden, but if the chinese people were first I can't tell...
Peso
2009-04-15		 re: Greatest Common Divisor function
Also see http://en.wikipedia.org/wiki/Euclidean_algorithm