Как уменьшить диапазон поиска для неизвестного числа?

Question

[HrustHr]

Имеется неизвестное число X которое находится в диапазоне от 2^80 до ^81

Какие вычисления произвести с X что бы X стало в диапазоне от 2^40 до 2^41 Но с количеством возможных вариантов(для дальнейшего поиска) меньшим чем 2^41-2^40 ? Брать к примеру каждое 20 число из диапазона 2^40 ...2^41 но что бы оно точно было в меньшем диапазоне ?

Ищу любой вариант, от "ответа Умельца" до ссылок на научно обоснованный алгоритм , может быть , если он имеется

Спасибо

Comments

[alexalexes]

Математика какая?
X - вещественное, или строго целочисленное?

[HrustHr]

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

?

[alexalexes]

У X еще должно быть какое-то ограничение. Оно как минимум не должно быть произвольным в диапазоне 2^80 до 2^81, а иметь шаг 2^n * i. Решение задачи будет отбросить 2^n и использовать только i.

[HrustHr]

alexalexes, X любое в диапазоне от 2**80...2**81. Шаг = 1

?

[alexalexes]

Тогда у вас этих X будет 2^80, без дополнительных условий вы этот диапазон не уменьшите.

[HrustHr]

alexalexes, если я вычту из X = 2**80 ,2**79, получу 2**79. Уменьшается же ?;)

[alexalexes]

Это действие - нормализация диапазона.
Вы просто диапазон поиска сдвигаете к нулю, но не уменьшаете его:
2^n... 2^(n+1) => 0 ... 2^n

[HrustHr]

alexalexes, уменьшаю. X в диапазоне от 2**80 ... 2** 81, когда я из X вычел 2**79, у меня диапазон поиска тоже на 2**79 уменьшился Я же Х а не диапазон ищу .

[Rsa97]

HrustHr, Вы ищете не просто X. Вы ищете такой X, при котором выполняется некое условие, например значение функции f(X) равняется Y. Вот и скажите нам, что это за функция, тогда можно будет что-то посоветовать.

[HrustHr]

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

[alexalexes]

В этом и суть, что в такой задачи X не может быть произвольным числом.
Например, если мы говорим об X как о простом числе, то мы сразу накладываем ограничение на диапазон b/ln(b) - a/ln(a) по теореме о распределении простых чисел, и этих чисел (простых) в данном диапазоне становится сильно меньше, чем произвольных чисел, если бы не было такого ограничения.

[Василий Банников]

HrustHr, никак

[Rsa97]

HrustHr, Никак. Для взаимно однозначного полного отображения одного конечного множества на другое конечное множество количество элементов в множествах должно быть одинаковым.

[Wataru]

HrustHr, вот вам аналогия вашего вопроса: мне надо найти убийцу из 100000 жителей города. Как не опрашивать всех, а только 10 человек? Ответ - никак. Если вам не известно какое-то еще свойство убийцы (например, кто-то видел мужика в черной куртке), то никак.

[code_panik]

Вопрос - иллюстрация Проблемы XY (Ошибки молотка).
Судя по вводным данным, вопрос, в частности, выглядит как ферматизм из области криптографии, как попытка решить большую сложную задачу устаревшими методами. Причем детали не раскрываются, потому что подход к решению - оригинальное изобретение. Если бы всё было так просто, задачу давно решили бы.

[Wattouch]

Возьмите для лучшего понимания диапазон поменьше, например: от 8 до 15.

У нас есть числа:
8, 9, 10, 11, 12, 13, 14, 15

Вычтем из каждого числа например 4, получим:
4, 5, 6, 7, 8, 9, 10, 11

Диапазон изменился, но количество чисел осталось тем же.
И какие бы действия вы не производили, но количество элементов для поиска останется тем же.

Есть один вариант как однократно уменьшить диапазон в 2 раза: из каждого числа вычесть 11.5

Получится:
-3.5, -2.5, -1.5, -0.5, 0.5, 1.5, 2.5, 3.5

Для вашей задачи ведь знак не имеет значения.
Но как потом сократить диапазон еще раз, я к сожалению не знаю.

Answer 1

[alexalexes]

Бинарный поиск, делов-то.
Число прыжков будет ~ log2(b-a), где [a, b] - ваш диапазон.
Чтобы работал бинарный поиск, нужна функция, которая укажет в какое направление прыгать - в меньшую половину фрагмента диапазона, или в большую.

Comments

[HrustHr]

Бинарный поиск он же для известного Х ?

[alexalexes]

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

[HrustHr]

alexalexes,

Мне нужно диапазон неизвестного числа уменьшить, что бы получить число возможных вариантов меньше чем уменьшенный диапазон. К примперу если взять каждый 10й случай из диапазона 2^40...2^41 получится нужно будет искать в 10 раз меньше ..

?

[Василий Банников]

HrustHr, если у вас нет никакой дополнительной информации, что число находится в каком-то диапазоне, то количество вариантов вы никак не сможете уменьшить.

У вас есть хотябы какая-нибудь функция, которая говорит, что найденное число - то самое?

Answer 2

[Rsa97]

Всё зависит от того, что именно ищем.
Если ноль монотонной функции, определённой на этом интервале, то бинарным поиском либо градиентным спуском.
А если хэш от числа, то только математическим анализом уязвимости алгоритма расчёта хэша. Если повезёт и такая уязвимость будет, то область поиска можно будет сократить.

Comments

[HrustHr]

Не о уязвимости алгоритма речь, а о математике...

[HrustHr]

Решения все ещё нет...

[Rsa97]

HrustHr, А математика - она штука такая. Возможность сократить область поиска зависит от того, что и как мы ищем. Вы напишите конкретно, а то у вас пока примерно так: есть триллион человек, как мне найти одного по фотографии, посмотрев только на сто из них.

[Wataru]

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

[Alexandroppolus]

Wataru, да, диапазоны чисел смутно знакомые ))

[HrustHr]

Alexandroppolus, ну не видно что Вам что то знакомо

[Wataru]

HrustHr, вам в прошлый раз пытались объяснить, что мы не телепаты, просто взять и выкинуть из перебора почти все числа - нельзя. Только если вы дадите полное и строгое описание свойств искомого числа X, может быть шанс на какое-то ускорение перебора. Но, если это действительно криптография, то шанса вообще нет.

Answer 3

[Максим Гришин]

Никак.

Вы не имеете критериев уточнения поиска, не имеете критериев проверки найденного, так что математически вам помочь нечем.

Comments

[HrustHr]

А зачем нужны критерии если , к примеру вычитаеш 4 из 167 40 раз, можно потом искать неизвестное 167 - 4* 1,2,3,3.. 40, 40 раз, а если брать и искать неизвестно только каждый воторой результат вычисления вычитания то искать нужно только 20 раз . Какие ещё критерии..

[Rsa97]

HrustHr, И что вы получите в результате? 1, 3, 5, ..., 39. Всё, 20 чисел перебрали, но нужное, 40, так и не нашли.

[Wataru]

HrustHr,

если , к примеру вычитаеш 4 из 167 40 раз

А почему из 167? Если вы ищете число 167, то его искать не надо, вот оно уже есть: "167". Если же вы знаете, что X от 1 до 167, то вычитать 4 нельзя. А вдруг искомое число 166? Вы его вычитанием 4 пропустите. Если вы можете сказать, что перескочили через искомое X - то это уже и есть тот самый критерий, какое-то дополнительное свойство X, которое можно использовать, например, для бинарного поиска.

[HrustHr]

Wataru, ну я вычитая 4 получаю в случае 167 число 3 и потом прибавляя назад нахожу число 167

[Wataru]

HrustHr, Всмысле, вам 167 уже дано? Зачем тогда из него вычитать что-то?

[HrustHr]

Wataru, оно не дано. И вычить что бы найти хоть что то и потом найти 167

[Wataru]

HrustHr, Т.е. у вас есть не данное число X, Вы из него вычитаете 4, получаете неизвестное X-4. Дальше что? Как вообще можно из неизвестного числа что-то вычитать? Ну допустим, вы 40 раз вычли, получили X-160. 42 раза вычли, получили X-168 - все неизвестные числа. Как вы определяете, что дальше вычитать не надо?

[HrustHr]

Wataru, я же написал что диапазон числа из которого вычитать известен или вы предлагаете вычитать больше чем диапазон...

[Wataru]

HrustHr, Т.е. 167 - это диапазон, а не искомое, неизвестное число? А если само число окажется 166, то уже первое -4 переведет в отрицательные числа.

Answer 4

[mayton2019]

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

Если функция более хитрая (не гладкая) то к ней надо с хитростью подходить.