Addition chains: Difference between revisions
Content deleted Content added
Added C |
|||
Line 1,080: | Line 1,080: | ||
Brauer example : [1, 2, 3, 4, 7, 10, 17, 27, 44, 88, 176, 203, 379] |
Brauer example : [1, 2, 3, 4, 7, 10, 17, 27, 44, 88, 176, 203, 379] |
||
Non-Brauer analysis suppressed |
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> |
</pre> |
||
Line 1,171: | Line 1,309: | ||
</pre> |
</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|EchoLisp}} |
{{trans|EchoLisp}} |