Greatest Common Divisor

From PostgreSQL wiki

Revision as of 14:03, 27 October 2009 by Intgr (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Library Snippets

Greatest Common Divison

Works with PostgreSQL

8.4

Written in

SQL

Depends on

Nothing


Using a CTE, the calculation of greatest common divisor (gcd) is trivial.

CREATE OR REPLACE FUNCTION gcd( a bigint,  b bigint)
RETURNS bigint
IMMUTABLE
STRICT
LANGUAGE SQL
AS $$
WITH RECURSIVE t(a,b) AS (
    VALUES (abs($1)::bigint, abs($2)::bigint)
UNION ALL
    SELECT b, mod(a,b) FROM t
    WHERE b > 0
)
SELECT a FROM t WHERE b = 0
$$;

Thanks to David Fetter for this query. Thanks to Pasha Golub for the faster, more correct version.

Personal tools