Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

My Links

Advertisement

News

Archives

Post Categories

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 ]

Feedback

Gravatar

# 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
Gravatar

# 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 | Peso
Gravatar

# re: Greatest Common Divisor function

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

Powered by:
Powered By Subtext Powered By ASP.NET