большая чиселка!

[rukia]

доброе время суток!
есть задание посчитать факториал 100 000! =(
 вот я делаю так:

Код:

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
//чтобы посчитать факториал от х надо совершить х-1 умножений
const int n=35660;// количество разрядов в числе( для факториала 10000! n=35660,дла100000!=456574)
int r=1;
int c[n];//теперь инициализируем начальный массив.
c[n-1]=1;for(int i=n-2;i>=0;i--){c[i]=0;}//в младшем разряде сначала 1, а остальные пока нули
int z=0;//вспомогательная
int x=10000;//x это то число, факториал которого нужен.
for(int i=0; i<x-1;i++)
{r+=1;
for(int k=n-1;k>=0;k--)//поразрядно с конца
{
  int a=c[k]*r+z;
  c[k]=(c[k]*r+z)%10;
  z=a/10;
}
}
ofstream rukia("Fucktorial.txt",ios::out);
if(!rukia)
{
	cerr<<"Oblom!";
}
for(int i=0;i<n;i++)
rukia<<c[i];
return 0;
}//снизойди с ледяных небе

это то, что приходит в голову сразу. оно считает корректно, скажем, 2!, 10!, 15!
весьма быстро считает и 10 000! но когда дело доходит до 100 000!, то виндоус начинает просить прощения и ничего не делает...о.0
я пробовала заменять тип элемента массива на short int, исходя из соображений, что меньше памяти выделять. тогда виндоус не просит прощения и делает фигню.. то есть где-то часа через пол выводит на сто страниц нулей..=(
подскажите, пожалуйста, что надо делать? и почему так? =) может, кто-то уже решал подобную задачу)

[Вад]

А чего удивительного? чем больше аргумент факториала, тем больше на конце нулей.

[rukia]

знаю.. но он выводит т о л ь к о нули... к тому же время работы около получаса, мы даже успели пообедать за то время и чуть про него не забыть. а надо не более 7-8 минут=) алгоритм, чтоли не подходящий?)

[Вад]

Вот тут:

Код:

int a=c[k]*r+z;

правильно я понимаю, что r может достигать 100000? Тогда, думается, скоро понадобится большой перенос в старшие разряды. После каждого умножения - иначе будет переполняться.

[rukia]

аа..) спасибо!
то есть я погорячилась здесь

Код:

int a=c[k]*r+z;

и переполняется "int а"? значит ее тоже надо представить массивом?

[Вад]

Тогда лучше, наверное, развести первый множитель и результат умножения по разным массивам - так будет нагляднее. И после умножения одного разряда потребуется вложенный цикл для переноса (вместо просто вспомогательной z=a/10).

[Crystal]

Здравствуйте! у меня аналогичная проблема. Необходимо вычислить факториал 100000. Написанный мною код правильно считает 20!, 30!.....10000!. а вот  на 100000 выдает ошибку, подскажите пожалуйста как это исправить и правильно ли я делаю???

Код:

#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;

void main()
{int mas[7], i;//массив хранит колич. знаков в значении факториала
mas[6]=1;
for(i=0;i<6;i++)
{
	mas[i]=0;
}

int m;
for(m=2;m<=10;m++)//в данном случае вычисляем факториал 10
{
   for(i=6;i>=0;i--)
	{
		mas[i]=mas[i]*m;
	}
for(i=6;i>=0;i--)
{
	if(mas[i]>9)
		{
			float f=(float)mas[i]/10;
			mas[i]=(mas[i]%10);
			mas[i-1]=mas[i-1]+floor(f);
		}
}
}

ofstream xxx("Faktorial.txt",ios::out);
if(!xxx)
{
	cerr<<"Error!!!";
}
for(i=0;i<7;i++)
xxx<<mas[i];
	
}

[Вад]

Crystal, ровно тот же самый код и та же ошибка - см. выше. Где вы его берёте?

[Crystal]

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

[Вад]

По моим прикидкам, отложенный перенос может переполниться. Экспериментально не проверял Надо у rukia спросить, что получилось

[Crystal]

извините, но что вы имеете в виду под фразой "отложенный перенос"?

[Вад]

Я имел в виду конструкцию с z = a / 10 и переносом этого значения в следующий разряд, суммирования его с произведением там, и так далее.

Однако, и на старуху бывает проруха. Попробовал. Дело оказалось не в том, что я думал. В общем, выкладываю поправленный и немного оптимизированный по времени код (отрабатывает у меня примерно раза в 1,5-2 быстрее):

Код:

// Factor.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    //чтобы посчитать факториал от х надо совершить х-1 умножений
    const int n=500000;// количество разрядов в числе( для факториала 10000! n=35660,дла100000!=456574)

    // выделяем память под массив
    int* c = new int[n];
    //теперь инициализируем начальный массив.
   
    for (int i = 0; i < n; ++i)
        c[i] = 0;
    c[0]=1;
    int z=0; //вспомогательная
    int max = 0;
    int x=100000;//x это то число, факториал которого нужен.
    for(int i=2; i <= x ; ++i)
    {
        for(int k = 0; k <= max; ++k)//поразрядно с младшего
        {
            z = c[k]*i + z;
            c[k] = z % 10;
            z /= 10;
            if (z && k == max)
                ++max;
        }
    }

    ofstream rukia("Fucktorial.txt",ios::out);
    if(!rukia)
    {
	    cerr<<"Oblom!";
    }

    for(int i=max; i >=0 ; --i)
        rukia<<c[i];
    
    // удаляем массив
    delete[] c;
    
    return 0;
}

Со статическим массивом на 500 тыщ элементов мне стек порвало

P.S. Аккурат 456574 байта в файле.

[rukia]

спасибо,Вад!
те первые-неумные-коды похожи были,видимо, потому, что все чайники думают похоже=)
у меня есть еще один вопрос..,.
код с динамическим массивом работает за ~20 мин на 2ядерном компутере. нам дали ограничение в 10 минут. то есть надо оптимизировать. Уменьшение памяти, выделяемой на элемент(то есть  short int c[..], char c[..]почему-то только делает хуже о.0 странно, почему)
наиболее логичным выглядит вариант уменьшить количество эл-тов массива. тоесть, посчитать мегачисло не в 10ной, а в ну.. например 256чной системе счисления. а потом отдельно перевести в 10ную. с переносом не отложенным,а хорошим. ох.. может, есть еще способы? =)

[Вад]

Можно считать "% 1000" или даже "% 10000" в одной ячейке - при умножении на 100000 должно хватить int для переноса (советую проверить ). Только один нюанс - вывод в поток надо сделать аккуратнее - чтобы на каждый разряд, кроме старшего, выводилось ровно 3 или 4 знака соответственно. Умножений станет намного меньше, так что резко возрастёт скорость.

Но, вообще, этот код у меня на Core2Duo отрабатывал минут за 8.

[Sla]

я так понимаю, что результат хранится в строке
В случае появления числа с нулями - запоминать нули, а при выводе их учитывать

[Вад]

Sla, можно, в принципе, и средствами iostream сманеврировать, заставив выводить нужное число символов и дополнять нулями. А можно, конечно, и нули выводить отдельно. Это уж на откуп топикстартеру

[Sla]

а еще можно запоминать один ноль после каждого девятого умножения
или 2 нуля после каждого десятого

Offtopic:

Вопрос: Как быстро умножить на 10 в процессоре который не имеет команд умножения?)
Ответ: Умножить на 8 и дважды прибавить самое себя

Поставлю в угол.

[Вад]

В случае появления числа с нулями - запоминать нули, а при выводе их учитывать

А, я не так понял. Ты предлагал все младшие разряды до первого ненулевого сокращать? Тоже хорошая оптимизация получится на таких масштабах

[rukia]

замечательно)))))
сейчас на пробу сделала по "методу %100" и во время аццкого испытания на том компе,которы считал за 19-20 минут, посчиталось за 645 секунд! (ну.. в смысле, правильно посчиталось)

Но, вообще, этот код у меня на Core2Duo отрабатывал минут за 8.

угум, ради инереса проверили Core2Duo еще быстрее..
 

а еще можно запоминать один ноль после каждого девятого умножения
или 2 нуля после каждого десятого

о, даа. по сути,я даже могу рассчтитать количество нулей вконце для факториала.. например для 500! так: 500\5=100; 100\5=20; 20\5=4; то есть noll=100+20+4=124, что совпадает с экспериментом.
то есть,как только множитель r увеличивается на 5(на 2 он увеличивается тем более, а 2*5=10), то сразу +ноль к концу..и массив можно заполнять получается чтоли в 2 направления? 
спасибо !