Greatest Common Divisor
From PostgreSQL wiki
Revision as of 14:03, 27 October 2009 by Intgr
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.