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
"""
Проверяет условия завершения рекурсии или продолжает её.
pos -- текущее количество шагов (глубина рекурсии),
seq -- текущая цепочка значений,
n -- целевое значение,
minlen -- максимальная разрешённая глубина (минимально найденная длина до этого момента).
Возвращает кортеж из:
(minimal_length_found, number_of_ways_with_that_length)
"""
function checksequence(pos, seq, n, minlen)
# Если мы уже превысили известный минимум – дальше не стоит проверять
pos > minlen || seq[1] > n ? (minlen, 0) :
# Если первое значение стало больше N – цепочка не годится
seq[1] == n ? (pos, 1) : # Мы достигли цели! Возвращаем кол-во шагов и одну найденную цепочку
# Если ещё не достигли максимума, но можно продолжать перебирать:
pos < minlen ? trypermutation(0, pos, seq, n, minlen) : (minlen, 0) # Иначе всё равно перешагнули
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 # Ничего нового не нашлось – просто возвращаем минимум
end
new_seq = deepcopy(seq) # Создаём копию цепочки
pushfirst!(new_seq, seq[1] + seq[i+1]) # Добавляем новое число в начало (слева): a[j] = a[1]+a[i+1]
res1 = checksequence(pos + 1, new_seq, n, minlen) # Проверяем полученную цепочку дальше
res2 = trypermutation(i + 1, pos, seq, n, res1[1]) # Пробуем другой вариант i -> i+1
# Выбираем наилучший результат:
if res2[1] < res1[1]
return res2
elseif res2[1] == res1[1]
return res2[1], res1[2] + res2[2] # Если равно — складываем количества путей
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) # Стартовая цепочка — [1]; максимальная допустимая длина — 12
println("N = ", num)
println("Минимальная длина цепочек: L(n) = ", minlen)
println("Количество цепочек такой длины (число Брауэра): ", 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 an 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