Self numbers\Phix: Difference between revisions
Content added Content deleted
m (corrected a different link) |
m (fixed syntax colouring/replaced lang tags) |
||
Line 5: | Line 5: | ||
(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> |