Self numbers\Phix: Difference between revisions
m (added backlink) |
m (fixed syntax colouring/replaced lang tags) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
My humiliatingly bad prior attempts at [[Self_numbers#Phix|this task]]: |
My humiliatingly bad prior attempts at [[Self_numbers#Phix|this task]]: |
||
Translation of [[Self_numbers#Go|Go]]. |
|||
{{trans|Go}} |
|||
Replacing the problematic sv[a+b+... line with a bit of dirty inline assembly improved performance by 90%<br> |
Replacing the problematic sv[a+b+... line with a bit of dirty inline assembly improved performance by 90%<br> |
||
(Of course you lose bounds checking, type checking, negative subscripts, fraction handling, and all that jazz.)<br> |
(Of course you lose bounds checking, type checking, negative subscripts, fraction handling, and all that jazz.)<br> |
||
We use a string of Y/N for the sieve to force one byte per element ('\0' and 1 would be equally valid). |
We use a string of Y/N for the sieve to force one byte per element ('\0' and 1 would be equally valid). |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>if machine_bits()=32 then crash("requires 64 bit") end if |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"requires 64 bit"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
function sieve() |
|||
string sv = repeat('N',2*1e9+9*9+1) -- (1.86GB) |
|||
integer n = 0 |
|||
for a=0 to 1 do |
|||
for b=0 to 9 do |
|||
for c=0 to 9 do |
|||
for d=0 to 9 do |
|||
for e=0 to 9 do |
|||
for f=0 to 9 do |
|||
for g=0 to 9 do |
|||
for h=0 to 9 do |
|||
for i=0 to 9 do |
|||
for j=0 to 9 do |
|||
-- n += 1 |
|||
-- sv[a+b+c+d+e+f+g+h+i+j+n] = 'Y' |
|||
#ilASM{ |
|||
[32] -- (allows clean compilation on 32 bit, before crash as above) |
|||
[64] |
|||
mov rax,[a] |
|||
mov r12,[b] |
|||
mov r13,[c] |
|||
mov r14,[d] |
|||
mov r15,[e] |
|||
add r12,r13 |
|||
add r14,r15 |
|||
add rax,r12 |
|||
mov rdi,[sv] |
|||
add rax,r14 |
|||
mov r12,[f] |
|||
mov r13,[g] |
|||
mov r14,[h] |
|||
mov r15,[i] |
|||
add r12,r13 |
|||
shl rdi,2 |
|||
mov rcx,[n] |
|||
mov r13,[j] |
|||
add r14,r15 |
|||
add rax,r12 |
|||
add rax,r14 |
|||
add r13,rcx |
|||
add rax,r13 |
|||
add rcx,1 |
|||
mov byte[rdi+rax],'Y' |
|||
mov [n],rcx } |
|||
end for |
|||
end for |
|||
end for |
|||
end for |
|||
end for |
|||
end for |
|||
end for |
|||
end for |
|||
printf(1,"%d,%d\r",{a,b}) -- (show progress) |
|||
end for |
|||
end for |
|||
return sv |
|||
end function |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">()</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">sv</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'N'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">9</span><span style="color: #0000FF;">*</span><span style="color: #000000;">9</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (1.86GB)</span> |
|||
string sv = sieve() |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
printf(1,"sieve build took %s\n",{elapsed(time()-t0)}) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
integer count = 0 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
printf(1,"The first 50 self numbers are:\n") |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
for i=1 to length(sv) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
if sv[i]='N' then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
count += 1 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
if count <= 50 then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">g</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
printf(1,"%3d ",i-1) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
if remainder(count,10)=0 then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
printf(1,"\n") |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
end if |
|||
<span style="color: #000080;font-style:italic;">-- n += 1 |
|||
end if |
|||
-- sv[a+b+c+d+e+f+g+h+i+j+n] = 'Y'</span> |
|||
if count == 1e8 then |
|||
#<span style="color: #7060A8;">ilASM</span><span style="color: #0000FF;">{</span> |
|||
printf(1,"\nThe %,dth self number is %,d (%s)\n", |
|||
<span style="color: #0000FF;">[</span><span style="color: #000000;">32</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (allows clean compilation on 32 bit, before crash as above)</span> |
|||
{count,i-1,elapsed(time()-t0)}) |
|||
<span style="color: #0000FF;">[</span><span style="color: #000000;">64</span><span style="color: #0000FF;">]</span> |
|||
exit |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">rax</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">a</span><span style="color: #0000FF;">]</span> |
|||
end if |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r12</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">]</span> |
|||
end if |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r13</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> |
|||
end for</lang> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r14</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r15</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">r12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r13</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">r14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r15</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">rax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r12</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">rdi</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">sv</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">rax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r14</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r12</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">f</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r13</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">g</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r14</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r15</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">r12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r13</span> |
|||
<span style="color: #000000;">shl</span> <span style="color: #000000;">rdi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">rcx</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">r13</span><span style="color: #0000FF;">,[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">r14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r15</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">rax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r12</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">rax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r14</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">r13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rcx</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">rax</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r13</span> |
|||
<span style="color: #000000;">add</span> <span style="color: #000000;">rcx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #000000;">byte</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rdi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">rax</span><span style="color: #0000FF;">],</span><span style="color: #008000;">'Y'</span> |
|||
<span style="color: #000000;">mov</span> <span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span><span style="color: #000000;">rcx</span> <span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d,%d\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">})</span> <span style="color: #000080;font-style:italic;">-- (show progress)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">sv</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">sv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"sieve build took %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 50 self numbers are:\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sv</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">sv</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'N'</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">50</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3d "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1e8</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nThe %,dth self number is %,d (%s)\n"</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 109: | Line 111: | ||
Only after writing this did I understand how to write a sliding sieve, which it turns out is a much better idea (see below). |
Only after writing this did I understand how to write a sliding sieve, which it turns out is a much better idea (see below). |
||
Still, this is pretty interesting and quite neat. |
Still, this is pretty interesting and quite neat. |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>integer gd = new_dict(), gdhead = 2, n = 0 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">gd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">gdhead</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
function ng(integer n) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">ng</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer r = n |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
while r do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">r</span> <span style="color: #008080;">do</span> |
|||
n += remainder(r,10) |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
r = floor(r/10) |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
return n |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function self(integer /*i*/) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">self</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000080;font-style:italic;">/*i*/</span><span style="color: #0000FF;">)</span> |
|||
-- note: assumes sequentially invoked (arg i unused) |
|||
<span style="color: #000080;font-style:italic;">-- note: assumes sequentially invoked (arg i unused)</span> |
|||
n += 1 |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
while n=gdhead do |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">gdhead</span> <span style="color: #008080;">do</span> |
|||
gdhead = pop_dict(gd)[1] |
|||
<span style="color: #000000;">gdhead</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pop_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gd</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
setd(ng(gdhead),0,gd) |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ng</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gdhead</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gd</span><span style="color: #0000FF;">)</span> |
|||
n += (n!=gdhead) |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">gdhead</span><span style="color: #0000FF;">)</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
setd(ng(n),0,gd) |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ng</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gd</span><span style="color: #0000FF;">)</span> |
|||
return n |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
printf(1,"The first 50 self numbers are:\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 50 self numbers are:\n"</span><span style="color: #0000FF;">)</span> |
|||
pp(apply(tagset(50),self),{pp_IntFmt,"%3d",pp_IntCh,false}) |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">50</span><span style="color: #0000FF;">),</span><span style="color: #000000;">self</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_IntFmt</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
|||
constant limit = 10000000 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10000000</span> |
|||
integer chk = 100 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">chk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span> |
|||
printf(1,"\n i n size time\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n i n size time\n"</span><span style="color: #0000FF;">)</span> |
|||
for i=51 to limit do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">51</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
|||
n = self(i) |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">self</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
if i=chk then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">chk</span> <span style="color: #008080;">then</span> |
|||
printf(1,"%,11d %,11d %6d %s\n",{i,n,dict_size(gd),elapsed(time()-t0)}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,11d %,11d %6d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gd</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
chk *= 10 |
|||
<span style="color: #000000;">chk</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"\nEstimated time for %,d :%s\n",{1e8,elapsed((time()-t0)*1e8/limit)})</lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nEstimated time for %,d :%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1e8</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">((</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">1e8</span><span style="color: #0000FF;">/</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 169: | Line 173: | ||
Mid-speed, perhaps helped by a slightly smarter way of calculating/updating the digit sums<br> |
Mid-speed, perhaps helped by a slightly smarter way of calculating/updating the digit sums<br> |
||
Similar to some other entries, we (only) need a sieve of 9*9, +1 here as I test an entry after the slide. |
Similar to some other entries, we (only) need a sieve of 9*9, +1 here as I test an entry after the slide. |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>--sequence sieve = repeat(0,82), -- (~25% slower) |
|||
sequence sieve = repeat(0, |
<span style="color: #000080;font-style:italic;">--sequence sieve = repeat(0,82), -- (~25% slower)</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sieve</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8192</span><span style="color: #0000FF;">),</span> |
|||
digits = repeat(0,10) |
|||
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
integer offset = 0, |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">offset</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> |
|||
digit_sum = 0, |
|||
<span style="color: #000000;">digit_sum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> |
|||
n = 0 |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
procedure next_self() |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">next_self</span><span style="color: #0000FF;">()</span> |
|||
while true do |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
n += 1 |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
for i=length(digits) to 1 by -1 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
integer d = digits[i] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
if d!=9 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">9</span> <span style="color: #008080;">then</span> |
|||
digits[i] = d+1 |
|||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
|||
digit_sum += 1 |
|||
<span style="color: #000000;">digit_sum</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
exit |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
digits[i] = 0 |
|||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
digit_sum -= 9 |
|||
<span style="color: #000000;">digit_sum</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">9</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
integer k = n+digit_sum-offset |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">digit_sum</span><span style="color: #0000FF;">-</span><span style="color: #000000;">offset</span> |
|||
if k>length(sieve) then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sieve</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
integer j = 1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
for i=n-offset to length(sieve) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">offset</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sieve</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
sieve[j] = sieve[i] |
|||
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
j += 1 |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
sieve[j..$] = 0 |
|||
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">..$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
offset = n-1 |
|||
<span style="color: #000000;">offset</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
k = digit_sum+1 |
|||
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digit_sum</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
sieve[k] = 1 |
|||
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
if sieve[n-offset]=0 then exit end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
-- (result in n) |
|||
<span style="color: #000080;font-style:italic;">-- (result in n)</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
constant limit = 100000000 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100000000</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
printf(1,"The first 50 self numbers are:\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 50 self numbers are:\n"</span><span style="color: #0000FF;">)</span> |
|||
integer chk = 100 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">chk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">100</span> |
|||
for i=1 to limit do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
|||
next_self() |
|||
<span style="color: #000000;">next_self</span><span style="color: #0000FF;">()</span> |
|||
if i<=50 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">50</span> <span style="color: #008080;">then</span> |
|||
printf(1," %3d%s",{n,iff(mod(i,25)=0?"\n":"")}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %3d%s"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)})</span> |
|||
elsif i=chk then |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">chk</span> <span style="color: #008080;">then</span> |
|||
if chk=100 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">chk</span><span style="color: #0000FF;">=</span><span style="color: #000000;">100</span> <span style="color: #008080;">then</span> |
|||
printf(1,"\n i n time\n") |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n i n time\n"</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
printf(1,"%,12d %,13d %s\n",{i,n,elapsed(time()-t0)}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,12d %,13d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
chk *= 10 |
|||
<span style="color: #000000;">chk</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">10</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"\nEstimated time for %,d :%s\n",{1e9,elapsed((time()-t0)*1e9/limit)})</lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nEstimated time for %,d :%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1e9</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">((</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">1e9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 03:11, 2 November 2022
My humiliatingly bad prior attempts at this task:
Translation of Go.
Replacing the problematic sv[a+b+... line with a bit of dirty inline assembly improved performance by 90%
(Of course you lose bounds checking, type checking, negative subscripts, fraction handling, and all that jazz.)
We use a string of Y/N for the sieve to force one byte per element ('\0' and 1 would be equally valid).
if machine_bits()=32 then crash("requires 64 bit") end if function sieve() string sv = repeat('N',2*1e9+9*9+1) -- (1.86GB) integer n = 0 for a=0 to 1 do for b=0 to 9 do for c=0 to 9 do for d=0 to 9 do for e=0 to 9 do for f=0 to 9 do for g=0 to 9 do for h=0 to 9 do for i=0 to 9 do for j=0 to 9 do -- n += 1 -- sv[a+b+c+d+e+f+g+h+i+j+n] = 'Y' #ilASM{ [32] -- (allows clean compilation on 32 bit, before crash as above) [64] mov rax,[a] mov r12,[b] mov r13,[c] mov r14,[d] mov r15,[e] add r12,r13 add r14,r15 add rax,r12 mov rdi,[sv] add rax,r14 mov r12,[f] mov r13,[g] mov r14,[h] mov r15,[i] add r12,r13 shl rdi,2 mov rcx,[n] mov r13,[j] add r14,r15 add rax,r12 add rax,r14 add r13,rcx add rax,r13 add rcx,1 mov byte[rdi+rax],'Y' mov [n],rcx } end for end for end for end for end for end for end for end for printf(1,"%d,%d\r",{a,b}) -- (show progress) end for end for return sv end function atom t0 = time() string sv = sieve() printf(1,"sieve build took %s\n",{elapsed(time()-t0)}) integer count = 0 printf(1,"The first 50 self numbers are:\n") for i=1 to length(sv) do if sv[i]='N' then count += 1 if count <= 50 then printf(1,"%3d ",i-1) if remainder(count,10)=0 then printf(1,"\n") end if end if if count == 1e8 then printf(1,"\nThe %,dth self number is %,d (%s)\n", {count,i-1,elapsed(time()-t0)}) exit end if end if end for
- Output:
sieve build took 6.6s The first 50 self numbers are: 1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468 The 100,000,000th self number is 1,022,727,208 (11.0s)
generator dictionary
While this is dog-slow (see shocking estimate below), it is interesting to note that even by the time it generates the
10,000,000th number, it is only having to juggle a mere 27 generators.
Just a shame that we had to push over 10,000,000 generators onto that stack, and tried to push quite a few more.
Memory use is pretty low, around ~4MB.
[unlike the above, this is perfectly happy on both 32 and 64 bit]
Long story short: this works much the same as a prime sieve, in which you only need to eliminate multiples
of previous primes. Here, you only need to eliminate digital additions of previous safe numbers.
Only after writing this did I understand how to write a sliding sieve, which it turns out is a much better idea (see below).
Still, this is pretty interesting and quite neat.
integer gd = new_dict(), gdhead = 2, n = 0 function ng(integer n) integer r = n while r do n += remainder(r,10) r = floor(r/10) end while return n end function function self(integer /*i*/) -- note: assumes sequentially invoked (arg i unused) n += 1 while n=gdhead do gdhead = pop_dict(gd)[1] setd(ng(gdhead),0,gd) n += (n!=gdhead) end while setd(ng(n),0,gd) return n end function atom t0 = time() printf(1,"The first 50 self numbers are:\n") pp(apply(tagset(50),self),{pp_IntFmt,"%3d",pp_IntCh,false}) constant limit = 10000000 integer chk = 100 printf(1,"\n i n size time\n") for i=51 to limit do n = self(i) if i=chk then printf(1,"%,11d %,11d %6d %s\n",{i,n,dict_size(gd),elapsed(time()-t0)}) chk *= 10 end if end for printf(1,"\nEstimated time for %,d :%s\n",{1e8,elapsed((time()-t0)*1e8/limit)})
- Output:
The first 50 self numbers are: { 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97,108,110,121,132,143, 154,165,176,187,198,209,211,222,233,244,255,266,277,288,299,310,312,323, 334,345,356,367,378,389,400,411,413,424,435,446,457,468} i n size time 100 973 18 0.1s 1,000 10,188 13 0.2s 10,000 102,225 10 1.0s 100,000 1,022,675 20 9.3s 1,000,000 10,227,221 17 1 minute and 37s 10,000,000 102,272,662 27 16 minutes and 40s Estimated time for 100,000,000 :2 hours, 46 minutes and 37s
For the record, I would not be at all surprised should a translation of this beat 20 minutes (for 1e8)
sliding sieve
Mid-speed, perhaps helped by a slightly smarter way of calculating/updating the digit sums
Similar to some other entries, we (only) need a sieve of 9*9, +1 here as I test an entry after the slide.
--sequence sieve = repeat(0,82), -- (~25% slower) sequence sieve = repeat(0,8192), digits = repeat(0,10) integer offset = 0, digit_sum = 0, n = 0 procedure next_self() while true do n += 1 for i=length(digits) to 1 by -1 do integer d = digits[i] if d!=9 then digits[i] = d+1 digit_sum += 1 exit end if digits[i] = 0 digit_sum -= 9 end for integer k = n+digit_sum-offset if k>length(sieve) then integer j = 1 for i=n-offset to length(sieve) do sieve[j] = sieve[i] j += 1 end for sieve[j..$] = 0 offset = n-1 k = digit_sum+1 end if sieve[k] = 1 if sieve[n-offset]=0 then exit end if end while -- (result in n) end procedure constant limit = 100000000 atom t0 = time() printf(1,"The first 50 self numbers are:\n") integer chk = 100 for i=1 to limit do next_self() if i<=50 then printf(1," %3d%s",{n,iff(mod(i,25)=0?"\n":"")}) elsif i=chk then if chk=100 then printf(1,"\n i n time\n") end if printf(1,"%,12d %,13d %s\n",{i,n,elapsed(time()-t0)}) chk *= 10 end if end for printf(1,"\nEstimated time for %,d :%s\n",{1e9,elapsed((time()-t0)*1e9/limit)})
- Output:
The first 50 self numbers are: 1 3 5 7 9 20 31 42 53 64 75 86 97 108 110 121 132 143 154 165 176 187 198 209 211 222 233 244 255 266 277 288 299 310 312 323 334 345 356 367 378 389 400 411 413 424 435 446 457 468 i n time 100 973 0.1s 1,000 10,188 0.1s 10,000 102,225 0.1s 100,000 1,022,675 0.1s 1,000,000 10,227,221 0.5s 10,000,000 102,272,662 4.5s 100,000,000 1,022,727,208 44.5s Estimated time for 1,000,000,000 :7 minutes and 25s