Rosetta Code

Self numbers\Phix: Difference between revisions

Page Discussion

Self numbers\Phix (view source)

Revision as of 03:11, 2 November 2022

33,381 bytes added ,  1 year ago
m
fixed syntax colouring/replaced lang tags
m (corrected a different link)
m (fixed syntax colouring/replaced lang tags)
 
Line 5:
(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).
<!--<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}}
<pre>
Line 109 ⟶ 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).
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}}
<pre>
Line 169 ⟶ 173:
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>--sequence sieve = repeat(0,82), -- (~25% slower)
<span style="color: #000080;font-style:italic;">--sequence sieve = repeat(0,819282), -- (~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
end if <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}}
<pre>
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/333057"