Rosetta Code

First perfect square in base n with n unique digits: Difference between revisions

Page Discussion

First perfect square in base n with n unique digits (view source)

Revision as of 17:53, 11 June 2021

36,072 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,921:
Partial translation of VB with bitmap idea from C++ and adopting the digit-array approach from pascal
instead of base conversion.
<!--<lang Phix>(notonline)-- demo\rosetta\PandigitalSquares.exw>
<span style="color: #000080;font-style:italic;">-- demo\rosetta\PandigitalSquares.exw</span>
include mpfr.e
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #000080;font-style:italic;">-- (mpz_set_str() currently only supports bases 2, 8, 10, and 16 under pwa/p2js)</span>
atom t0 = time()
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
constant chars = "0123456789abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz|",
<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>
use_hll_code = true
<span style="color: #008080;">constant</span> <span style="color: #000000;">chars</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"0123456789abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz|"</span><span style="color: #0000FF;">,</span>
 
<span style="color: #000000;">use_hll_code</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
function str_conv(sequence s, integer mode=+1)
-- mode of +1: eg {1,2,3} -> "123", mode of -1 the reverse.
<span style="color: #008080;">function</span> <span style="color: #000000;">str_conv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">mode</span><span style="color: #0000FF;">=+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
-- note this doesn't really care what base s/res are in.
<span style="color: #000080;font-style:italic;">-- mode of +1: eg {1,2,3} -&gt; "123", mode of -1 the reverse.
{sequence res,integer dcheck} = iff(mode=+1?{"",9}:{{},'9'})
-- note this doesn't really care what base s/res are in.</span>
for i=1 to length(s) do
<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: #004080;">integer</span> <span style="color: #000000;">dcheck</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mode</span><span style="color: #0000FF;">=+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">}:{{},</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">})</span>
integer d = s[i]
<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;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
d += mode*iff(d>dcheck?'a'-10:'0')
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
res &= d
<span style="color: #000000;">d</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">mode</span><span style="color: #0000FF;">*</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">dcheck</span><span style="color: #0000FF;">?</span><span style="color: #008000;">'a'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">10</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">d</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure do_one(integer base)
-- tabulates one base
<span style="color: #008080;">procedure</span> <span style="color: #000000;">do_one</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
integer bm1 = base-1,
<span style="color: #000080;font-style:italic;">-- tabulates one base</span>
dr = iff(and_bits(base,1) ? floor(base/2) : 0),
<span style="color: #004080;">integer</span> <span style="color: #000000;">bm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
id = 0,
<span style="color: #000000;">dr</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</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: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">:</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">),</span>
rc = 0,
<span style="color: #000000;">id</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
sdri
<span style="color: #000000;">rc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
atom st = time()
<span style="color: #000000;">sdri</span>
sequence sdr = repeat(0,bm1)
<span style="color: #004080;">atom</span> <span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
for i=0 to bm1-1 do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sdr</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;">bm1</span><span style="color: #0000FF;">)</span>
sdri = mod(i*i,bm1)
<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;">bm1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
rc += (sdri==dr)
<span style="color: #000000;">sdri</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;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bm1</span><span style="color: #0000FF;">)</span>
sdr[i+1] = iff(sdri=0 ? bm1 : sdri)
<span style="color: #000000;">rc</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">sdri</span><span style="color: #0000FF;">==</span><span style="color: #000000;">dr</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #000000;">sdr</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: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sdri</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #0000FF;">?</span> <span style="color: #000000;">bm1</span> <span style="color: #0000FF;">:</span> <span style="color: #000000;">sdri</span><span style="color: #0000FF;">)</span>
if dr>0 then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
id = base
<span style="color: #008080;">if</span> <span style="color: #000000;">dr</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
for i=1 to dr do
<span style="color: #000000;">id</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">base</span>
sdri = sdr[i+1]
<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;">dr</span> <span style="color: #008080;">do</span>
if sdri>=dr
<span style="color: #000000;">sdri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sdr</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>
and id>sdri then
<span style="color: #008080;">if</span> <span style="color: #000000;">sdri</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">dr</span>
id = sdri
<span style="color: #008080;">and</span> <span style="color: #000000;">id</span><span style="color: #0000FF;">></span><span style="color: #000000;">sdri</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">id</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sdri</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
id -= dr
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
<span style="color: #000000;">id</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">dr</span>
string sq = chars[1..base]
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if id>0 then sq = sq[1..id]&chars[id+1]&sq[id+1..$] end if
<span style="color: #004080;">string</span> <span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">base</span><span style="color: #0000FF;">]</span>
sq[1..2] = "10"
<span style="color: #008080;">if</span> <span style="color: #000000;">id</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">id</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">chars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">id</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">sq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">id</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
mpz sqz = mpz_init(),
<span style="color: #000000;">sq</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: #0000FF;">=</span> <span style="color: #008000;">"10"</span>
rtz = mpz_init(),
<span style="color: #004080;">mpz</span> <span style="color: #000000;">sqz</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
dnz = mpz_init(),
<span style="color: #000000;">rtz</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
tmp = mpz_init()
<span style="color: #000000;">dnz</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
mpz_set_str(sqz,sq,base)
<span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
mpz_sqrt(rtz,sqz)
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sq</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
mpz_add_ui(rtz,rtz,1) -- rtz = sqrt(sqz)+1
<span style="color: #7060A8;">mpz_sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">)</span>
mpz_mul_si(dnz,rtz,2)
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- rtz = sqrt(sqz)+1</span>
mpz_add_si(dnz,dnz,1) -- dnz = rtz*2+1
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
mpz_mul(sqz,rtz,rtz) -- sqz = rtz * rtz
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- dnz = rtz*2+1</span>
integer d = 1,
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- sqz = rtz * rtz</span>
inc = 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
if base>3 and rc>0 then
<span style="color: #000000;">inc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
while mpz_fdiv_ui(sqz,bm1)!=dr do
<span style="color: #008080;">if</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">></span><span style="color: #000000;">3</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rc</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
-- align sqz to dr
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_fdiv_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bm1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">dr</span> <span style="color: #008080;">do</span>
mpz_add_ui(rtz,rtz,1) -- rtz += 1
mpz_add(sqz,sqz,dnz) <span style="color: #000080;font-style:italic;">-- align sqz +=to dnzdr</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- rtz += 1</span>
mpz_add_ui(dnz,dnz,2) -- dnz += 2
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- sqz += dnz</span>
end while
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- dnz += 2</span>
inc = floor(bm1/rc)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
if inc>1 then
<span style="color: #000000;">inc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bm1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">rc</span><span style="color: #0000FF;">)</span>
mpz_mul_si(tmp,rtz,inc-2)
<span style="color: #008080;">if</span> <span style="color: #000000;">inc</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
mpz_sub_ui(tmp,tmp,1)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inc</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
mpz_add(dnz,dnz,tmp) -- dnz += rtz*(inc-2)-1
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- dnz += rtz*(inc-2)-1</span>
d = inc * inc
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
mpz_add(dnz,dnz,dnz)
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inc</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">inc</span>
mpz_add_ui(dnz,dnz,d) -- dnz += dnz + d
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- dnz += dnz + d</span>
d *= 2
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
atom mask, fullmask = power(2,base)-1 -- ie 0b111..
<span style="color: #000000;">d</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
integer icount = 0
<span style="color: #004080;">atom</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fullmask</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: #000000;">base</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- ie 0b111..</span>
mpz_set_si(tmp,d)
<span style="color: #004080;">integer</span> <span style="color: #000000;">icount</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
sequence sqi = str_conv(mpz_get_str(sqz,base), mode:=-1),
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
dni = str_conv(mpz_get_str(dnz,base), mode:=-1),
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sqi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">str_conv</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">mode</span><span style="color: #0000FF;">:=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
dti = str_conv(mpz_get_str(tmp,base), mode:=-1)
<span style="color: #000000;">dni</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">str_conv</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">mode</span><span style="color: #0000FF;">:=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
while true do
<span style="color: #000000;">dti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">str_conv</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">mode</span><span style="color: #0000FF;">:=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
if use_hll_code then
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
mask = 0
<span style="color: #008080;">if</span> <span style="color: #000000;">use_hll_code</span> <span style="color: #008080;">then</span>
for i=1 to length(sqi) do
<span style="color: #000000;">mask</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
mask = or_bits(mask,power(2,sqi[i]))
<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;">sqi</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">mask</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">or_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mask</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: #000000;">sqi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]))</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?9/0 -- see below, inline part 1
<span style="color: #008080;">else</span>
end if
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- see below, inline part 1</span>
if mask=fullmask then exit end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer carry = 0, sidx, si
<span style="color: #008080;">if</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">=</span><span style="color: #000000;">fullmask</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 use_hll_code then
<span style="color: #004080;">integer</span> <span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sidx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">si</span>
for sidx=-1 to -length(dni) by -1 do
<span style="color: #008080;">if</span> <span style="color: #000000;">use_hll_code</span> <span style="color: #008080;">then</span>
si = sqi[sidx]+dni[sidx]+carry
<span style="color: #008080;">for</span> <span style="color: #000000;">sidx</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dni</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
carry = si>=base
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sqi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">dni</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">carry</span>
sqi[sidx] = si-carry*base
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">base</span>
end for
<span style="color: #000000;">sqi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">-</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">*</span><span style="color: #000000;">base</span>
sidx += length(sqi)+1
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
while carry and sidx do
<span style="color: #000000;">sidx</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqi</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
si = sqi[sidx]+carry
<span style="color: #008080;">while</span> <span style="color: #000000;">carry</span> <span style="color: #008080;">and</span> <span style="color: #000000;">sidx</span> <span style="color: #008080;">do</span>
carry = si>=base
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sqi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">carry</span>
sqi[sidx] = si-carry*base
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">base</span>
sidx -= 1
<span style="color: #000000;">sqi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">-</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">*</span><span style="color: #000000;">base</span>
end while
<span style="color: #000000;">sidx</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
?9/0 --see below, inline part 2
<span style="color: #008080;">else</span>
end if
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">--see below, inline part 2</span>
if carry then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sqi = carry&sqi
<span style="color: #008080;">if</span> <span style="color: #000000;">carry</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">sqi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">carry</span><span style="color: #0000FF;">&</span><span style="color: #000000;">sqi</span>
carry = 0
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for sidx=-1 to -length(dti) by -1 do
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
si = dni[sidx]+dti[sidx]+carry
<span style="color: #008080;">for</span> <span style="color: #000000;">sidx</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dti</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
carry = floor(si/base)
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dni</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">dti</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">carry</span>
dni[sidx] = remainder(si,base)
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">/</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #000000;">dni</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
sidx += length(dni)+1
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
while carry and sidx do
<span style="color: #000000;">sidx</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dni</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
si = dni[sidx]+carry
<span style="color: #008080;">while</span> <span style="color: #000000;">carry</span> <span style="color: #008080;">and</span> <span style="color: #000000;">sidx</span> <span style="color: #008080;">do</span>
carry = si>=base
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dni</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">carry</span>
dni[sidx] = si-carry*base
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">base</span>
sidx -= 1
<span style="color: #000000;">dni</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sidx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">-</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">*</span><span style="color: #000000;">base</span>
end while
<span style="color: #000000;">sidx</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
if carry then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
dni = carry&dni
<span style="color: #008080;">if</span> <span style="color: #000000;">carry</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">dni</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">carry</span><span style="color: #0000FF;">&</span><span style="color: #000000;">dni</span>
icount += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #000000;">icount</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
mpz_set_si(tmp,icount)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
mpz_mul_si(tmp,tmp,inc)
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">icount</span><span style="color: #0000FF;">)</span>
mpz_add(rtz,rtz,tmp) -- rtz += icount * inc
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">inc</span><span style="color: #0000FF;">)</span>
sq = str_conv(sqi, mode:=+1)
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- rtz += icount * inc</span>
string rt = mpz_get_str(rtz,base),
<span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">str_conv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mode</span><span style="color: #0000FF;">:=+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
idstr = iff(id?sprintf("%d",id):" "),
<span style="color: #004080;">string</span> <span style="color: #000000;">rt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">),</span>
ethis = elapsed_short(time()-st),
<span style="color: #000000;">idstr</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">id</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">id</span><span style="color: #0000FF;">):</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">),</span>
etotal = elapsed_short(time()-t0)
<span style="color: #000000;">ethis</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed_short</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">st</span><span style="color: #0000FF;">),</span>
printf(1,"%3d %3d %s %18s -> %-28s %10d %8s %8s\n",
<span style="color: #000000;">etotal</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed_short</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>
{base, inc, idstr, rt, sq, icount, ethis, etotal})
<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 %3d %s %18s -&gt; %-28s %10d %8s %8s\n"</span><span style="color: #0000FF;">,</span>
{sqz,rtz,dnz,tmp} = mpz_free({sqz,rtz,dnz,tmp})
<span style="color: #0000FF;">{</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">inc</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">idstr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sq</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">icount</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ethis</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">etotal</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #0000FF;">{</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">({</span><span style="color: #000000;">sqz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rtz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dnz</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
puts(1,"base inc id root -> square" &
" test count time total\n")
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"base inc id root -&gt; square"</span> <span style="color: #0000FF;">&</span>
for base=2 to 19 do
<span style="color: #008000;">" test count time total\n"</span><span style="color: #0000FF;">)</span>
--for base=2 to 25 do
<span style="color: #008080;">for</span> <span style="color: #000000;">base</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">19</span> <span style="color: #008080;">do</span>
--for base=2 to 28 do
<span style="color: #000080;font-style:italic;">--for base=2 to 25 do
do_one(base)
--for base=2 to 28 do</span>
end for
<span style="color: #000000;">do_one</span><span style="color: #0000FF;">(</span><span style="color: #000000;">base</span><span style="color: #0000FF;">)</span>
printf(1,"completed in %s\n", {elapsed(time()-t0)})</lang>
<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;">"completed in %s\n"</span><span style="color: #0000FF;">,</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>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,818

edits

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