Возведение в степень., Верхняя оценка. |
Добро пожаловать, гость ( Вход | Регистрация )
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
Возведение в степень., Верхняя оценка. |
nik_vic |
22.1.2008, 11:11
Сообщение
#1
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Есть известная задача о минимальном количестве умножений для возведения в натуральную степень n с оценками log2(n) и 2log2(n).
Известна ли в качестве верхней оценки log2(n)*(1+о(1))? С уважением, НикВик. -------------------- Где это видано?
|
Geen |
22.1.2008, 11:52
Сообщение
#2
|
Участник Группа: Пользователи Braingames Сообщений: 52 Регистрация: 29.5.2007 Пользователь №: 1 027 |
Прошу прощения, а что такое 1+o(1)? (о малое?)
|
nik_vic |
22.1.2008, 12:36
Сообщение
#3
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Прошу прощения, а что такое 1+o(1)? (о малое?) -------------------- Где это видано?
|
Geen |
22.1.2008, 14:22
Сообщение
#4
|
Участник Группа: Пользователи Braingames Сообщений: 52 Регистрация: 29.5.2007 Пользователь №: 1 027 |
o(1) это 0. Особенно, если его прибавлять/сравнивать с 1.
|
nik_vic |
22.1.2008, 14:27
Сообщение
#5
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
o(1) это 0. Особенно, если его прибавлять/сравнивать с 1. Ладно, переформулирую - предел отношения минимальное_число_умножений_для_возведения_в_степень_n / log2(n) равен 1. -------------------- Где это видано?
|
waldian |
22.1.2008, 15:38
Сообщение
#6
|
Активный участник Группа: Пользователи Braingames Сообщений: 813 Регистрация: 20.4.2007 Из: Питер Пользователь №: 103 |
Был вроде древовидный алгоритм.. И вроде бы его можно заточить под определенный диапазон степеней (достаточно большой), тогда на них он будет давать похожую сложность.
|
nik_vic |
22.1.2008, 15:58
Сообщение
#7
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Был вроде древовидный алгоритм.. И вроде бы его можно заточить под определенный диапазон степеней (достаточно большой), тогда на них он будет давать похожую сложность. Поставлю вопрос ещё более конкретно - в какое число умножений можно "уложиться" при возведении в степени, число бит которых не превосходит, скажем, 1000? "Стандарт" даёт 1998 - 999 возведений в квадрат и 999 умножений на аргумент. Я умею за 1230... Кто меньше? -------------------- Где это видано?
|
waldian |
22.1.2008, 20:46
Сообщение
#8
|
Активный участник Группа: Пользователи Braingames Сообщений: 813 Регистрация: 20.4.2007 Из: Питер Пользователь №: 103 |
Не слышал ничего такого - кроме стандартного для начинающих программистов. Поставлю вопрос ещё более конкретно - в какое число умножений можно "уложиться" при возведении в степени, число бит которых не превосходит, скажем, 1000? "Стандарт" даёт 1998 - 999 возведений в квадрат и 999 умножений на аргумент. Я умею за 1230... Кто меньше? Только все убыстрения являются разменом времени на память. Так что, надо критерий четче ставить. |
Mouse |
22.1.2008, 20:57
Сообщение
#9
|
и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
эта задача не связанна с какой-то гипотизой в математике гда что-то похожее но с матрицами и типа 1.000.000баксов за решение?
|
nik_vic |
22.1.2008, 21:00
Сообщение
#10
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Только все убыстрения являются разменом времени на память. Так что, надо критерий четче ставить. Задача сформулирована однозначно. Впрочем, меня больше интересует, не слышал ли кто-нибудь что-то подобное. -------------------- Где это видано?
|
Mouse |
22.1.2008, 23:44
Сообщение
#11
|
и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
1. размеры памяти хоть залейся в разумных приделах? типа несколько гиг.
2. возможно ли осушествление предварительных расчётов. 3. все опреции происходять за одно и тоже время? т.е. ейчас перемножить 1000знаковых числа будет помедленее чем сложение аналогичных? |
Geen |
22.1.2008, 23:52
Сообщение
#12
|
Участник Группа: Пользователи Braingames Сообщений: 52 Регистрация: 29.5.2007 Пользователь №: 1 027 |
Гм, обозначение достаточно стандартно. Ладно, переформулирую - предел отношения минимальное_число_умножений_для_возведения_в_степень_n / log2(n) равен 1. Гм, не встречал таких обозначений. Обычное обозначение будет O(log(n)) для всех приведённых выражений. Переспрошу иначе, чем третий вариант отличается от первого (из исходного поста)? |
Mouse |
23.1.2008, 0:04
Сообщение
#13
|
и.о. админа Группа: Администраторы Сообщений: 86 Регистрация: 5.12.2006 Пользователь №: 20 |
QUOTE Гм, не встречал таких обозначений. Обычное обозначение будет O(log(n)) для всех приведённых выражений.Переспрошу иначе, чем третий вариант отличается от первого (из исходного поста)? это стандартное обозначение, просто в програмирование обычно что Н, что 10*Н операций относительно одно и тоже. поэтому О большое встречаеться чаще. а тут важно более точное кол-во операций т.е. 1.5*Н намного лучше 2*Н. т.е. при больших Н число операций будет 1.00000...0001*лог2(Н) без всяких О |
nik_vic |
23.1.2008, 9:08
Сообщение
#14
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
1. размеры памяти хоть залейся в разумных приделах? типа несколько гиг. 2. возможно ли осушествление предварительных расчётов. 3. все опреции происходять за одно и тоже время? т.е. ейчас перемножить 1000знаковых числа будет помедленее чем сложение аналогичных? Именно так её и нужно представлять - как расстановку скобок в выражении х*х*х*...х с n "множителями" х и количеством различных подформул как критерием. Впрочем, мой алгоритм для степени из 1000 бит требует всего несколько десятков дополнительных "ячеек" -------------------- Где это видано?
|
nik_vic |
25.1.2008, 10:38
Сообщение
#15
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
эта задача не связанна с какой-то гипотизой в математике гда что-то похожее но с матрицами и типа 1.000.000баксов за решение? Хотя не исключаю, что задача построения минимизирующей схемы по степени относится к т.н. универсальным NP-задачам. За решение проблемы перебора тоже обещают мильон -------------------- Где это видано?
|
waldian |
25.1.2008, 14:03
Сообщение
#16
|
Активный участник Группа: Пользователи Braingames Сообщений: 813 Регистрация: 20.4.2007 Из: Питер Пользователь №: 103 |
Нет. Хотя не исключаю, что задача построения минимизирующей схемы по степени относится к т.н. универсальным NP-задачам. За решение проблемы перебора тоже обещают мильон За доказательство "P=NP?" обещают мильон.. А минимизирующая схема вроде решается проще... Вроде это аналог вычисления порядка перемножения матриц, но могу ошибаться. |
nik_vic |
25.1.2008, 14:14
Сообщение
#17
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
А минимизирующая схема вроде решается проще... Вроде это аналог вычисления порядка перемножения матриц, но могу ошибаться. В некотором смысле задача похожа на построение минимальной схемы для вычисления булевых функций. Эта задача - NP-универсальна. Если хочется подумать, то вот эквивалентная формулировка. По данному N построить массив целых минимальной длины, первый элемент которого =1, все последующие - сумма каких-то 2-х предыдущих (в том числе удвоение какого-либо предыщего), а последний равен n. -------------------- Где это видано?
|
waldian |
25.1.2008, 17:02
Сообщение
#18
|
Активный участник Группа: Пользователи Braingames Сообщений: 813 Регистрация: 20.4.2007 Из: Питер Пользователь №: 103 |
В некотором смысле задача похожа на построение минимальной схемы для вычисления булевых функций. Эта задача - NP-универсальна. Если хочется подумать, то вот эквивалентная формулировка. По данному N построить массив целых минимальной длины, первый элемент которого =1, все последующие - сумма каких-то 2-х предыдущих (либо удвоение какого-либо предыщего), а последний равен n. "NP-универсальна" - это NP-полная или NP-сложная? Не встречал такого термина раньше. Переформулирование понятно, но что-то мне не верится, что тут только перебором (ветвями-границами и прочим, но по сути перебором) решится. Вроде получается последовательно получать схемы при увеличении степени. А это скорее аналог динамического программирования. |
nik_vic |
25.1.2008, 17:12
Сообщение
#19
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
"NP-универсальна" - это NP-полная или NP-сложная? Не встречал такого термина раньше. Переформулирование понятно, но что-то мне не верится, что тут только перебором (ветвями-границами и прочим, но по сути перебором) решится. Вроде получается последовательно получать схемы при увеличении степени. А это скорее аналог динамического программирования. Можно и как диеамическое прграммирование. Только "точками" будут множества -------------------- Где это видано?
|
nik_vic |
27.1.2008, 20:13
Сообщение
#20
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
Пожалуй, дам решение. Чтобы почти без формул, для небольшой степени, скажем, не более 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. Семёрка - перебор. -------------------- Где это видано?
|
Упрощённая версия | Сейчас: 6.5.2024, 3:54 |