Версия для печати темы

Автор: nik_vic 22.1.2008, 11:11

Есть известная задача о минимальном количестве умножений для возведения в натуральную степень n с оценками log2(n) и 2log2(n).
Известна ли в качестве верхней оценки log2(n)*(1+о(1))?
С уважением, НикВик.

Автор: Geen 22.1.2008, 11:52

Прошу прощения, а что такое 1+o(1)? (о малое?)

Автор: nik_vic 22.1.2008, 12:36

Через o(1) обозначают функцию с нулевым пределом, или бесконечно-малую (при рассматриваемом предельном переходе).

Автор: Geen 22.1.2008, 14:22

o(1) это 0. Особенно, если его прибавлять/сравнивать с 1.

Автор: nik_vic 22.1.2008, 14:27

Гм, обозначение достаточно стандартно.
Ладно, переформулирую - предел отношения
минимальное_число_умножений_для_возведения_в_степень_n / log2(n)
равен 1.

Автор: waldian 22.1.2008, 15:38

Был вроде древовидный алгоритм.. И вроде бы его можно заточить под определенный диапазон степеней (достаточно большой), тогда на них он будет давать похожую сложность.

Автор: nik_vic 22.1.2008, 15:58

Не слышал ничего такого - кроме стандартного для начинающих программистов.

Поставлю вопрос ещё более конкретно - в какое число умножений можно "уложиться" при возведении в степени, число бит которых не превосходит, скажем, 1000?
"Стандарт" даёт 1998 - 999 возведений в квадрат и 999 умножений на аргумент.
Я умею за 1230...
Кто меньше?

Автор: waldian 22.1.2008, 20:46

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

Автор: Mouse 22.1.2008, 20:57

эта задача не связанна с какой-то гипотизой в математике гда что-то похожее но с матрицами и типа 1.000.000баксов за решение?

Автор: nik_vic 22.1.2008, 21:00

Памяти - хоть залейся
Задача сформулирована однозначно.
Впрочем, меня больше интересует, не слышал ли кто-нибудь что-то подобное.

Автор: Mouse 22.1.2008, 23:44

1. размеры памяти хоть залейся в разумных приделах? типа несколько гиг.
2. возможно ли осушествление предварительных расчётов.
3. все опреции происходять за одно и тоже время? т.е. ейчас перемножить 1000знаковых числа будет помедленее чем сложение аналогичных?

Автор: Geen 22.1.2008, 23:52

Гм, не встречал таких обозначений. Обычное обозначение будет O(log(n)) для всех приведённых выражений.
Переспрошу иначе, чем третий вариант отличается от первого (из исходного поста)?

Автор: Mouse 23.1.2008, 0:04

это стандартное обозначение, просто в програмирование обычно что Н, что 10*Н операций относительно одно и тоже. поэтому О большое встречаеться чаще. а тут важно более точное кол-во операций т.е. 1.5*Н намного лучше 2*Н. т.е. при больших Н число операций будет 1.00000...0001*лог2(Н) без всяких О

Автор: nik_vic 23.1.2008, 9:08

Гм, странно было бы упоминать конкретные гиги - "умножение", фигурирующее в задаче, может быть умножением больших матриц (да ещё "по модулю", чтобы не заморачиваться переполнением) или просто какой-то ассоциативной операцией.
Именно так её и нужно представлять - как расстановку скобок в выражении х*х*х*...х с n "множителями" х и количеством различных подформул как критерием.

Впрочем, мой алгоритм для степени из 1000 бит требует всего несколько десятков дополнительных "ячеек"

Автор: nik_vic 25.1.2008, 10:38

Нет.
Хотя не исключаю, что задача построения минимизирующей схемы по степени относится к т.н. универсальным NP-задачам. За решение проблемы перебора тоже обещают мильон

Автор: waldian 25.1.2008, 14:03

За доказательство "P=NP?" обещают мильон..
А минимизирующая схема вроде решается проще... Вроде это аналог вычисления порядка перемножения матриц, но могу ошибаться.

Автор: nik_vic 25.1.2008, 14:14

В некотором смысле задача похожа на построение минимальной схемы для вычисления булевых функций. Эта задача - NP-универсальна.

Если хочется подумать, то вот эквивалентная формулировка.
По данному N построить массив целых минимальной длины, первый элемент которого =1, все последующие - сумма каких-то 2-х предыдущих (в том числе удвоение какого-либо предыщего), а последний равен n.

Автор: waldian 25.1.2008, 17:02

"NP-универсальна" - это NP-полная или NP-сложная? Не встречал такого термина раньше.
Переформулирование понятно, но что-то мне не верится, что тут только перебором (ветвями-границами и прочим, но по сути перебором) решится.
Вроде получается последовательно получать схемы при увеличении степени. А это скорее аналог динамического программирования.

Автор: nik_vic 25.1.2008, 17:12

Сейчас чаще говорят NP-полная.
Можно и как диеамическое прграммирование. Только "точками" будут множества

Автор: nik_vic 27.1.2008, 20:13

Пожалуй, дам решение. Чтобы почти без формул, для небольшой степени, скажем, не более 1023
Обычный алгоритм для числа 1023 получает последовательные степени 2,3,6,7,14,15,...1023, используя ровно 20 умножений.
Мой сначала вычислит и запомнит степени 0,1,2,3 (два умножения), или, в битовом представлении, 00,01,10,11.
Запись исходной степени - 10 бит - разбивается на 5 групп по 2 бита (каждая совпадает с одной из вычисленных), старшую обозначим как Х, и она у нас уже есть. Двигаясь "вниз", делаем 4 шага: возведение в квадрат, возведение в квадрат, умножение на надлежащее число из памяти - итого 2+4*3=14 умножений.

... а если битов тысяча, то берутся группы подлиннее...
Кажется, 5(?) - 30+995/5*6-1224!!
А с 6-й ещё лучше - 1221. Семёрка - перебор.