First perfect square in base n with n unique digits: Difference between revisions
Content added Content deleted
m (→{{header|Python}}: Tidied.) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 2,921: | Line 2,921: | ||
Partial translation of VB with bitmap idea from C++ and adopting the digit-array approach from pascal |
Partial translation of VB with bitmap idea from C++ and adopting the digit-array approach from pascal |
||
instead of base conversion. |
instead of base conversion. |
||
<lang Phix>-- |
<!--<lang Phix>(notonline)--> |
||
<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} -> "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 |
|||
<span style="color: #000080;font-style:italic;">-- align sqz to dr</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 -> %-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 -> 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}} |
{{out}} |
||
<pre> |
<pre> |