Оптимальность алгоритма бинарного возведения в степень
Добавлено: 19 июн 2018, 13:18
В питере задали на экзамене: вычислить [math] при помощи не более чем 7 умножений.
С 8 ясно, вычислить 2,4....32 степень и согласно двоичному разложению 43 некоторые перемножить.
UPD. oeis тоже говорит, что за 7 возможно
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7[math]
но не говорит как) http://oeis.org/A003313
С 8 ясно, вычислить 2,4....32 степень и согласно двоичному разложению 43 некоторые перемножить.
UPD. oeis тоже говорит, что за 7 возможно
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7[math]
но не говорит как) http://oeis.org/A003313