Как уменьшить диапазон поиска для неизвестного числа?
Имеется неизвестное число X которое находится в диапазоне от 2^80 до ^81
Какие вычисления произвести с X что бы X стало в диапазоне от 2^40 до 2^41 Но с количеством возможных вариантов(для дальнейшего поиска) меньшим чем 2^41-2^40 ? Брать к примеру каждое 20 число из диапазона 2^40 ...2^41 но что бы оно точно было в меньшем диапазоне ?
Ищу любой вариант, от "ответа Умельца" до ссылок на научно обоснованный алгоритм , может быть , если он имеется
У X еще должно быть какое-то ограничение. Оно как минимум не должно быть произвольным в диапазоне 2^80 до 2^81, а иметь шаг 2^n * i. Решение задачи будет отбросить 2^n и использовать только i.
alexalexes, уменьшаю. X в диапазоне от 2**80 ... 2** 81, когда я из X вычел 2**79, у меня диапазон поиска тоже на 2**79 уменьшился Я же Х а не диапазон ищу .
HrustHr, Вы ищете не просто X. Вы ищете такой X, при котором выполняется некое условие, например значение функции f(X) равняется Y. Вот и скажите нам, что это за функция, тогда можно будет что-то посоветовать.
Rsa97, нет речи о какой либо функции, речь о формуле или алгоритме как можно неизвестное число из одного диапазона в другой перенести , в условиях когда число не известно
В этом и суть, что в такой задачи X не может быть произвольным числом.
Например, если мы говорим об X как о простом числе, то мы сразу накладываем ограничение на диапазон b/ln(b) - a/ln(a) по теореме о распределении простых чисел, и этих чисел (простых) в данном диапазоне становится сильно меньше, чем произвольных чисел, если бы не было такого ограничения.
HrustHr, Никак. Для взаимно однозначного полного отображения одного конечного множества на другое конечное множество количество элементов в множествах должно быть одинаковым.
HrustHr, вот вам аналогия вашего вопроса: мне надо найти убийцу из 100000 жителей города. Как не опрашивать всех, а только 10 человек? Ответ - никак. Если вам не известно какое-то еще свойство убийцы (например, кто-то видел мужика в черной куртке), то никак.
Вопрос - иллюстрация Проблемы XY (Ошибки молотка).
Судя по вводным данным, вопрос, в частности, выглядит как ферматизм из области криптографии, как попытка решить большую сложную задачу устаревшими методами. Причем детали не раскрываются, потому что подход к решению - оригинальное изобретение. Если бы всё было так просто, задачу давно решили бы.
Бинарный поиск, делов-то.
Число прыжков будет ~ log2(b-a), где [a, b] - ваш диапазон.
Чтобы работал бинарный поиск, нужна функция, которая укажет в какое направление прыгать - в меньшую половину фрагмента диапазона, или в большую.
Нет, если у вас есть функция, которая укажет в какую сторону двигаться, если вы взяли произвольное любое число, то легко найдете X за логарифмическую сложность.
Мне нужно диапазон неизвестного числа уменьшить, что бы получить число возможных вариантов меньше чем уменьшенный диапазон. К примперу если взять каждый 10й случай из диапазона 2^40...2^41 получится нужно будет искать в 10 раз меньше ..
HrustHr, если у вас нет никакой дополнительной информации, что число находится в каком-то диапазоне, то количество вариантов вы никак не сможете уменьшить.
У вас есть хотябы какая-нибудь функция, которая говорит, что найденное число - то самое?
Для правильного вопроса надо знать половину ответа
Всё зависит от того, что именно ищем.
Если ноль монотонной функции, определённой на этом интервале, то бинарным поиском либо градиентным спуском.
А если хэш от числа, то только математическим анализом уязвимости алгоритма расчёта хэша. Если повезёт и такая уязвимость будет, то область поиска можно будет сократить.
HrustHr, А математика - она штука такая. Возможность сократить область поиска зависит от того, что и как мы ищем. Вы напишите конкретно, а то у вас пока примерно так: есть триллион человек, как мне найти одного по фотографии, посмотрев только на сто из них.
Rsa97, по-моему, этот кадр уже был здесь несколько месяцев назад с несколькими похожими вопросами. Собственно задачу так и не рассказал ни разу, а только намеками. Чувак явно ломает криптографию и держит в тайне свою гениальную идею.
HrustHr, вам в прошлый раз пытались объяснить, что мы не телепаты, просто взять и выкинуть из перебора почти все числа - нельзя. Только если вы дадите полное и строгое описание свойств искомого числа X, может быть шанс на какое-то ускорение перебора. Но, если это действительно криптография, то шанса вообще нет.
А зачем нужны критерии если , к примеру вычитаеш 4 из 167 40 раз, можно потом искать неизвестное 167 - 4* 1,2,3,3.. 40, 40 раз, а если брать и искать неизвестно только каждый воторой результат вычисления вычитания то искать нужно только 20 раз . Какие ещё критерии..
А почему из 167? Если вы ищете число 167, то его искать не надо, вот оно уже есть: "167". Если же вы знаете, что X от 1 до 167, то вычитать 4 нельзя. А вдруг искомое число 166? Вы его вычитанием 4 пропустите. Если вы можете сказать, что перескочили через искомое X - то это уже и есть тот самый критерий, какое-то дополнительное свойство X, которое можно использовать, например, для бинарного поиска.
HrustHr, Т.е. у вас есть не данное число X, Вы из него вычитаете 4, получаете неизвестное X-4. Дальше что? Как вообще можно из неизвестного числа что-то вычитать? Ну допустим, вы 40 раз вычли, получили X-160. 42 раза вычли, получили X-168 - все неизвестные числа. Как вы определяете, что дальше вычитать не надо?
Ну в задаче как-бы не хватает информации. Если мы ищем решение какого-нибудь корня квадратного
то у нас есть методы дихотомии, Ньютона, всяких там хорд и прочее.
Если функция более хитрая (не гладкая) то к ней надо с хитростью подходить.
