Additive chain algorithms in Julia language
In this example, we consider the implementation of an algorithm for finding the minimum length of an additive chain for given numbers in the Julia programming language.
Introduction
The additive chain algorithm solves the problem of finding the smallest number of steps necessary to obtain the target number, starting from one, where each subsequent member of the chain is equal to the sum of the two previous members of the same chain.
This is a classic problem in number theory and has applications in optimizing exponentiation, computing in cryptography, as well as in analyzing the complexity of certain algorithms.
The theoretical part
Additive цепочка lengths for It is a sequence of , such as . Each element is the sum of two previous terms, not necessarily distinguishable.
Brower's Chain for is a chain of addition, where . Each element uses the previous element as a summand.
In this example, we are interested in chains of minimal length. .
Task
For everyone output the following:
-
,
-
number of Brower length chains .
Function trypermutation
Function trypermutation recursively builds all possible sequences of such sums, trying to achieve the goal in the minimum number of steps. This is done by going through all the possible combinations (permutations).
The main part
The function of checking the current state of the sequence — checksequence
"""
Checks the conditions for completion of the recursion or continues it.
pos -- current number of steps (recursion depth),
seq -- the current value chain,
n -- target value,
minlen is the maximum allowed depth (the minimum length found up to this point).
Returns a tuple of:
(minimal_length_found, number_of_ways_with_that_length)
"""
function checksequence(pos, seq, n, minlen)
# If we have already exceeded the known minimum, we should not check further.
pos > minlen || seq[1] > n ? (minlen, 0) :
# If the first value is greater than N, the chain is no good.
seq[1] == n ? (pos, 1) : # We have reached the goal! We return the number of steps and one found chain.
# If you haven't reached the maximum yet, but you can continue to iterate.:
pos < minlen ? trypermutation(0, pos, seq, n, minlen) : (minlen, 0) # Otherwise, they stepped over anyway
end
Recursive function of trying all valid permutations — trypermutation
"""
trypermutation(i, pos, seq, n, minlen)
i is the index of the last element, which can be a summand,
pos -- how many items are in the current chain (chain length),
seq -- the string of numbers itself,
n is the target (desired) number,
minlen is the current best found chain length.
Returns a pair (best_line, the number of ways to get this length).
"""
function trypermutation(i, pos, seq, n, minlen)
if i > pos
return minlen, 0 # We didn't find anything new, so we're just returning the minimum.
end
new_seq = deepcopy(seq) # Creating a copy of the chain
pushfirst!(new_seq, seq[1] + seq[i+1]) # Adding a new number to the beginning (on the left): a[j] = a[1]+a[i+1]
res1 = checksequence(pos + 1, new_seq, n, minlen) # We check the received chain further
res2 = trypermutation(i + 1, pos, seq, n, res1[1]) # Let's try another option i -> i+1
# Choosing the best result:
if res2[1] < res1[1]
return res2
elseif res2[1] == res1[1]
return res2[1], res1[2] + res2[2] # If it is equal, we add up the number of paths.
else
error("The result with a large i is less than the result with a smaller i – logically wrong!")
end
end
Main program: output of results for a set of numbers
A set of test numbers: for each of them, the minimum length of the additive chain will be found.
for num in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
(minlen, nchains) = trypermutation(0, 0, [1], num, 12) # The starting chain is [1]; the maximum allowed length is 12
println("N = ", num)
println("Minimum chain length: L(n) = ", minlen)
println("The number of chains of this length (Brower's number): ", nchains)
end
How does the main loop work?
For each number in the list, the following is performed:
- Recursive iteration is started.
trypermutation, starting from the starting chain[1]. - Recursion generates all possible sequences by adding a new term as the sum of any two existing ones.
- Function
checksequencetracks the achievement of the desired value (== n) and fixes if the new chain is shorter than the current one. - At the end of the iteration, two numbers are output for each input:
L(n)— minimum length of the additive chain;- The number of minimal Brower chains (with different order of addition, but the same length).
Conclusion
We have reviewed the implementation of the algorithm for constructing minimal additive chains using the full iteration method using recursion in the Julia environment. For a set of numbers, the minimum lengths of the corresponding chains were found and the number of such chains (the so-called Brower chains) was calculated. This technique is useful, for example, for efficient algorithms for fast exponentiation and analysis of the complexity of operations in cryptographic systems.
The example was developed using materials from Rosetta Code