При возведении в какую степень потребуется больше операций?

Question

[Антонио Вивальди]

При возведении в какую степень потребуется больше операций?
88 83 97

Comments

[Денис Загаевский]

а вам таки зачем?

[Владислав Лысков]

У самого никаких догадок?

[Антонио Вивальди]

Денис Загаевский, это вопрос с теста

[Антонио Вивальди]

Владислав Лысков, я думал 97

[Владислав Лысков]

Антонио Вивальди, ну помоему это более, чем очевидно

[Антонио Вивальди]

Владислав Лысков, это не правильно

[Владислав Лысков]

Антонио Вивальди, ээээ, фига се, дай подумать

Answer 1

[Владимир Т]

88 в двоичной системе = 1011000
83 = 1010011
97 = 1100001

То есть мы сначала перемножаем число 6 раз, чтобы получить степени 2, 4, 8, 16, 32, 64, затем перемножаем их между собой. Для этого понадобится столько умножений, сколько единиц в двоичном предсьавлении числа. Т.е. для возведения в степень 88 нужно будет 6+3 = 9 умножений, для степени 83 -> 6+4 = 10 умножений, для степени 97 девять умножений.

Если вычислять через экспоненту и логарифм, то две операции для любой степени.

Comments

[jcmvbkbc]

Для этого понадобится столько умножений, сколько единиц в двоичном предсьавлении числ

На одно меньше, потому что одно умножение добавляет одну единицу. Можно начать не с 0 единиц, а с одной.

[Владимир Т]

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

[jcmvbkbc]

Но результат это не меняет

97 степень можно получить за 8 умножений, в некотором смысле меняет...

[Владимир Т]

jcmvbkbc, тогда 83 степень - 9 умножений, 97 степень - 8 умножений.
т.е. 83 степень требует максимального числа умножений в любом случае.