maxim1000

Цитата

это практически никакого ускорения не даст

В том смысле, что считать сумму натуральных логарифмов по всем числам, а потом экспоненту по получившемуся. Может подскажешь, как разложить в ряд натуральный логарифм??? Там можно будет покумекать с многоразрядными делами потом...
Добавлено @ 16:08
А, ну понял.
Ну всё равно подскажи, как логарифм разложить.

Цитата

В том смысле, что считать сумму натуральных логарифмов по всем числам, а потом экспоненту по получившемуся.

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

Цитата

Может подскажешь, как разложить в ряд натуральный логарифм???

ряда не помню
к тому же есть разные ряды (Тейлора, Фурье)
если в Тейлора, то попробуй разложить ln(1+x) с помощью производных
кроме того, можно еще искать логарифм с помощью бисекции (правда, тогда придется реализовывать еще и операцию корня)

Надо выделить степени 2 и 5, встречающиеся в разложениях i = 2, n
на множители, и посчитать их степени отдельно. Потом, если степень 2 больше,
домножить на 2 в степени (степень 2 - степень 5), иначе 5 в степени (степень 5 - степень 2),
остаток пойдет в замыкающие нули.
Причем все умножения делаются только для последней цифры, без "длинной" арифметики

// отделить степени 2 и 5
// разбить число на C * 2^x2 * 5^x5
void Decompose(int& n, int& x2, int& x5)
{
for (x2 = 0; n%2 == 0; n/= 2, x2++);
for (x5 = 0; n%5 == 0; n/= 5, x5++);
}

// последняя ненулевая цифра n!
int Factorial(int n)
{
int res = 1, n2 = 0, n5 = 0;
for (int i = 2; i <= n; i++)
{
int r= i, x2, x5;
Decompose(r, x2, x5);
// отдельно домножаем степени 2 и 5, отдельно остальное
res= (res * r)%10; // взять последнюю цифру
n2+= x2;
n5+= x5;
}

// домножить на 2 или 5
if (n2 > n5)
for (int i = 0; i < n2-n5; i++)
res= (res * 2)%10; // взять последнюю цифру
else
if (n2 < n5)
for (int i = 0; i < n5-n2; i++)
res= (res * 5)%10; // взять последнюю цифру

return res;
}

P.S. Вычисляя n! для проверки обнаружил неприятный факт - в C Builder нет range checking (проверки переполнения)
Добавлено @ 20:35
Надо выделить степени 2 и 5, встречающиеся в разложениях i = 2, n
на множители, и посчитать их степени отдельно. Потом, если степень 2 больше, домножить на 2 в степени (степень 2 - степень 5), иначе 5 в степени (степень 5 - степень 2), остаток пойдет в замыкающие нули.
Причем все умножения делаются только для последней цифры, без "длинной" арифметики

// отделить степени 2 и 5
// разбить число на C * 2^x2 * 5^x5
void Decompose(int& n, int& x2, int& x5)
{
for (x2 = 0; n%2 == 0; n/= 2, x2++);
for (x5 = 0; n%5 == 0; n/= 5, x5++);
}

// последняя ненулевая цифра n!
int Factorial(int n)
{
int res = 1, n2 = 0, n5 = 0;
for (int i = 2; i <= n; i++)
{
int r= i, x2, x5;
Decompose(r, x2, x5);
// отдельно домножаем степени 2 и 5, отдельно остальное
res= (res * r)%10; // взять последнюю цифру
n2+= x2;
n5+= x5;
}

// домножить на 2 или 5
if (n2 > n5)
for (int i = 0; i < n2-n5; i++)
res= (res * 2)%10; // взять последнюю цифру
else
if (n2 < n5)
for (int i = 0; i < n5-n2; i++)
res= (res * 5)%10; // взять последнюю цифру

return res;
}

P.S. Вычисляя n! для проверки обнаружил неприятный факт - в C Builder нет range checking (проверки переполнения)

Зачем же так сложно.
Всего, при перемножении n! будет встречено множителей с 5-ками: целая часть(n/5) + челая часть (n/25) и т.д.
Это меньше, чем Сумма от 1 до k(k понятно количество членов получившегося ряда) (n/5^i, i=1бл), а это геометрическая прогрессия, значит сумма(Выше) равна n*((1/5-1/5^(k+1))/(1-1/5) < n/4 (это оченка количества 5 во всем числе n!)
Если мы возьмем только первые степени двойки хотя бы от трех множителей из каждого десятка (а там ведь каждый второй - четный), то это будет n*0.3>n*/4=n*0.25
Значит посчитав 5-ки, можно будет отнять только 2 от четных чисел, не считая все множители
Чтобы зря не множить на 10, сразу отнимем их количество от 5, посчитав ряд (я имею в виду точно, а не приближенно)
В результате получится только три цикла, безо всякого вложения.
Например:

Код

Dim l, n, j As Integer Dim i, k, t As Long    t = CLng(NF)    'Посчитаем количество 5    k = 0    While t >= 5        t = Fix(t / 5)        k = k + t    Wend    'Сразу не учтем целые 10    t = CLng(NF)    While t >= 10        t = Fix(t / 10)        k = k - t    Wend        n = 1    l = 1    For i = 2 To CLng(NF)        l = l + 1        If k = 0 Then        Select Case l            Case 5            Case 10                i = i + 1                l = 1            Case Else                n = (n * l) Mod 10            End Select        Else            Select Case l            Case 2                k = k - 1            Case 4                k = k - 1                i = i + 1                l = 5                n = (n * 2) Mod 10            Case 6                k = k - 1                n = (n * 3) Mod 10            Case 10                i = i + 1                l = 1            Case Else                n = (n * l) Mod 10            End Select        End If    Next    n = n Mod 10    Label3.Caption = str(n)

Добавлено @ 12:42
Заметьте, все вычисления идут с типом integer, кроме самого числа, которое может быть и очень большим
Добавлено @ 12:44
Да, кстати, третий раз делить на 2 (case 6) можно ненадо, т.к. мы уже отняли десятки

maxim1000, а по моему дак всё будет не только рациональным, но ещё и целым (ну или типа 123.999999934345793487), я на маленьких числах пробовал.

Aslan74 и ovr2000, я чё-то нить вашего разговора не поймал...

Да суть в порядке чисел, в алгоритмах не используются числа больше сотни, за исключением самого числа N
Именно это я хотел сказать, т.к. все алгоритмы, кроме последних двух , при определенных числах N уходили в переполнение

да когда ж вы читать научитесь. Я уже давно написал решение, которое не переполняется, в нем есть все "гениальные идеи", которые потом всем пришли, и вообще то с математически доказанной верностью.
Похоже кому-то влом смотреть чье-то решение, кроме своего любимого...

GePo
Спасибо за алгоритм! Мне очень помог.

Может, это не совсем то, что нужно, но вдруг кому-нибудь пригодится. У меня есть небольшой пример на Delphi работы с очень большими (по порядку величины) целыми числами. Демонстрируется лишь сам принцип - разделение числа на значущую часть и порядок. Адрес: http://sadovoya.narod.ru/BIG_NUMBERS.ZIP

А вот пример на Java, на своей машине я смог вычеслить 100001! за 9 мин 24 сек:
private String calkFacktorial(String str)
    {
        if(str.equals("0")) return "1";
        BigInteger i = new BigInteger("1");
        BigInteger n = new BigInteger(str);
        BigInteger result = new BigInteger("1");
        
        for(; !i.equals(n); i = i.add(BigInteger.ONE))
        {
            result = result.multiply(i);
        }
        
        return result.multiply(n).toString();
    }

а я за своей за 12 секунд считал