2011-03-25

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

2 comments:

  1. and the udag?

    kind of

    select deptno, gcd(sal) from emp group by deptno

    ;-)

    ReplyDelete
  2. U mean user defined aggregate function? Not impossible. Maybe another post later with that topic.

    ReplyDelete

About Me

My photo
I am Timo Raitalaakso. I have been working since 2001 at Solita Oy as a Senior Database Specialist. I have received Oracle ACE nomination. My main focus is on projects involving Oracle database. In this Rafu on db blog I write some interesting issues that evolves from my interaction with databases. Mainly Oracle.