Created
June 1, 2022 14:35
-
-
Save youz/2884304a36baf6e63f35583675f022ec to your computer and use it in GitHub Desktop.
Spigot algorithm in SQL (for duckdb)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
drop table if exists consts; | |
drop table if exists digits; | |
create table consts as select 10000 ndigits; | |
create table digits(n int primary key, d int); | |
.timer on | |
insert into digits(n, d) | |
with recursive init(n, num, den) as ( | |
select n, 1, n+2 from (select ndigits*6/4 n from consts) | |
union all select n, 1, den-1 from init where den>2 | |
), spigot(c, n, num, den, m, p, d) as ( | |
select 0, n, num, den, case when den = 2 then 2000 else 1000 end, 0, null | |
from init | |
union all select | |
c+1 | |
, case when p=1 then n-6 else n end | |
, num, den | |
, case when p = 0 | |
then | |
case | |
when n = den+2 then m*10000 | |
when (lag(p) over (order by num desc)) = 1 | |
then m*10000 + num*((lag(m) over (order by num desc))/den) | |
else | |
m | |
end | |
else -- p = 1 | |
case when den=2 then 0 else m % (den-1) end | |
end | |
, case | |
when p=1 then 0 | |
when n = den+2 or (lag(p) over (order by num desc)) = 1 then 1 | |
else p | |
end | |
, case | |
when den=2 and p=1 then m | |
else null | |
end | |
from spigot | |
where n >= den+2 | |
) | |
select n/6, d from spigot where d is not null; | |
.timer off | |
.headers off | |
.mode csv | |
with recursive a(p, c, o) as ( | |
select 1, d/10000, '' from digits where n = 0 | |
union all select | |
a.p+1 | |
, (a.c + t.d) / 10000 | |
, printf('%04d', (a.c + t.d) % 10000) || a.o | |
from a inner join digits t on a.p = t.n | |
) | |
select c || o from a where p > (select max(n) from digits); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
drop table if exists consts; | |
drop table if exists digits; | |
create table consts as select 10000 ndigits; | |
create table digits(n int primary key, d int); | |
.timer on | |
insert into digits(n, d) | |
with recursive init(n, num, den) as ( | |
select n, n, n*2+1 from (select ndigits*14/4 n from consts) | |
union all select n, num-1, den-2 from init where num>1 | |
), spigot(c, n, num, den, m, p, d) as ( | |
select 0, n, num, den, 2000, 0, null from init | |
union all select | |
c+1 | |
, case when p=1 then n-14 else n end | |
, num, den | |
, case when p = 0 | |
then | |
case | |
when n = num then m*10000 | |
when (lag(p) over (order by num desc)) = 1 | |
then m*10000 + num*((lag(m) over (order by num desc))/den) | |
else | |
m | |
end | |
else -- p = 1 | |
case when num=1 then 0 else m % (den - 2) end | |
end | |
, case | |
when p=1 then 0 | |
when n = num or (lag(p) over (order by num desc)) = 1 then 1 | |
else p | |
end | |
, case | |
when num=1 and p=1 then m | |
else null | |
end | |
from spigot | |
where n >= num | |
) | |
select n/14, d from spigot where d is not null; | |
.timer off | |
.headers off | |
.mode csv | |
with recursive a(p, c, o) as ( | |
select 1, d/10000, '' from digits where n = 0 | |
union all select | |
a.p+1 | |
, (a.c + t.d) / 10000 | |
, printf('%04d', (a.c + t.d) % 10000) || a.o | |
from a inner join digits t on a.p = t.n | |
) | |
select c || o from a where p > (select max(n) from digits); |
Author
youz
commented
Jun 1, 2022
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment