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

[ivank]

Время выполнения программы для даной задачи ограничено 1 секундой и обьем кода до 4кб. »
Обычно 64кб ограничение на размер исходника (по ACM'овским правилам).

Что такое контестер, что такое ACM и что такое контестер типра ACM? »
http://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest

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

[DaRiYs]

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

[ivank]

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

Всё решение будет типа такого:

unsigned char[] diff_table="blah-blah blah..."; //667 символов таблицы.

// получить i-й сдвиг из таблицы.
int getDiff(int i) {
unsigned char c = diff_table[i/6] - 32;
int diff = (c >> ((i%6)*2)) & 3;
return diff;
}
// ....
char fac_str[10000];
cin >> fac_str; // зачитываем факториал, _как строку_

int need_len = strlen(fac_str); // длина факториала, для которого надо найти n
int n = 0; // ответ будет здесь
if (need_len <= 8) {
// n <= 10, тупо подбираем
int facn = 1;
int fac = atoi(fac_str);
for (n = 1; facn < fac; ++n) {
facn *= n;
}
} else {
int len = 8; // длина факториала 10
// начинаем подбирать с 11
for (n = 11; len < need_len; ++n) {
len += getDiff(n);
}
}


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

[Altair86]

Могу предложить еще вариант без длинной арифметики. Не знаю, будет ли он работать быстрее, поскольку там много вычислений с плавающей точкой... и влезет ли в нужный объем.
Правильно работать он будет, только если число в файле заведомо является факториалом.
Способ: приближенное значение натурального логарифма факториала числа 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, могут иметь одинаковое кол-во знаков)

[DaRiYs]

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

[Admiral]

Можно на примере или прочесть где?! »
Пример для MSVS 6+
#include <Windows.h>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
SYSTEMTIME st;
GetSystemTime(&st);//GetLocalTime()
cout << "\n" <<st.wSecond << " " <<st.wMilliseconds;
Sleep(1000);
GetSystemTime(&st);//GetLocalTime()
cout << "\n" <<st.wSecond << " " <<st.wMilliseconds;
return 0;
}

Для данного примера разницы между 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, что не брезгливый к этому. За это он не в стандарте?

[ivank]

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

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

Со сторчкой printf("%s %s",st.wSecond, st.wMilliseconds); компилится но во время выполнения, естественно ошибка »
Все приличные компиляторы умеют выдавать warning на такой код, очень уж распространённая ошибка :)

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

[Admiral]

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

[ivank]

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

[Admiral]

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>
нашёл здесь (http://www-uxsup.csx.cam.ac.uk/pub/misc/ntp/ntp3/patches/patch.135).

[Admiral]

<iostream> - вполне есть в стандарте. »
А может он описан в С++ стандарте, а <iostream.h> в С?
ЕМНИП: <iostream.h> используется для С, <iostream> для С++. >> (http://forum.oszone.net/post-357776.html#post357776)
Или память всё же изменила hasherfrog?

[ivank]

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

[Admiral]

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

[ivank]

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

[superlom]

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

[Busla]

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

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

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