Skip to content

Instantly share code, notes, and snippets.

Last active December 30, 2015 23:18
Show Gist options
  • Save dhedegaard/7899425 to your computer and use it in GitHub Desktop.
Save dhedegaard/7899425 to your computer and use it in GitHub Desktop.
-- Euler 72 - implemented as a postgresql 9.x function.
-- A very brute forceish approach to see how psql handles lots of data
-- in a temporary table while doing lots of calculations.
drop function if exists gcd(integer, integer);
drop function if exists euler72(integer);
create function gcd (a integer, b integer) returns integer as $$
while a <> b loop
if a > b then
a := a - b;
b := b - a;
end if;
end loop;
return a;
$$ language plpgsql;
create function euler72 (_limit integer) returns integer as $$
n integer;
d integer;
_gcd integer;
result integer;
_n integer;
_d integer;
match integer;
d := 2;
n := 1;
-- holds the fractions.
create temp table cache (
a integer not null,
b integer not null,
primary key(a, b)
-- iterate on d
while d <= _limit loop
-- show some progress
if d % 100 = 0 then
select count(*) into result from cache;
raise notice '%: %', d, result;
end if;
-- iterate on n
n := 1;
while n < d loop
-- calculate the gcd.
_gcd := gcd(n, d);
_n := n;
_d := d;
-- if gcd, divide and use the divided values.
if _gcd > 1 then
_n := _n / _gcd;
_d := _d / _gcd;
end if;
-- if n and d exists in the cache, skip.
select count(*) into match from cache where a = _n and b = _d;
if match = 0 then
-- otherwise add it to the cached.
insert into cache values (_n, _d);
end if;
n := n + 1;
end loop;
d := d + 1;
end loop;
-- Get the number of results in the cache, and return it.
select count(*) into result from cache;
drop table cache;
return result;
$$ language plpgsql;
select euler72(1000000);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment