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

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

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

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

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

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

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

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

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

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

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

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

А какой правильный тогда?

Такой, который использует длинную арифметику. Лучше не a делить на i, а ввести некоторое b, которое домножать на i до тех пор пока b < a. (потому что умножение длинных чисел сильно быстрее деления)

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

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

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

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

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

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

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

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

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

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

DaRiYs, я указал что во вторых я показал математику этого оператора
Я оператор с ассемблером связал, так как при изучении его с ним познакомился, а потом обнаружил его в С и Паскале. (вернее в С я про него узнал, но природу процесса понял при изучении ассемблера).

Обычно 64кб ограничение на размер исходника (по ACM'овским правилам).

http://en.wikipedia.org/wiki/ACM_Int...amming_Contest

Так вот, если ограничение всё-таки 64 кб, то спокойно можно сделать таблицу. (длина десятичной записи n!) -> значение n. Длина для всех факториалов начиная с 10! точно различна (для значений меньше можно использовать честный подбор). Длина 2000! - 5737. Элементарная программа на питоне (или любом другом языке, в котором встроена поддержка больших чисел) легко позволяет построить такую таблицу за пару минут.

Ну так у меня ограничение кода до 4 кб. Эт не АСМ а ему подобный

Если очень хочется извратиться и впихнуть всё в 4кб, то можно закодировать таблицу в виде сдвигов между соседними значениями. Т.к. мы умножаем максимум на 2000, то длина изменяется не более, чем на 4 знака каждый раз; но не менее, чем на один. Для хранения этой информации достаточно 2 бит. А для хранения всех сдвигов - 4000 бит, которые можно записать в виде строки (если использовать только печатные символы из нижней половины ascii, чтобы можно было вставить в исходный текст без изменений) всего в 4000/log2(64)=667 символов, ещё 3кб на код останется :). И потом декодировать оттуда нужную информацию небольшим кусочком кода.

Всё решение будет типа такого:
А можно, всё-таки, честно запрограммировать длинное умножение и не париться с извращениями. Ссылку в яндекс, где объясняется, как правильно умножать длинные числа, я уже бросал.

Могу предложить еще вариант без длинной арифметики. Не знаю, будет ли он работать быстрее, поскольку там много вычислений с плавающей точкой... и влезет ли в нужный объем.
Правильно работать он будет, только если число в файле заведомо является факториалом.
Способ: приближенное значение натурального логарифма факториала числа n равно
ln(n!)=1/2(ln(2)+ln (Pi))+ln(n)+n*ln(n)-n
десятичный логарифм равен
Log(n!)=ln(n!)/ln(10)
Количество знаков в факториале будет равно Log(n!)+1, округленному снизу.
Считываем из файла факториал в виде символьной строки. Считаем количество знаков в этой строке. Дальше ищем на отрезке числовой оси (1;2000) нужное нам число n методом деления отрезка пополам. То есть, проверяем числа 1 и 2000 (считаем по формуле), если кол-ва цифр в их факториалах не подходят, берем число в середине отрезка (например 1000), считаем кол-во цифр в его факториале. Если опять не подходит, берем середину отрезка (1;1000) или (1000;2000)-- в зависимости от того, больше или меньше кол-во знаков в числе из файла, чем в 1000! Дальше снова, максимум за 10--12 шагов число n точно определяется
И одна тонкость: для чисел, меньших 7, лучше сохранить факториалы в файле с программой, и сначала проверять не является ли n одним из этих чисел. после чего делить отрезок не от 1 до 2000, а от 7 до 2000. (потому, что факториалы разных чисел, меньших 7, могут иметь одинаковое кол-во знаков)

Мож хтонибудь всетаки напишет код на ассемблере для использования его в С++

Цитата:

Цитата Drongo Можно на примере или прочесть где?! »

Пример для MSVS 6+

Для данного примера разницы между GetSystemTime() и GetLocalTime() нет. А вообще первая возвращает время по Гринвичу UTC, вторая по выбранному свойствах системы часовому поясу.

ivank, а как быть с iostream что б по стандарту? Или это » только в Linux, а micorosoft будет оставлять совместимость в своём компиляторе?
cout удобние printf
Или можно просто вывести значения st.wSecond и st.wMilliseconds через printf не усложняя код?
Со строчкой printf("%s %s",st.wSecond, st.wMilliseconds); компилится, но во время выполнения ошибка естественно

Цитата:

The instruction at "0x00000000" referenced memory at "0x00000000". The memory could not be "read".

Так как не совпадение типов. Чем собственно и удобен cout, что не брезгливый к этому. За это он не в стандарте?

Admiral, Не понял вопроса :) Заголовочный файл iostream есть в стандарте и всегда будет и в gcc и в msvc. Нет в стандарте заголовочного файла iostream.h, который объявляет всё в глобальной области видимости (а не в std), но абсолютное большинство компиляторов его всё равно поддерживают, как раз для совместимости.

Спорное утверждение :) Если попробовать вывести что-то с более-менее сложным форматом, то форматная строка printf намного удобнее (мне во всяком случае).

Все приличные компиляторы умеют выдавать warning на такой код, очень уж распространённая ошибка :)

DaRiYs, за вас никто ничего писать не будет. Вам предложили методы решения задачи (целых 3). Если вы чётко объясните, что вас в них не устраивает (или что непонятно), то можно будет продолжать диалог.

ivank, вопрос навеян этим постом, я об этом в предыдущем посте указал », когда сказал про Linux.
Да я понимаю, что строка printf("%s %s",st.wSecond, st.wMilliseconds); ошибочна. Я к примеру показал сравнения с cout << "\n" <<st.wSecond << " " <<st.wMilliseconds; которой кроме себя самой не нужно приведения типов, что б не вызывать ошибку при выполнении.
Компилятор MS C++ 2008 Express прохлопал всё без Warnings, возможно по дефолтному уровню предупреждений не положено замечать эту строчку как потенциально опасной. Сам я использую в основном printf, но когда отлаживаю программу и ещё не знаю нужной функции приведения типов, использую cout, так как он их щёлкает как орешки и выводит мне нужное значение. Можно и Debug средствами среды узнавать значения переменных, но они не всегда доступны.

Вероятно я там неясно выразился. <iostream.h> официально не существует, просто <iostream> - вполне есть в стандарте.

ivank, не прошло и дня.
printf("time %02u:%02u:%02u:%03u\n", st.wHour, st.wMinute, st.wSecond, st.wMilliseconds);
и ни каких сout с #include <iostream> и using namespace std;
а лишь printf c #include <stdio.h>
нашёл здесь.

А может он описан в С++ стандарте, а <iostream.h> в С?
Или память всё же изменила hasherfrog?

Admiral, нет. В C вообще нет такого понятия, как потоки ввода-вывода. Так что да, у hasherfrog'а изменят память. Со всеми бывает.

ivank, я никого обвинять не собирался. Дело всё в том что после этой темы стал внимательнее смотреть исходники, форумные сообщения на данный сабж. Самым большим удивлением было увидеть iostream.h в печатной литературе. Автора называть не стану, книга ссылается на стандарт ISO/IEC 14882 (1998). Теперь буду иметь ввиду. :happy:

На крайний случай можно глянуть в драфт стандарта (вторая ссылка): http://www.google.ru/search?q=c%2B%2B+standard Никакого iosteam.h там не упоминается, в отличие от iostream (701 страница). Больше половины нынешней печатной литературы по программированию - мукулатура. К сожалению.

я не понимаю - если известен предел, по которому будет высчитываться факториал (тут n до 2000), то почему бы сперва не создать алгоритмик, который запишет текстовый файлик со всеми значениями n до 2000, и потом будет просто вестись вборка.. факториал же можно высчитать только для натуральных чисел - поэтому никаких дробей.
да.. числа огромные будут - но таблица все равно будет не больше 10кб..
или тут нужен именно алгоритм?? а то меня учили идти по пути наименьшего сопротивления и без выпендрежа)

DaRiYs, поскольку вы просите помочь с оптимизацией - уточните условия по максимуму!

В частности - необходимо вычислить один "обратный" факториал или данный алгоритм будет вызываться из цикла?
На входе только факториалы - т.е. можно ли использовать приближённую оценку?

Использование ассемблера заметных плюсов в скорости выполнения не даст. Примитивный цикл с умножением/делением компилируется довольно эффективно.