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

Аватар пользователя
Ian
Сообщений: 708
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 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

zykov
Сообщений: 1059
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 19 июн 2018, 18:45

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
Последний раз редактировалось zykov 19 июн 2018, 18:49, всего редактировалось 1 раз.

zykov
Сообщений: 1059
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 19 июн 2018, 18:48

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

Аватар пользователя
Ian
Сообщений: 708
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 19 июн 2018, 21:09

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

zykov
Сообщений: 1059
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 19 июн 2018, 21:42

Ian писал(а):Source of the post Интересно, почему Вы решили что это был школьник

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

Аватар пользователя
Ian
Сообщений: 708
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 20 июн 2018, 08:18

Только я не согласен, что дерево Кнута не продолжается на 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....

zykov
Сообщений: 1059
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 20 июн 2018, 10:34

Там про 43 ничего такого не написано.
Там написано про тройку (43, 77, 149), что нет дерева, где все три были бы одновременно оптимальны.


Вернуться в «Computer Science»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость