Ускорение поиска числа факториала

[DaRiYs]

Люди помогите сделать бысрый алгоритм нахождения числа из его факториала.
Я писал вот такой код но он оч медленный

#include <iostream.h>
#include <fstream.h>
int faknom(int a)
{
int i=1;
while(a!=i)
{
a=a/i;
i++;
};
return i;
};
int main()
{
int Nfak;
ifstream fin("input.txt");
fin>>Nfak;
fin.close();
ofstream fout("output.txt");
fout<<faknom(Nfak)<<endl;
fout.close();
return 0;
}

В файле input.txt лежит значение факториала N! числа N, а в файле output.txt должно быть записано значение N.
Как ускорить алгоритм расчета?

[Altair86]

Мне кажется, алгоритм расчета тут не ускорить. Если бы числа были большими, можно было бы поискать приближенную формулу для вычисления. А так-- только последовательное деление на целые числа, начиная с 1, все правильно. int 32-разрядные вроде? примерно до 2*10^9-- это факториалы чисел до 12 или 13 только.

[Coutty]

Не понимаю, почему медленно он работает.
Вот пример на JavaScript'е (ну не знаю я C), который отрабатывает мгновенно (учитывайте, что int - не безразмерен):

var fak = 39916800; // можно оформить в виде функции и передавать это число в неё, но для теста пойдёт и простое присваивание. Это число - факториал от 11.
var i = 2;
while(i) {
if (fak == i)
{
alert("Заданное число является факториалом от " + i);
break;
}
if (fak/i == parseInt(fak/i))
fak = fak/i;
else
{
alert("Нет такого числа!");
break;
}
i++;
}

Попробуйте изменить fak, скажем, на 39916801 и число найдено не будет.

[DaRiYs]

Altair86 Нет я помню точно гдето видел чото тип какойто формулы или спец метода. Но не помню где.
По инету шарил но ненашол. :(
Алгоритм быстрее этого точно есть.
Coutty мне нада скорость до 1 секунды, а при некоторых значениях скорость 1,015сек. Ето в моей ситуации неприпустимо. Используются факториалы чисел до 2000, тоесть максимально 2000!

[ivank]

http://en.wikipedia.org/wiki/Factorial#Rate_of_growth

Там есть только приблизительные формулы, для вычисления n! по n, Если вычислять в обратную сторону по требуется на порядок больше операций, чем для честного деления. Потому что, уже указали, что в int поместится только 12!. Т.е. в для такой операции достаточно всего 12 операций делений.

[Drongo]

DaRiYs, мне нада скорость до 1 секунды, а при некоторых значениях скорость 1,015сек. »А как вычислялось время вычисления? Я тоже хочу несколько программ проверить, вернее алгоритмы и сравнить.

[Coutty]

DaRiYs, так вот Altair86 и говорит - в Int влезет факториал не более чем от 12 или 13.

Иногда для скорости можно пожертвовать объёмами. Используйте подстановочные таблицы с заранее сопоставленными величинами (пусть не для всех чисел, а, скажем, каждое двадцатое. Остальные просчитывать).
Алгоритм:
1. Находим число (a), которое меньше полученного из файла (f) (следующее число из таблицы будет уже больше).
2. Определяем сопоставляемое этому значению число (b).
3. И число (a) умножаем на (b++), пока произведение не будет равно или не превысит (f).

Drongo, перед выполняемой функцией определяешь системное время с точностью до миллисекунд, потом то же самое после функции. И сравниваешь значения. Если интересно, ещё по поводу замеров fps могу посоветовать :)

[DaRiYs]

А может этот кусок кода на ассемблере написать? Ток я ассемблера незнаю :( :(

[ivank]

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

[DaRiYs]

DaRiYs, Этот код работает долго для факториалов больше 13, потому что он неправильный. »
А какой правильный тогда?

[ivank]

Такой, который использует длинную арифметику (http://yandex.ru/yandsearch?text=%E4%EB%E8%ED%ED%E0%FF+%E0%F0%E8%F4%EC%E5%F2%E8%EA%E0&rpt=rad). Лучше не a делить на i, а ввести некоторое b, которое домножать на i до тех пор пока b < a. (потому что умножение длинных чисел сильно быстрее деления)

[DaRiYs]

Всеравно исчерпывается лимит времени. :(
Тут полный проход по деления или умножению некатит. Над
какойто иной способ.
А на ассемблере что никто и нескажет как написать?

[Altair86]

А для чисел меньше 12 за сколько времени прога срабатывает?

[Admiral]

На ассемблере (как и в Паскале и в С) есть так называемые операции сдвига:
вправо (shr) и влево (shl). Для десятичной системы это выглядит так
3 shl 5 => (3x(2в пятой степени))
5 shr 3 =>(5/(2в третей степени))
На примере двоичной системе становится ясно откуда они получили своё имя
00010101 shl 3 => 10101000
и в другую сторону при shr
Они могут быть полезны, если придумать как их здесь можно применить.

[DaRiYs]

Че придумывать если я ассемблера незнаю? :(

[mrcnn]

Почему бы не создать список всех факториалов до 2000 в файле!?

номер факториала соответствует номеру строки.
Считываем заданное число, помещаем в строку, определяем длину строки

и начинаем сравнивать длину строки заданного числа с длинами строк в файле,
Начать нужно не с нуля, а со строки номер которой равен длине строки заданного числа.

Если длины строки равны, то номер строки в файле искомый факториал.

Таким образом задача избавляется от чрезмерно быстрого факториального роста. задача сводится к поиску. Можно создать 2000 файлов, чтобы не мучать один файл и сравнивать уже количество байт файла в котором заданное число и количество байт в файле, в котором факториалы. Просто тупо проверяем есть ли файл заданного размера. Без вычислений.

[DaRiYs]

Понимаете ето задача для онлайн контестера тип АСМ. Время выполнения программы для даной задачи ограничено 1 секундой и обьем кода до 4кб. И кроме кода сторонних фаилов использовать нельзя.

[Admiral]

DaRiYs, я указал что как и в Паскале и в С »
во вторых я показал математику этого оператора
3 shl 5 => (3x(2в пятой степени))
5 shr 3 =>(5/(2в третей степени)) »
Я оператор с ассемблером связал, так как при изучении его с ним познакомился, а потом обнаружил его в С и Паскале. (вернее в С я про него узнал, но природу процесса понял при изучении ассемблера).

[mrcnn]

Надо было сразу указывать эти ограничения. Что такое контестер, что такое ACM и что такое контестер типра ACM?

[Drongo]

Coutty, Drongo, перед выполняемой функцией определяешь системное время с точностью до миллисекунд »Если честно, то я не знаю, как его определять?! Можно на примере или прочесть где?! Чтобы доходчиво было.