Addition chains: Difference between revisions
→{{header|Phix}}
(Added C) |
|||
Line 1,080:
Brauer example : [1, 2, 3, 4, 7, 10, 17, 27, 44, 88, 176, 203, 379]
Non-Brauer analysis suppressed
</pre>
=={{header|Phix}}==
Modification of [[Addition-chain_exponentiation#Phix]], which probably will be faster if you already know l(n) and only want one (Brauer).<br>
Note the internal values of l(n) are [consistently] +1 compared to what the rest of the world says.
<lang Phix>constant nums = {7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}
constant maxlen = 13
constant max_non_brauer = 379
function isBrauer(sequence a)
-- translated from Go
for i=3 to length(a) do
bool ok = false
for j=i-1 to 1 by -1 do
if a[i-1]+a[j] == a[i] then
ok = true
exit
end if
end for
if not ok then
return false
end if
end for
return true
end function
integer last_lm = 0
procedure progress(string m)
puts(1,m&repeat(' ',max(0,last_lm-length(m)))&"\r")
last_lm = length(m)
end procedure
integer brauer_count,
non_brauer_count
sequence brauer_example,
non_brauer_example
atom t1 = time()+1
atom tries = 0
function addition_chains(integer target, len, sequence chosen={1})
-- nb: target and len must be >=2
tries += 1
integer l = length(chosen),
last = chosen[l]
if last=target then
if l<len then
brauer_count = 0
non_brauer_count = 0
end if
if isBrauer(chosen) then
brauer_count += 1
brauer_example = chosen
else
non_brauer_count += 1
non_brauer_example = chosen
end if
return l
end if
if l=len then
if time()>t1 then
progress(sprintf("working... %s, %,d permutations",{sprint(chosen[1..l]),tries}))
t1 = time()+1
end if
elsif target>max_non_brauer then
for i=l to 1 by -1 do
integer next = last+chosen[i]
if next<=target and next>chosen[$] and i<=len then
len = addition_chains(target,len,chosen&next)
end if
end for
else
sequence ndone = {} -- if chosen was {1,2,4,5}, don't recurse {1,2,4,5,6} twice,
-- once because 5+1=6, and again because 4+2=6, or similar.
while true do
for i=l to 1 by -1 do
integer next = last+chosen[i]
if next<=target and next>chosen[$] and i<=len and not find(next,ndone) then
ndone = append(ndone,next)
len = addition_chains(target,len,chosen&next)
end if
end for
l -= 1
if l=0 then exit end if
last = chosen[l]
end while
end if
return len
end function
printf(1,"Searching for Brauer chains up to a minimum length of %d:\n",{maxlen-1})
for i=1 to length(nums) do
atom t = time()
brauer_count = 0
brauer_example = {}
non_brauer_count = 0
integer num = nums[i],
l = addition_chains(num,13)
integer bc = brauer_count,
nbc = non_brauer_count
string bs = iff(bc?" eg "&sprint(brauer_example)&",":""),
ns = iff(nbc?" eg "&sprint(non_brauer_example)&",":""),
e = elapsed_short(time()-t)
progress("") -- (wipe it clean)
printf(1,"l(%d) = %d, Brauer:%d,%s Non-Brauer:%d,%s (%s, %d perms)\n",{num,l-1,bc,bs,nbc,ns,e,tries})
end for</lang>
{{out}}
<pre>
Searching for Brauer chains up to a minimum length of 12:
l(7) = 4, Brauer:5, eg {1,2,3,4,7}, Non-Brauer:0, (0s, 18 perms)
l(14) = 5, Brauer:14, eg {1,2,3,4,7,14}, Non-Brauer:0, (0s, 153 perms)
l(21) = 6, Brauer:26, eg {1,2,3,4,7,14,21}, Non-Brauer:3, eg {1,2,4,5,8,13,21}, (0s, 1014 perms)
l(29) = 7, Brauer:114, eg {1,2,3,4,7,11,18,29}, Non-Brauer:18, eg {1,2,3,6,9,11,18,29}, (0s, 7610 perms)
l(32) = 5, Brauer:1, eg {1,2,4,8,16,32}, Non-Brauer:0, (0s, 7780 perms)
l(42) = 7, Brauer:78, eg {1,2,3,4,7,14,21,42}, Non-Brauer:6, eg {1,2,4,5,8,13,21,42}, (0s, 15935 perms)
l(64) = 6, Brauer:1, eg {1,2,4,8,16,32,64}, Non-Brauer:0, (0s, 17018 perms)
l(47) = 8, Brauer:183, eg {1,2,3,4,7,10,20,27,47}, Non-Brauer:37, eg {1,2,3,5,7,14,19,28,47}, (0s, 105418 perms)
l(79) = 9, Brauer:492, eg {1,2,3,4,7,9,18,36,43,79}, Non-Brauer:129, eg {1,2,3,5,7,12,24,31,48,79}, (0s, 998358 perms)
l(191) = 11, Brauer:7172, eg {1,2,3,4,7,8,15,22,44,88,103,191}, Non-Brauer:2615, eg {1,2,3,4,7,9,14,23,46,92,99,191}, (1:41, 174071925 perms)
l(382) = 11, Brauer:4, eg {1,2,4,5,9,14,23,46,92,184,198,382}, Non-Brauer:0, (2:53, 467243477 perms)
l(379) = 12, Brauer:6583, eg {1,2,3,4,7,10,17,27,44,88,176,203,379}, Non-Brauer:2493, eg {1,2,3,4,7,14,17,31,62,124,131,248,379}, (29:45, 3349176887 perms)
</pre>
For comparison with the Kotlin timings, setting the constant max_non_brauer to 79 yields the following
(making it about 20% slower than the Go submission above, on the same box)
<pre>
Searching for Brauer chains up to a minimum length of 12:
l(7) = 4, Brauer:5, eg {1,2,3,4,7}, Non-Brauer:0, (0s, 18 perms)
l(14) = 5, Brauer:14, eg {1,2,3,4,7,14}, Non-Brauer:0, (0s, 153 perms)
l(21) = 6, Brauer:26, eg {1,2,3,4,7,14,21}, Non-Brauer:3, eg {1,2,4,5,8,13,21}, (0s, 1014 perms)
l(29) = 7, Brauer:114, eg {1,2,3,4,7,11,18,29}, Non-Brauer:18, eg {1,2,3,6,9,11,18,29}, (0s, 7610 perms)
l(32) = 5, Brauer:1, eg {1,2,4,8,16,32}, Non-Brauer:0, (0s, 7780 perms)
l(42) = 7, Brauer:78, eg {1,2,3,4,7,14,21,42}, Non-Brauer:6, eg {1,2,4,5,8,13,21,42}, (0s, 15935 perms)
l(64) = 6, Brauer:1, eg {1,2,4,8,16,32,64}, Non-Brauer:0, (0s, 17018 perms)
l(47) = 8, Brauer:183, eg {1,2,3,4,7,10,20,27,47}, Non-Brauer:37, eg {1,2,3,5,7,14,19,28,47}, (0s, 105418 perms)
l(79) = 9, Brauer:492, eg {1,2,3,4,7,9,18,36,43,79}, Non-Brauer:129, eg {1,2,3,5,7,12,24,31,48,79}, (0s, 998358 perms)
l(191) = 11, Brauer:7172, eg {1,2,3,4,7,8,15,22,44,88,103,191}, Non-Brauer:0, (11s, 43748038 perms)
l(382) = 11, Brauer:4, eg {1,2,4,5,9,14,23,46,92,184,198,382}, Non-Brauer:0, (17s, 103474842 perms)
l(379) = 12, Brauer:6583, eg {1,2,3,4,7,10,17,27,44,88,176,203,379}, Non-Brauer:0, (2:19, 622842429 perms)
</pre>
Line 1,171 ⟶ 1,309:
</pre>
=={{header|zkl}}==
{{trans|EchoLisp}}
| |||