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
Additional chain 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
"""
Проверяет условия завершения рекурсии или продолжает её.
pos -- текущее количество шагов (глубина рекурсии),
seq -- текущая цепочка значений,
n -- целевое значение,
minlen -- максимальная разрешённая глубина (минимально найденная длина до этого момента).
Возвращает кортеж из:
(minimal_length_found, number_of_ways_with_that_length)
"""
function checksequence(pos, seq, n, minlen)
# If we have already exceeded the known minimum, it is not worth checking 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 -- индекс последнего элемента, который может быть слагаемым,
pos -- сколько элементов есть в текущей цепочке (длина цепочки),
seq -- сама цепочка чисел,
n -- целевое (искомое) число,
minlen -- текущая лучшая найденная длина цепочки.
Возвращает пару (лучшая_длина, число способов получить эту длину).
"""
function trypermutation(i, pos, seq, n, minlen)
if i > pos
return minlen, 0 # We haven't found 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]) # We 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("Результат с большим i меньше результата меньшей i – логически ошибочно!")
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 addition order, 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