# Thinking outside the box

Patron Saint of Lost Yaks

## Greatest Common Divisor function

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

Print | posted on Wednesday, April 15, 2009 10:17 AM | Filed Under [ SQL Server 2008 Algorithms SQL Server 2005 SQL Server 2000 ]

## #re: Greatest Common Divisor function

That's the iterative version of the chinese remainder algorithim, isn't it Peso?
4/15/2009 8:19 PM | RBarryYoung

## #re: Greatest Common Divisor function

I think it's commonly called Eucliden, but if the chinese people were first I can't tell...
4/15/2009 8:21 PM |

## #re: Greatest Common Divisor function

Also see http://en.wikipedia.org/wiki/Euclidean_algorithm
4/15/2009 8:24 PM |
Comments have been closed on this topic.