Только 17% всех 64-битных целых чисел можно разложить на два 32-битных

Вот важная новость с фронта ИИ: PatientZero 56 минут назад Только 17% всех 64-битных целых чисел можно разложить на два 32-битных Простой 3 мин 2K Математика * Алгоритмы * Программирование * Перевод Автор оригинала: Daniel Lemire В разработке ПО произведение двух целых чисел часто вычисляется до фиксированного количества битов с переполнением. Возьмём для примера 8-битные целые. Если умножить 127 на 127, то мы получим число 1 в виде 8-битного беззнакового целого с переполнением.

Реальное полное произведение равно 16129. Для представления 16129 обычно используются 16 бит точности. Таким образом у нас появляется понятие полного произведения.

Технические детали

Полное произведение двух 32-битных чисел обычно представляется при помощи 64 бит. У меня возник вопрос, какую долю всех 64-битных чисел можно записать, как произведение двух 32-битных целых. Хотите знать, почему меня это интересует?

Мы часто проектируем хэш-функции: это особые функции, получающие входные данные и генерирующие случайно выглядящие выходные. Много лет назад я проектировал очень быструю хэш-функцию clhash. Эта сверхбыстрая функция предназначена для хэширования строк из сотен и более байт.

Если вы не знаете про clhash, то можете почитать про неё, она интересна сама по себе. В clhash используется тип умножения, характерный для криптографии. Я пытался показать, что такой подход выгоднее по сравнению с методиками, основанными на стандартном умножении.

Отраслевые последствия

Попробую это проиллюстрировать: простая хэш-функция для 32-битных целых чисел может брать младшие биты у перемножать их со старшими. // simpleHighLowHash - это простой (и слабый) 32-битный хэш, // умножающий старшие 16 бит на младшие 16 бит. func simpleHighLowHash(x uint32) Вероятно, вам нужно, чтобы хэш-функция была равномерной: вероятность всех возможных 32-битных значений хэша должна быть одинаковой.

В данном случае это возможно, только если хэш-функция может возвращать все 32-битные значения хэша, но это не так. Великий математик Пал Эрдёш доказал, что доля всех 2n-битных значений, которую можно сгенерировать перемножением двух n-битных значений при увеличении n стремится к нулю. Это значит, что если, например, вы умножаете 10000000-битные целые на 10000000-битные целые, то получится относительно мало 100000000000000-битных целых.

Но как насчёт практических случаев, например, 32-битных или 64-битных целых? Задачу легко можно решить перебором, перемножая 16-битные числа для получения 32-битных произведений. Там мы выясним, что произведением двух 16-битных целых оказываются чуть больше одного из пяти 32-битных чисел.

Событие, по словам экспертов, усилит конкуренцию в сфере ИИ.