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

В разработке ПО произведение двух целых чисел часто вычисляется до фиксированного количества битов с переполнением. Возьмём для примера 8-битные целые. Если умножить 127 на 127, то мы получим число 1 в виде 8-битного беззнакового целого с переполнением. Реальное полное произведение равно 16129. Для представления 16129 обычно используются 16 бит точности.

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

Хотите знать, почему меня это интересует?

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

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

// simpleHighLowHash - это простой (и слабый) 32-битный хэш,// умножающий старшие 16 бит на младшие 16 бит.func simpleHighLowHash(x uint32) uint32 {    high := uint16(x >> 16)    low := uint16(x & 0xFFFF)    return uint32(high) * uint32(low)}

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

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

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

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

func simpleHighLowHash(x uint64) uint64 {    high := uint32(x >> 16)    low := uint32(x & 0xFFFFFFFF)    return uint64(high) * uint64(low)}

Можно ли получить точный результат?

Да!

Джонатан Уэбстер с коллегами разработали математический аппарат, позволяющий нам масштабировать как раз такие вычисления. Он любезно опубликовал свой код.

Существует 3 215 709 724 700 470 902 64-битных (беззнаковых) целых чисел, которые можно записать, как произведение двух 32-битных целых. Это примерно 17% от всех возможных значений.

А как насчёт реального вычисления пар целых чисел из их произведения? Одно из решений заключается в вычислении его полного разложения на простые числа с последующим получением всех возможных делителей меньше 2^32, начиная с множества кандидатов, содержащих только 1, и итеративно умножая имеющихся кандидатов на каждый простой делитель (оставляя при этом только произведения меньше 2^32). Мы можем избежать добавления во множество дубликатов, обрабатывая уникальные простые делители с кратными им числами. Затем мы выбираем такого максимального кандидата m в качестве наибольшего делителя меньше 2^32, вычисляем соответствующий сомножитель n / m и сообщаем, существует ли допустимое разбиение на два 32-битных множителя. В общем случае, ответ (если он существует) не уникален: он возвращает пару, в котором одно значение максимизировано. На Python код может выглядеть так:

for p in factor_multiplicities:    new_candidates = []    for c in candidates:        for i in range(factor_multiplicities[p] + 1):            if c * (p ** i) < 2**32:                new_candidates.append(c * (p ** i))    for new_c in new_candidates:        candidates.append(new_c)m = max(candidates)print(f"Maximum candidate: {m}")leftover = n // mprint(f"Leftover: {leftover}")if leftover >= 2**32:    print("Leftover is too large, cannot find a suitable candidate.")

Вероятно, вы сможете придумать более эффективный алгоритм. Мне показалось интересным, что если выбрать значение случайным образом, то в большинстве случаев его не удастся разложить на два 32-битных множителя!