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

[Varim]

А это точно так?

Код на c#

using System;

class HelloWorld
{
    static void Main()
    {
        ulong a = uint.MaxValue;
        ulong b = uint.MaxValue;

        ulong x = a * b;

        Console.WriteLine(x);
    }
}

Вывел 18446744065119617025

То есть если перемножение максимальных 32 битных значений влезло в 64 бит, то очевидно что другие значения тоже влезут

[Varim]

А, у вас обратная задача. Тогда не понятно что у вас вызывает удивление.

[kipar]

Разумеется произведение двух 32 битных влезет в 64 бита. Но обратное неверно - делители большинства 64 битных не влезут в 32 бита.

[Akina]

Именно делители - у большинства влезут. А вот разложить 64-битное на два сомножителя, каждый из которых влезет в 32 бита - да, для большинства не получится.

[kchhay]

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

[Shalundrive]

Интересная академическая гимнастика, но как это часто бывает с работами Даниэля Лемира, мы наблюдаем героическое решение проблемы сферического коня в вакууме. Автор искусственно загнал себя в рамки кастрированного сетапа ( 32*32=64), получил закономерные 83% брака (пустот в распределении), а затем мужественно пошёл изобретать сложные хэш-алгоритмы на безпереносном умножении вроде clhash. Зачем городить эти сложности, если современные процессоры дают нам всё необходимое практически бесплатно? Вместо того чтобы латать ущербный триггер, который математически не вывозит, достаточно просто сменить архитектурный шаблон и развернуть вычисления в ширину. Давайте посмотрим, как устроен современный суперскалярный процессор (будь то Intel, AMD или ARM). Внутри каждого ядра простаивают по 4–6 независимых исполнительных блоков (ALU). Если мы заставляем CPU считать честное 128-битное число на одном конвейере, мы собираем цепочку зависимых инструкций с переносом (типа MUL + ADC), и конвейер встаёт в микрозадержку.Но если мы берём два независимых 64-битных потока данных в параллель, процессор раскидывает их по разным ALU и выполняет операции в один и тот же такт. Скорость выполнения два по 64 в железе равна скорости выполнения одного по 64. Мы получаем 128 бит результата вообще без накладных расходов.

При этом математические дыры Лемира уничтожаются на корню:

1. Мы берём входные данные, разбиваем их на два независимых 64-битных куска (A и B).

2. Запускаем их через параллельные смесители (миксеры) с использованием огромных 64-битных простых констант (K_1 и K_2), а не 32-битных обрубков. Каждый поток внутри своего 64-битного пространства сразу работает со 100% плотностью.

3. В самом финале делаем перекрёстное скрещивание (cross-mixing): H_1 = H_1 + H_2; $H_2 = H_2 + H_1.

Энтропия лавиной размазывается между потоками. На выходе мы имеем идеальное, абсолютно равномерное заполнение 128-битного пространства хэшей. Вероятность коллизии — 1 на 2^{128} (скорее вселенная схлопнется, чем вылетит дубликат).

Именно так спроектированы по-настоящему быстрые промышленные хэши (например, 128-битная версия MurmurHash3 или гугловский FarmHash).

В реальных боевых low-latency системах никто в здравом уме не будет использовать вещественные числа из-за хаоса округлений IEEE 754 и капризов компилятора, но и платить 50–100 тактов за программную эмуляцию сверхточного float тоже никто не станет. Схема два по 64 в параллель идеально ложится на нативные регистры общего назначения (rax, rcx и т.д.), компилируется в плоский ассемблер и утилизирует кремний на 100%.

По сути статья Лемира полезна как напоминание о том, почему не надо делать хэши на коленке из 32-битных половинок. Но практический инженерный ответ на эту проблему лежит не в области усложнения математики, а в архитектурной симметрии и параллелизме, которые процессор отдаёт даром.

[wataru]

Фи, я-то думал, что там кто-то серьезно подсчитал, но в статье, на которую ссылается автор, нет вычисления M(2^32-1). Есть только алгоритм, который хоть ассимптотически и быстрее тупого перебора, на практике медленнее для вменяемых ограничений. Еще там есть монте-карло симуляция.

Код на гитхабе, судя по всему, будет считать это почти месяц для 2^32-1 на одном компьютере, и не очень-то параллелится.

Откуда взялись эти 17% пока не ясно.

[Gordon_from_Blumberg]

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

А когда 2 * 10000000 стало равно 100000000000000?

[gordey_egorov]

2*32=64

2*log(10000000)=log(100000000000000)

10000000*10000000=100000000000000

[Gordon_from_Blumberg]

Говорится про теорему, описывающую связь n-битных чисел с 2n-битными, а пример сравнивает n-битные с (n^2)-битными.

Да и вообще, если взять самое большое беззнаковое 10000000-битное 2^10000000-1 и умножить на себя, то получим 2^20000000 - 2^10000001 + 1 (применил квадрат разности), что спокойно влезает в 20000000 бит, а значит добавление 99999980000000 битов не дает ни одного нового произведения двух 10000000-битных чисел.

[Akina]

Не 2 * 10000000, а вовсе даже 10000000^2.

[Metotron0]

Когда брали два восьмибитных, то смотрели на 16. Когда брали два тридцатидвухбитных, то смотрели на 64. Почему тут квадрат?

[Akina]

Ошибочка вышла, невнимательность, под вечер бывает..

[domix32]

Там количество разрядов в числе n и 2n, а не разница между числами. если у вас число было длиной в 3 цифры, то удвоенное количество разрядов будет уже 6 цифр.