Гипотеза о факториале из нефакториальных цифр

[Dmitriy40]

Впрочем, кажется достаточно не проверять старшие цифр 15-20 (увеличив буфер цифр до 80 и более), считать что там шум, но в вычислениях использовать. Похоже ошибка не накапливается/размножается, а раз возникнув (при обнулении младшей цифры в буфере) за несколько шагов вымывается за старшую границу буфера.

-- 26.08.2016, 04:13 --

Почему 15 минимум: для множителя $5^{15}\approx 3\cdot10^{10}$ может образоваться 15 младших нулей, которые при сдвиге вправо испортят 15 старших цифр. Ну и ещё пару цифр про запас.

[Dmitriy40]

Перепроверил до $10^9!$ с учётом запаса цифр, решений всё равно нет.

(Скорость на Дельфи)

Вот же гадская дельфи, компилит кошмарно тормозной код с int64, замена всего трёх операций умножения/деления

Используется синтаксис Delphi

m := m * n + c; с := m div 1000000000; m := m mod 1000000000;

на ассемблер

Используется синтаксис ASM

        mov     EAX,m
        mov     EDX,n
        mov     ECX,c
        mul     EDX
        add     EAX,ECX
        adc     EDX,0
        mov     ECX,1000000000
        div     ECX
        mov     m,EDX
        mov     c,EAX

дала 40-кратное ускорение! До $10^9!$ вместо ~4300с считается всего лишь 107с.

[mihaild]

Dmitriy40, поверю на слово (вроде говорите правду, и эффект воспроизводится, но я еще не успел "понять", что делать). С вашей поправкой ($13$ разрядов длиной $10^6$, смотрим первые $10$) считается за 30 секунд.

(Оффтоп)

Завтра доберусь до машины с AVX-512, там вроде бы все нужные интринсики есть. В SSE* и AVX с 64-битными числами только сложение/вычитание