Есть ли практический алгоритм, который дает "цепочки умножения"
Чтобы уточнить, цель состоит в том, чтобы произвести замену умножения произвольной и точной длины
Цепочки умножения длины 1 тривиальны.
«Цепочка умножения» будет определена как 2 числа, {начало} и {множитель}, используемые в коде:
Given a pointer to array of size [{count}] // count is a parameter
a = start;
do
{
a = a * multiplier; // Really: a = (a * multiplier) MOD (power of 2
*(pointer++) = a;
}
while (a != {constant} )
// Postcondition: all {count} entries are filled.
Я хочу найти подпрограмму, которая принимает три параметра
1. Степень числа 2
2. Остановка {константа}
3. {count} — количество повторений цикла.
Подпрограмма вернет {start} и {multiplier}.
В идеале значение {Constant}, равное 0, должно быть допустимым.
Тривиальный пример:
power of 2 = 256
stopping constant = 7
number of times for the loop = 1
returns {7,1}
Нетривиальный пример:
power of 2 = 256
stopping constant = 1
number of times for the loop = 49
returns {25, 19}
Максимальное значение {count} для данной степени числа 2 может быть довольно небольшим.
Например, 2^4 (16) кажется ограниченным числом 4.