Только 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]

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

[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 цифр.