Self numbers: Difference between revisions
→{{header|Phix}}
(→{{header|Go}}: Added a third version based on the Pascal entry.) |
|||
Line 504:
real 0m13,252s</pre>
=={{header|Phix}}==
{{trans|Go}}
Replacing the problematic s[a+b+... line with a bit of dirty inline assembly improved performance by 90%<br>
We use a string of Y/N for the sieve to force one byte per element ('\0' and 1 would be equally valid).
<lang Phix>if machine_bits()=32 then crash("requires 64 bit") end if
function sieve()
string sv = repeat('N',2*1e9+9*9+1)
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</lang>
{{out}}
<pre>
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)
</pre>
=== 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 1,000,000 generators onto that stack, and tried to push quite a few more.
Memory use is pretty stable, around a paltry 4MB.<br>
Aside: the getd_index() check is often worth trying with phix dictionaries: if there is a high probability that
the key already exists, it will yield a win, but with a low probability it will just be unhelpful overhead.
<lang Phix>integer gd = new_dict(), g = 1, pqhead = 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)
integer nxt
n += 1
while n=pqhead do
while g<=pqhead do
nxt = ng(g)
if getd_index(nxt, gd)=NULL then -- (~25% gain)
setd(nxt,0,gd)
end if
g += 1
end while
integer waspqhead = pqhead
while true do
pqhead = pop_dict(gd)[1]
if pqhead!=waspqhead then exit end if
-- ?{"ding",waspqhead} -- 2, once only...
end while
nxt = ng(pqhead)
-- if getd_index(nxt, gd)=NULL then -- (~1% loss)
setd(nxt,0,gd)
-- end if
n += (n!=pqhead)
end while
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 = 10000-0-00
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)})</lang>
{out}
<pre>
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
</pre>
For the record, I would not be at all surprised should a translation of this beat 20 minutes (for 1e8)
=={{header|Wren}}==
| |||