Addition-chain exponentiation: Difference between revisions

=={{header|Phix}}==

=== Brute force ===

Naieve brute force search, no attempt to optimise, manages about 4 million checks/s.<br>

Replacing the recursion with an internal stack and chosen with a fixed length array might help, but

otherwise I got no good ideas at all for trimming the search space.<br>

Giving it the same length, I think, yields the same result as [[Knuth%27s_power_tree#Phix]], and at least

in the cases that I tried, somewhat faster than the method on that page.<br>

If you know the A003313 number, you can throw that at it and wait (for several billion years) or get the

power tree length and loop trying to find a path one shorter (and wait several trillion years). For the

path() and treepow() routines see link above.<br>

Note that "tries" overflows (crashes) at 1073741824, which I kept in as a deliberate limiter.

<lang Phix>atom t1 = time()+1

integer tries = 0

function addition_chain(integer target, len, sequence chosen={1})

-- target and len must be >=2

tries += 1

integer l = length(chosen),

last = chosen[$]

if last=target then return chosen end if

if l=len then

if time()>t1 then

?{"addition_chain",chosen,tries}

t1 = time()+1

end if

else

for i=l to 1 by -1 do

integer next = last+chosen[i]

if next<=target then

sequence res = addition_chain(target,len,chosen&next)

if length(res) then return res end if

end if

end for

end if

return {}

end function

-- first, some proof of correctness at the lower/trivial end:

sequence res = repeat(0,120)

res[2] = 1

for n=3 to length(res) do

integer l = length(path(n))

while true do

sequence ac = addition_chain(n,l)

if length(ac)=0 then exit end if

l = length(ac)-1

end while

res[n] = l

end for

puts(1,"The first 120 members of A003313:\n")

pp(res)

printf(1,"addition_chain(31,8):%s\n",{sprint(addition_chain(31,8))})</lang>

{{out}}

<pre>

The first 120 members of A003313:

{0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,7,5,6,6,7,6,7,

7,7,6,7,7,7,7,7,7,8,6,7,7,7,7,8,7,8,7,8,8,8,7,8,8,8,6,7,7,8,7,8,8,9,7,8,8,

8,8,8,8,9,7,8,8,8,8,8,8,9,8,9,8,9,8,9,9,9,7,8,8,8,8,9,8,9,8,9,9,9,8,9,9,9,

8,9,9,9,9,9,9,9,8}

addition_chain(31,8):{1,2,4,8,10,20,30,31}

</pre>

On the task numbers, however, as to be expected, it struggles but probably would eventually get there if the overflow on tries were removed:

<pre style="font-size: 11px">--?path(12509) -- {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,12288,12416,12480,12496,12504,12508,12509}

--?addition_chain(12509,21) -- 0s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,12288,12416,12480,12496,12504,12508,12509}

--?addition_chain(12509,20) -- 12.3s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,4160,8320,12480,12496,12504,12508,12509}

--?addition_chain(12509,19) -- 1.1s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,4160,4168,8336,12504,12508,12509}

--?addition_chain(12509,18) -- bust

--?addition_chain(12509,17) -- bust

--?path(31415) -- {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,24576,28672,30720,31232,31360,31392,31408,31412,31414,31415}

--?addition_chain(31415,25) -- 0s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,24576,28672,30720,31232,31360,31392,31408,31412,31414,31415}

--?addition_chain(31415,24) -- bust

--?addition_chain(31415,23) -- bust

--?addition_chain(31415,22) -- 137s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,10240,10368,10384,10386,20772,31158,31414,31415}

--?addition_chain(31415,21) -- 116s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,6144,6272,6288,6290,12562,25124,31414,31415}

--?addition_chain(31415,20) -- bust

--?addition_chain(31415,19) -- bust

--?path(27182) -- {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,24576,26624,27136,27168,27176,27180,27182}

--?addition_chain(27182,22) -- 0s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,24576,26624,27136,27168,27176,27180,27182}

--?addition_chain(27182,21) -- 19.4s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,8704,8712,8714,17428,26142,27166,27182}

--?addition_chain(27182,20) -- 14.2s {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,5120,5128,5640,5642,10770,21540,27182}

--?addition_chain(27182,19) -- bust

--?addition_chain(27182,18) -- bust</pre>

Once you have an addition chain, of course, apply it as per [[Knuth%27s_power_tree#Phix]]

<pre>--sequence pn = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,24576,28672,30720,31232,31360,31392,31408,31412,31414,31415}

--sequence pn = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,10240,10368,10384,10386,20772,31158,31414,31415}

--sequence pn = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,6144,6272,6288,6290,12562,25124,31414,31415}

--sequence pn = {1,2,4,8,16,17,33,49,98,196,392,784,1568,3136,6272,6289,12561,25122,31411,31415} -- (from C)

--printf(1,"%3g ^ %d (%d) = %s\n", {1.00002206445416,31415,length(pn),treepow(1.00002206445416,31415,pn)})

--1.00002 ^ 31415 (25) = 1.9999999998949602994638558

--1.00002 ^ 31415 (22) = 1.9999999998949602994638556

--1.00002 ^ 31415 (21) = 1.9999999998949602994638552

--1.00002 ^ 31415 (20) = 1.9999999998949602994638291

--sequence pn = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,24576,26624,27136,27168,27176,27180,27182}

--sequence pn = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,8704,8712,8714,17428,26142,27166,27182}

--sequence pn = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,5120,5128,5640,5642,10770,21540,27182}

--sequence pn = {1,2,4,8,10,18,28,46,92,184,212,424,848,1696,3392,6784,13568,27136,27182} -- (from C)

--printf(1,"%3g ^ %d (%d) = %s\n", {1.00002550055251,27182,length(pn),treepow(1.00002550055251,27182,pn)})

--1.00003 ^ 27182 (22) = 1.9999999999727968238298861

--1.00003 ^ 27182 (21) = 1.9999999999727968238298859

--1.00003 ^ 27182 (20) = 1.9999999999727968238298855

--1.00003 ^ 27182 (19) = 1.9999999999727968238298527</pre>