Функция, где небольшие изменения во входе всегда приводят к большим изменениям в выводе
Я хотел бы алгоритм за функцию, которая берет n целые числа и возвращает одно целое число. Для небольших изменений во входе получающееся целое число должно варьироваться значительно. Даже при том, что я взял много курсов в математике, я не использовал то знание очень, и теперь я нуждаюсь в некоторой помощи...
Важное свойство этой функции должно быть то, что, если она используется с координатными парами, как введено и результатом, напечатан (как полутоновое значение, например) на изображении, любые шаблоны повторения должны только быть видимы, если изображение является очень большим.
Я экспериментировал с различными алгоритмами для псевдослучайных чисел с небольшим успехом, и наконец он ударил меня, что md5 почти соответствует моим критериям, за исключением того, что это не для чисел (по крайней мере, не от того, что я знаю). Это привело к чему-то вроде этого прототип Python (для n = 2, он мог легко быть изменен для взятия списка целых чисел, конечно):
import hashlib
def uniqnum(x, y):
return int(hashlib.md5(str(x) + ',' + str(y)).hexdigest()[-6:], 16)
Но очевидно чувствует себя неправильным пробежаться через строки, когда оба ввода и вывода являются целыми числами. Какова была бы хорошая замена для этой реализации (в псевдокоде, Python, или безотносительно языка)?
5 ответов
«Хеш» - это решение, созданное для решения именно проблемы, которую вы описываете. См. статью в википедии
. Любая хеш-функция, которую вы используете, будет хороша; хэш-функции обычно оцениваются на основе следующих критериев:
- Степень, в которой они предотвращают коллизии (два отдельных входа производят один и тот же результат) - побочным продуктом этого является степень, в которой функция минимизирует выходы, которые никогда не могут быть достигнуты ни с одного входа.
- Равномерность распределения его выходов при равномерно распределенном наборе входов
- Степень, в которой небольшие изменения входных данных вызывают большие изменения в выходных данных.
(см. идеальная хеш-функция )
Учитывая, насколько сложно создать хеш-функцию, которая максимизирует все эти критерии, почему бы просто не использовать один из наиболее часто используемых и надежных существующих хэш-функции уже есть?
На первый взгляд, превращение целых чисел в строки кажется еще одним уровнем шифрования! (что, как я полагаю, хорошо для ваших целей)
Однако ваш вопрос касается хэш-функций, которые имеют дело , в частности, с числами , так что поехали.
Хеш-функции, которые работают с целыми числами
Если вы хотите позаимствовать уже существующие алгоритмы, вы можете попробовать генераторы псевдослучайных чисел
Один из простых способов - метод среднего квадрата:
- Возьмите цифровое число
- Возведите его в квадрат
- Отрежьте цифры и оставьте средние цифры той же длины, что и исходная.
то есть
1111 => 01234321 => 2342
так, 1111 будет "хешировано" до 2342 в методе среднего квадрата.
Этот способ не тот эффективен, но для небольшого количества хешей он имеет очень низкую частоту конфликтов, равномерное распределение и большой потенциал хаоса (небольшие изменения => большие изменения). Но если у вас много значений, пора поискать что-нибудь еще ...
Прадедушкой всех реально эффективных и простых генераторов случайных чисел является (Mersenne Twister) [ http: //en.wikipedia. org / wiki / Mersenne_twister] . Фактически, реализация, вероятно, существует для любого языка программирования, который только можно вообразить. Ваш хэш-«вход» - это то, что в их терминологии будет называться «семенем».
В заключение
- В строковых хэш-функциях нет ничего плохого.
- Если вы хотите придерживаться целых чисел и проявлять фантазию, попробуйте использовать свое число в качестве начального числа для генератора псевдослучайных чисел.
Хэширование идеально подходит под ваши требования. Если вы действительно не хотите использовать строки, найдите библиотеку Hash, которая будет принимать числа или двоичные данные. Но использование строк здесь выглядит нормально, на мой взгляд.
Функция смешивания Боба Дженкинса является классическим выбором при n = 3.
Взгляните на это, может быть, вы вдохновитесь
В хаотической динамике небольшие изменения сильно меняют результаты.
Как отмечают другие, хэш-функции делают именно то, что вы хотите. Хеши принимают байты - не символьные строки - и возвращают байты, а преобразование между целыми числами и байтами, конечно, простое. Вот пример функции python, которая работает с 32-битными целыми числами и выдает 32-битное целое число:
import hashlib
import struct
def intsha1(ints):
input = struct.pack('>%di' % len(ints), *ints)
output = hashlib.sha1(input).digest()
return struct.unpack('>i', output[:4])
Конечно, ее можно легко адаптировать для работы с входами и выходами разной длины.