Rosetta Code

Iterated digits squaring: Difference between revisions

Page Discussion

Iterated digits squaring (view source)

Revision as of 04:36, 25 May 2021

28,405 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (Modified a comment.)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,093:
=={{header|Phix}}==
{{trans|C}}
<!--<lang Phix>(phixonline)-->
<lang Phix>constant MAXINT = iff(machine_bits()=32?9007199254740992
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAXINT</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">?</span><span style="color: #000000;">53</span><span style="color: #0000FF;">:</span><span style="color: #000000;">64</span><span style="color: #0000FF;">))</span>
:9223372036854775807)
 
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
procedure main(integer limit)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sums</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;">limit</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
sequence sums = repeat(0,limit*81+1)
<span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
sums[1] = 1
<span style="color: #008080;">for</span> <span style="color: #000000;">n</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>
for n=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;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</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>
for i=n*81 to 1 by -1 do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
for j=1 to 9 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">*</span><span style="color: #000000;">j</span>
integer s = j*j
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">i</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>
if s>i then exit end if
<span style="color: #000000;">sums</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: #0000FF;">+=</span> <span style="color: #000000;">sums</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: #000000;">s</span><span style="color: #0000FF;">]</span>
sums[i+1] += sums[i+1-s]
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #004080;">atom</span> <span style="color: #000000;">count89</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
atom count89 = 0
<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;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span> <span style="color: #008080;">do</span>
for i=1 to n*81 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
integer r, digit, w = i
<span style="color: #008080;">while</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
while w!=1 do
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
r = 0
<span style="color: #008080;">while</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
while w!=0 do
<span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
digit = mod(w,10)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">*</span><span style="color: #000000;">digit</span>
r += digit*digit
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
w = floor(w/10)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">89</span> <span style="color: #008080;">then</span>
if r=89 then
<span style="color: #000000;">count89</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">sums</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>
count89 += sums[i+1]
<span style="color: #008080;">if</span> <span style="color: #000000;">count89</span><span style="color: #0000FF;">></span><span style="color: #000000;">MAXINT</span> <span style="color: #008080;">then</span>
if count89>MAXINT then
<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;">"counter overflow for 10^%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
printf(1,"counter overflow for 10^%d\n",n)
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
w = r
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<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;">"There are %d numbers from 1 to 10^%d ending with 89\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count89</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">})</span>
printf(1,"There are %d numbers from 1 to 10^%d ending with 89\n",{count89,n})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
end procedure
 
<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>
atom t0 = time()
<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span>
main(20)
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
?time()-t0</lang>
<!--</lang>-->
{{out}}
on 32 bit:
Line 2,169 ⟶ 2,170:
I realised I needed to do this in two stages.<br>
Phase 1. Make sure we can count.
<!--<lang Phix>(phixonline)-->
<lang Phix>function comb(sequence res, from, integer n, at=1, sequence chosen={})
<span style="color: #008080;">function</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
if length(chosen)=n then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
sequence digits = repeat(0,10)
<span style="color: #004080;">sequence</span> <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>
for i=1 to length(chosen) 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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
digits[chosen[i]+1]+=1
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">chosen</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: #000000;">1</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
atom p = factorial(length(chosen))
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">))</span>
for i=1 to 10 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;">10</span> <span style="color: #008080;">do</span>
if digits[i] then
<span style="color: #008080;">if</span> <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: #008080;">then</span>
p /= factorial(digits[i])
<span style="color: #000000;">p</span> <span style="color: #0000FF;">/=</span> <span style="color: #7060A8;">factorial</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>
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>
res = sq_add(res,{p,1})
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
else
<span style="color: #008080;">else</span>
for i=at to length(from) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">at</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
res = comb(res,from,n,i,append(chosen,from[i]))
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">),</span><span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]))</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return res
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
constant nums = {0,1,2,3,4,5,6,7,8,9}
<span style="color: #008080;">constant</span> <span style="color: #000000;">nums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">}</span>
for i=1 to 8 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;">8</span> <span style="color: #008080;">do</span>
?comb({0,0},nums,i)
<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;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">comb</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span><span style="color: #000000;">nums</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)})</span>
end for</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
Starting with the combinations method from http://rosettacode.org/wiki/Combinations_with_repetitions#Phix converted to a function, make sure we
are covering all the numbers correctly by checking that we have indeed found power(10,n) of them, and show we are looking at significantly fewer combinations.
Line 2,209 ⟶ 2,212:
Phase 2. Add in the rest of the logic, as suggested count 1's in preference to 89's and subtract from 10^n to get the answer.<br>
[PS There is an eerie similarity between this and the 2nd C version, but I swear it is not a copy, and I noticed that later.]
<!--<lang Phix>sequence(notonline, is1too slow)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">is1</span>
 
function comb(atom res, sequence from, integer n, at=1, sequence chosen={})
<span style="color: #008080;">function</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
if length(chosen)=n then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
sequence digits = repeat(0,10)
<span style="color: #004080;">sequence</span> <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>
atom sumsq = 0
<span style="color: #004080;">atom</span> <span style="color: #000000;">sumsq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for i=1 to length(chosen) 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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer ci = chosen[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
sumsq += ci*ci
<span style="color: #000000;">sumsq</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">ci</span><span style="color: #0000FF;">*</span><span style="color: #000000;">ci</span>
digits[ci+1]+=1
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</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>
if sumsq=0 or is1[sumsq] then
<span style="color: #008080;">if</span> <span style="color: #000000;">sumsq</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">is1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sumsq</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
atom perms = factorial(length(chosen))
<span style="color: #004080;">atom</span> <span style="color: #000000;">perms</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">))</span>
for i=1 to 10 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;">10</span> <span style="color: #008080;">do</span>
if digits[i] then
<span style="color: #008080;">if</span> <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: #008080;">then</span>
perms /= factorial(digits[i])
<span style="color: #000000;">perms</span> <span style="color: #0000FF;">/=</span> <span style="color: #7060A8;">factorial</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>
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>
res += perms
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">perms</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
else
<span style="color: #008080;">else</span>
for i=at to length(from) do
<span style="color: #000000;">chosen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">0</span>
res = comb(res,from,n,i,append(chosen,from[i]))
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">at</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
 
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
procedure setis1(integer n)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
is1 = repeat(0,n*81)
for i=1 to length(is1) do
<span style="color: #008080;">procedure</span> <span style="color: #000000;">setis1</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, digit, w = i
<span style="color: #000000;">is1</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;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span><span style="color: #0000FF;">)</span>
while 1 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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">is1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
r = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
while w!=0 do
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
digit = mod(w,10)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
r += digit*digit
<span style="color: #008080;">while</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
w = floor(w/10)
<span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
end while
<span style="color: #000000;">r</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">*</span><span style="color: #000000;">digit</span>
if r=89 then exit end if
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
if r=1 then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
is1[i] = 1
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">89</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>
exit
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">is1</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;">1</span>
w = r
<span style="color: #008080;">exit</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
constant nums = {0,1,2,3,4,5,6,7,8,9}
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
for i=1 to 16 do
atom t0 = time()
<span style="color: #008080;">constant</span> <span style="color: #000000;">nums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">}</span>
setis1(i)
<span style="color: #004080;">atom</span> <span style="color: #000000;">t00</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
printf(1,"There are %d numbers from 1 to 10^%d ending with 89 (%3.2fs)\n",{power(10,i)-comb(0,nums,i),i,time()-t0})
<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;">16</span> <span style="color: #008080;">do</span>
end for</lang>
<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: #000000;">setis1</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</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;">"There are %d numbers from 1 to 10^%d ending with 89 (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nums</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #000000;">i</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;">end</span> <span style="color: #008080;">for</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;">t00</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
Sadly, while still very much faster than brute force, several times slower than the translated from C version.
Line 2,270 ⟶ 2,279:
There are 80 numbers from 1 to 10^2 ending with 89 (0.00s)
There are 857 numbers from 1 to 10^3 ending with 89 (0.00s)
There are 8558 numbers from 1 to 10^4 ending with 89 (0.00s02s)
There are 85623 numbers from 1 to 10^5 ending with 89 (0.02s00s)
There are 856929 numbers from 1 to 10^6 ending with 89 (0.00s02s)
There are 8581146 numbers from 1 to 10^7 ending with 89 (0.02s)
There are 85744333 numbers from 1 to 10^8 ending with 89 (0.02s03s)
There are 854325192 numbers from 1 to 10^9 ending with 89 (0.05s08s)
There are 8507390852 numbers from 1 to 10^10 ending with 89 (0.09s16s)
There are 84908800643 numbers from 1 to 10^11 ending with 89 (0.17s31s)
There are 850878696414 numbers from 1 to 10^12 ending with 89 (0.34s61s)
There are 8556721999130 numbers from 1 to 10^13 ending with 89 (01.58s16s)
There are 86229146720315 numbers from 1 to 10^14 ending with 89 (02.92s16s)
There are 869339034137667 numbers from 1 to 10^15 ending with 89 (13.66s77s)
There are 87547808827393378754780882739336 numbers from 1 to 10^16 ending with 89 (26.75s59s)
"15s"
</pre>
 
Petelomax
7,805

edits

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