Greatest Common Divisor

Need a greatest common divisor function? Vadim Tropashko has written a SQL implementation of such. Here it is wrapped inside a function.

create or replace function greatest_common_div(n1 number, n2 number) 
return number 
as
ret number;
begin
with NumberSet as ( 
select column_value Element from table(sys.odcinumberlist( n1, n2 ))
), Integers as (
select level num# from dual connect by level <= least( n1, n2 )
)
select max(Divisor) into ret 
from (
  select Divisor
    from (
    select num# as Divisor from Integers 
    where num# <= (select min(Element) from NumberSet)
  ), NumberSet 
  where mod(Element, Divisor)=0
  group by Divisor
 having count(*) = (select count(*) from NumberSet)
);
return ret;
end;
/


select greatest_common_div(15,123) from dual;

3

And a 11.2 version. Idea borrowed from http://wiki.postgresql.org. This is a better performing one as it handles only two numbers.

create or replace function greatest_common_div2(n1 number, n2 number) 
return number 
as
ret number;
begin
WITH t(a,b) AS (
    select n1, n2 from dual
UNION ALL
    SELECT b, mod(a,b) FROM t
    WHERE b > 0
)
SELECT a into ret
  FROM t 
 WHERE b = 0
;
return ret;
end;
/

And the same without pl/sql to sql context switch. Added 12.9.2011

create or replace function greatest_common_div3(n1 number, n2 number) 
return number 
as
ret number;
begin
ret := n1;
if (n2 != 0) then 
 ret := greatest_common_div3(n2,mod(n1,n2));
end if;
return ret;
end;
/

with numbers as (select level num from dual connect by level < 100)
, test as (
select a.num a
     , b.num b
     , greatest_common_div(a.num,b.num) gcd
     , greatest_common_div2(a.num,b.num) gcd2
     , greatest_common_div3(a.num,b.num) gcd3
 from numbers a, numbers b
)
select * from test where gcd!=gcd2 or gcd!=gcd3
;

Update 28.3.2011
Added an user defined aggregate also.

CREATE OR REPLACE TYPE t_gcd_agg AS OBJECT
(
  g_number  number,
  STATIC FUNCTION ODCIAggregateInitialize(sctx  IN OUT  t_gcd_agg)
    RETURN NUMBER,
  MEMBER FUNCTION ODCIAggregateIterate(self   IN OUT  t_gcd_agg,
                                       value  IN      number )
     RETURN NUMBER,
  MEMBER FUNCTION ODCIAggregateTerminate(self         IN   t_gcd_agg,
                                         returnValue  OUT  number,
                                         flags        IN   NUMBER)
    RETURN NUMBER,
  MEMBER FUNCTION ODCIAggregateMerge(self  IN OUT  t_gcd_agg,
                                     ctx2  IN      t_gcd_agg)
    RETURN NUMBER
);
/

CREATE OR REPLACE TYPE BODY t_gcd_agg IS
  STATIC FUNCTION ODCIAggregateInitialize(sctx  IN OUT  t_gcd_agg)
    RETURN NUMBER IS
  BEGIN
    sctx := t_gcd_agg(NULL);
    RETURN ODCIConst.Success;
  END;
  MEMBER FUNCTION ODCIAggregateIterate(self   IN OUT  t_gcd_agg,
                                       value  IN      number )
    RETURN NUMBER IS
  BEGIN
    SELF.g_number := greatest_common_div3(case when self.g_number is null then value else self.g_number end, value);
    RETURN ODCIConst.Success;
  END;
  MEMBER FUNCTION ODCIAggregateTerminate(self         IN   t_gcd_agg,
                                         returnValue  OUT  number,
                                         flags        IN   NUMBER)
    RETURN NUMBER IS
  BEGIN
    returnValue := SELF.g_number;
    RETURN ODCIConst.Success;
  END;
  MEMBER FUNCTION ODCIAggregateMerge(self  IN OUT  t_gcd_agg,
                                     ctx2  IN      t_gcd_agg)
    RETURN NUMBER IS
  BEGIN
    SELF.g_number := greatest_common_div3(case when self.g_number is null then ctx2.g_number else self.g_number end
                                        , case when ctx2.g_number is null then self.g_number else ctx2.g_number end);
    RETURN ODCIConst.Success;
  END;
END;
/

CREATE OR REPLACE FUNCTION gcd (p_input VARCHAR2)
RETURN VARCHAR2
PARALLEL_ENABLE AGGREGATE USING t_gcd_agg;
/

select gcd(column_value) from table(sys.odcinumberlist(4,8,34));

2

with test as (
select 'a' a, 4 n from dual union all
select 'a' a, 6 n from dual union all
select 'b' a, 30 n from dual union all
select 'b' a, 60 n from dual union all
select 'b' a, 96 n from dual
)
select a,gcd(n) 
from test 
group by a;

a 2
b 6