Self numbers: Difference between revisions
Content added Content deleted
(→{{header|Go}}: Added a third version based on the Pascal entry.) |
|||
Line 504: | Line 504: | ||
real 0m13,252s</pre> |
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}}== |
=={{header|Wren}}== |