Страница 1 из 1

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 19 июн 2018, 13:18
Ian
В питере задали на экзамене: вычислить [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

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 19 июн 2018, 18:45
zykov
Ian писал(а):Source of the post но не говорит как) http://oeis.org/A003313

Там по ссылке есть дерево глубины 5 (в "example"). Из него видно, что 43=20+20+3. Эти два сложения плюс пять сложений для получения 20 (3 получается в процессе) дают семь сложений.
20=10+10
10=5+5
5=3+2
3=2+1
2=1+1

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 19 июн 2018, 18:48
zykov
Думаю, школьник для решения должен начать строить это дерево от 1. Достаточно 3 уровней. После достижения 5 уже очевидно - 5*8+3.

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 19 июн 2018, 21:09
Ian
zykov писал(а):Думаю, школьник для решения должен начать строить это дерево от 1. Достаточно 3 уровней. После достижения 5 уже очевидно - 5*8+3.
Интересно, почему Вы решили что это был школьник :D . Другие вопросы были на группы Галуа, цепные дроби, и на все час с мелочью

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 19 июн 2018, 21:42
zykov
Ian писал(а):Source of the post Интересно, почему Вы решили что это был школьник

Невнимательно прочитал. Написано "экзамен", а я подумал "олимпиада".

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 20 июн 2018, 08:18
Ian
Только я не согласен, что дерево Кнута не продолжается на 7й уровень до 43, почему там именно 43 упоминают как исключение.Действительно, его заполнение неоднозначно, 40 можно получить на 6м уровне и как 32+8 но это не приведет к решению. То есть нельзя составить дерево, на котором цепи к каждому числу одновременно оптимальны, но с 43 как раз то, что приведено, хорошо дополняется

Код: Выбрать все

                1

                  |

                  2

                 / \

                /   \

               /     \

              /       \

             /         \

            3           4

           / \           \

          /   \           \

         /     \           \

        /       \           \

       5         6           8

      / \        |         /   \

     /   \       |        /     \

    7    10      12      9       16

   /    /  \    /  \    /  \    /  \

  14   11  20  15  24  13  17  18  32
  ...........\.....
  ............40.......
  ..............\.....
  ...............43....

Оптимальность алгоритма бинарного возведения в степень

Добавлено: 20 июн 2018, 10:34
zykov
Там про 43 ничего такого не написано.
Там написано про тройку (43, 77, 149), что нет дерева, где все три были бы одновременно оптимальны.