Форум программистов, компьютерный форум CyberForum.ru

Большие факториалы - C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.88
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
02.09.2011, 15:32     Большие факториалы #1
Помогите написать программу,котороя щитает большые фактуриалы(100!,200! и тд)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.09.2011, 15:32     Большие факториалы
Посмотрите здесь:

Факториалы! C++
большие массивы C++
C++ Слишком большие программы!
C++ Большие-маленькие
Факториалы... C++
C++ Факториалы
Большие числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2011, 09:49     Большие факториалы #21
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
03.09.2011, 09:53     Большие факториалы #22
Цитата Сообщение от iama Посмотреть сообщение
что оптимальное умножение длинного на короткое можно сделать не больше, чем за size
В зависимости от способа хранения длинного. Если оно представлено одним числом, то не более чем за n, если массивом(как у меня), то мне его сложность будет О((Kx - Ny)*n), где Kx - количество задействованных элементов, Ny - количество младших нулей, n - основание факториала. И следует заметить, что K и N все время увеличивается
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.09.2011, 12:06     Большие факториалы #23
Цитата Сообщение от iama Посмотреть сообщение
KING1994, не задумывались, почему гугл не возвращает факториалов чисел, больших 170?
Гугл не возвращает, зато возвращает bing.

Добавлено через 55 секунд
http://www.wolframalpha.com/bing/?i=999!
Вот сайт для вычислений факториалов

Добавлено через 1 минуту
Цитата Сообщение от Dani Посмотреть сообщение
Гугл не возвращает, зато возвращает bing.
Возвращает до 815!
ValeryLaptev
Эксперт С++
1012 / 791 / 46
Регистрация: 30.04.2011
Сообщений: 1,601
03.09.2011, 13:41     Большие факториалы #24
Цитата Сообщение от KING1994 Посмотреть сообщение
long double +/- 1,1810e-4932-+/-1,1810e+4932(надеюсь ети позначки вам знакомы)-ето диапазон значений лонг дабл
Не все компиляторы это поддерживают.
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:09  [ТС]     Большие факториалы #25
Ну вот посидел немного написал порогу которая щитает любые фактуриалы за принципом умножения и додавание в столбец вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "stdafx.h"
#include <iostream>
#include<conio.h>
using namespace std;
long int vvid,m[1000000],n[1000000],h[1000000],q[1000000],sum,sum1,ost,ost1;int i,j=0,x,y,z,k=0,v,L,b,K,k1,w,c=0,r=0;
int main()
{
    cin>>vvid;
    m[999999]=1;n[999999]=1;j=999999;z=999999;h[999999]=0;b=j;
for(i=2,y=j;i<=vvid;i++)   
{
    y=j;z=j;v=j;L=j;b=j;w=j;K=j;
    if(i<=10)
       {
        do{m[z]*=i;z--;}while(z>=0);
            do 
            {
            if(m[y]>=10)
            {ost=m[y]%10;m[y]-=ost;m[y]/=10;m[y-1]+=m[y];m[y]=ost;}y--;
            }while(y>=0);
       }
     else if(i>=11)
         { 
            sum=i;
             sum=i;ost1=sum%10;sum1=(sum-ost1)/10;k=0;r=0;
            do{n[z]=m[z];n[z]*=ost1;z--;}while(z>=0);
            do 
            {
            if(n[y]>=10)
            {ost=n[y]%10;n[y]-=ost;n[y]/=10;n[y-1]+=n[y];n[y]=ost;}y--;
            }while(y>=0);
            do{h[b-1]=m[b];h[b]*=sum1;b--;}while(b>=0);
            do 
            {
            if(h[v]>=10)
            {ost=h[v]%10;h[v]-=ost;h[v]/=10;h[v-1]+=h[v];h[v]=ost;}v--;
            }while(v>=0);   
            do{q[w]=n[w]+h[w];m[w]=q[w];w--;}while(w>=0);
            do 
            {   
            if(m[K]>=10)
             {ost=m[K]%10;m[K]-=ost;m[K]/=10;m[K-1]+=m[K];m[K]=ost;}K--;
             }while(K>=0);
             
        }
}
while(m[c]==0)c++;
    cout<<endl;
    if(vvid>=11)
    {for(k1=c;k1<=j;k1++)
    cout<<m[k1];
    cout<<endl;}
    else if(vvid<=10)
        for(k1=c;k1<=j;k1++)cout<<m[k1];
    getch();
    return 0;
}
есть немного лишних переменных но я нехотел розбиратса)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
04.09.2011, 23:13     Большие факториалы #26
Работает медленно, на ******** есть задача, про факториалы - вычислить факториал n (n<=1000), во времени ограничение - 1 секунда. А тут на 1000 работает уж точно больше. Вывод: надо писать версию 2.0 - модифицированную
KING1994
-68 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
04.09.2011, 23:15  [ТС]     Большие факториалы #27
Dani,я студент 1 курс)мне препод поставил задачу я выполнил) 1000!щитает около 15-20 сек)конешно буду улучшать свои навыки)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
04.09.2011, 23:21     Большие факториалы #28
Цитата Сообщение от KING1994 Посмотреть сообщение
конешно буду улучшать свои навыки)
В этом вся суть
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 08:17     Большие факториалы #29
KING1994, я вообще школота, но у меня 100000! считает меньше чем за 10 секунд.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.09.2011, 10:29     Большие факториалы #30
Цитата Сообщение от Thinker Посмотреть сообщение
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Только делал не через сдвиги. Но все равно быстрее, а памяти так вообще в разы меньше надо
TheAthlete
05.09.2011, 11:48
  #31

Не по теме:

Цитата Сообщение от KING1994 Посмотреть сообщение
Помогите написать программу,котороя щитает большые фактуриалы(100!,200! и тд)
в русском языке нет слова "щитает", есть слово "считает". Просьба писать нормальным русским языком без ошибок. А то во всех постах пишешь "щитает, щитаешь". Не "фактуриалы", а "факториалы"

iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 15:40     Большие факториалы #32
fasked, а процедуры ввода-вывода показать можете?
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.09.2011, 15:42     Большие факториалы #33
Цитата Сообщение от iama Посмотреть сообщение
а процедуры ввода-вывода показать можете?
Сейчас уже нет Исходники (как и все университетские) были утеряны. Но вообще преобразовывал в строку и обратно. Могу на досуге поковыряться и вспомнить, если интересно. Да мне и самому интересно
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 17:39     Большие факториалы #34
fasked, просто я всю жизнь считаю, что вывод длинного числа, хранящегося по основанию http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n - довольно сложная задача
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.09.2011, 17:51     Большие факториалы #35
iama, либо я что-то неправильно понял, либо Вы.
Тут смысл в том, что в одной ячейке массива хранится не одна десятичная цифра, а максимум http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n - 1. И, грубо говоря, для хранения числа http://www.cyberforum.ru/cgi-bin/latex.cgi?12345678901234567890 требуется не двадцать байт памяти, а 16. Плюс при том же сложении, надо выполнить не 20 итераций цикла, а всего 5. Даже на таких грубых подсчетах в 4 раза быстрее. Но это я отошел от темы... Ну а при выводе, тоже самое число хранится в памяти следующим образом:
Код
0AD2h EB1Fh A98Ch AB54h
И собственно для преобразования в hex строку вообще ничего делать не надо, ну а для десятичной строки уже применять арифметику
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 18:00     Большие факториалы #36
fasked, ааа, то есть основание таки будет не степень двойки, а максимальная степень десяти, помещающаяся в данных целочисленный тип, то есть, используя 32-битные беззнаковые числа мы можем хранить в каждой ячейке массива по 9 десятичных разрядов, вы это имеете в виду? Так я так всегда и пишу и с выводом удобно, и по памяти лучше, и размер массива меньше http://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow вычисления быстрее
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.09.2011, 18:10     Большие факториалы #37
Цитата Сообщение от iama Посмотреть сообщение
то есть основание таки будет не степень двойки
Так это и есть основание по-моему Основание это же максимальное возможное значение для одного разряда числа. Здесь получается один разряд числа соответствует одной ячейки массива. Да и все операции выполняются с разрядами (ячейками), а не их частями. Просто символов не хватит, чтобы нарисовать число по основанию http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n. А железка все равно все битами хранит, ну или байтами... это как посмотреть

Цитата Сообщение от iama Посмотреть сообщение
в каждой ячейке массива по 9 десятичных разрядов
Ну вообще немного не так. Десятичная система неудобна в том плане, что в 1 байт памяти помещается число 255, а 256 уже не помещается.
То есть, если взять за основание 256, то 255 (dec) это число из одного разряда, а 256 (dec) уже из двух.

В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
05.09.2011, 18:23     Большие факториалы #38
Цитата Сообщение от fasked Посмотреть сообщение
В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
А вот выводить - не удобней
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.09.2011, 18:30     Большие факториалы #39
Цитата Сообщение от iama Посмотреть сообщение
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
операции по-моему вообще пофигу не в уме же считаем, все машинка делает сама.
Цитата Сообщение от iama Посмотреть сообщение
А вот выводить - не удобней
так как я занимался длинной арифметикой исключительно в криптографическом плане, то ... я ни разу не видел длинных десятичных чисел
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.09.2011, 10:37     Большие факториалы
Еще ссылки по теме:

C++ Большие числа в C
C++ Не большие операции с массивом.
C++ большие числа
C++ Обьясните, почему код так странно считает факториалы
C++ Факториалы числа

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.09.2011, 10:37     Большие факториалы #40
Цитата Сообщение от fasked Посмотреть сообщение
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Это все и так понятно. Думал кто-нибудь на время тестировал когда степень 10^m и степень 2^n.
Yandex
Объявления
06.09.2011, 10:37     Большие факториалы
Ответ Создать тему
Опции темы

Текущее время: 02:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru