[C++] Program liczący silnię z dużych liczb
Rafał Bednarski
Jestem początkującym programistą, ale ambitnym ;), więc pomyślałem sobie
żeby napisać program liczący silnię z dużych liczb. Ma obliczyć
powiedzmy silnię z 30 000. Za bardzo nie wiem jak się do tego zabrać.
Myślę, że trzeba stworzyć własny typ liczb, najlepiej tablicę składającą
się w wielu pól i pamiętającą w przybliżeniu 121 000 znaków. Może ktoś
ma lepszy pomysł? Do tej pory udało mi się napisać sam kod
odpowiedzialny za wyliczenie silni. Proszę o dokładny kod, żeby to
wszystko miało ręce i nogi ;)
#include <iostream>
using namespace std;
int main()
{
int liczba;
unsigned long int silnia;
silnia = 1;
cout << endl << "Wprowadź liczbę naturalną, której silnię chcesz
obliczyć: ";
cin >> liczba;
cin.ignore();
for (int i = 1; i <= liczba; ++i)
{
silnia *= i;
}
cout << "Wynik: " << liczba << "! = " << silnia << '\n';
getchar();
return 0;
}
--
Pozdrawiam,
Rafał Bednarski
"M(dot)Ked...@elka.pw.edu.pl
> żeby napisać program liczący silnię z dużych liczb. Ma obliczyć
> powiedzmy silnię z 30 000. Za bardzo nie wiem jak się do tego zabrać.
> Myślę, że trzeba stworzyć własny typ liczb, najlepiej tablicę składającą
> się w wielu pól i pamiętającą w przybliżeniu 121 000 znaków. Może ktoś
> ma lepszy pomysł? Do tej pory udało mi się napisać sam kod
> odpowiedzialny za wyliczenie silni. Proszę o dokładny kod, żeby to
> wszystko miało ręce i nogi ;)
Kiedyś się bawiłem biblioteką BigDigits, która pozwala na operowanie na
liczbach dowolnej wielkości, chyba że pamięć w systemie ci się skończy :)
Jest też biblioteka gmp. W sumie chyba nią właśnie powinieneś się
zainteresować.
A tak na marginesie, to po co ci takie duże wartości silni?
--
Mariusz Kędzierawski
+---------------------------------------------------------------+
tratatata
+---------------------------------------------------------------+
Kyle
> Jestem początkującym programistą, ale ambitnym ;), więc pomyślałem sobie
> żeby napisać program liczący silnię z dużych liczb. Ma obliczyć
> powiedzmy silnię z 30 000. Za bardzo nie wiem jak się do tego zabrać.
> Myślę, że trzeba stworzyć własny typ liczb, najlepiej tablicę składającą
> się w wielu pól i pamiętającą w przybliżeniu 121 000 znaków. Może ktoś
dobrze myślisz, będziesz potrzebował jakąś klasę modelującą zachowanie int'a
> ma lepszy pomysł? Do tej pory udało mi się napisać sam kod
> odpowiedzialny za wyliczenie silni. Proszę o dokładny kod, żeby to
> wszystko miało ręce i nogi ;)
//minimalistyczna wersja będzie zapewne wyglądać jakoś tak
class BigUInt {
std::vector<unsigned> cyfry; //tudzież std::deque
public:
explicit BigUInt(unsigned a=0) : cyfry(1,a) {}
BigInt& operator*=( unsigned other );
friend operator<<( std::ostream& str, const BigUInt& liczba );
};
>
> #include <iostream>
#include <BigUInt.h>
>
> using namespace std;
>
> int main()
> {
unsigned liczba;
BigUInt silnia(1);
> cout << endl << "Wprowadź liczbę naturalną, której silnię chcesz
> obliczyć: ";
> cin >> liczba;
> cin.ignore();
for(unsigned i=1; i <= liczba; ++i)
> {
> silnia *= i;
> }
> cout << "Wynik: " << liczba << "! = " << silnia << '\n';
> getchar();
//a to to skąd ci sie tu wzięło ? <:, jak chcesz tego używać to
'podłącz' odpowiedni nagłówek
> return 0;
//return 0; nie jest konieczny
> }
>
//przy mnożeniu musisz tylko sobie uwzględnić że mnożysz w systemie o
podstawie 2**32 (zakładając 32bity na inta) co może być pewnym
problemem, dlatego lepiej ogranicz wartość wprowadzaną do 2**16 i w
takim systemie mnóż, albo przy mnożeniu poszczególnych 'cyfr' korzystaj
z jakiegoś typu 64 bitowego - żadnych cudów tam nie wymyślaj, mnożenie
pod kreską to najlepsze co możesz zrobić w swojej sytuacji
Rafał Bednarski
> Kiedyś się bawiłem biblioteką BigDigits, która pozwala na operowanie na
> liczbach dowolnej wielkości, chyba że pamięć w systemie ci się skończy :)
>
> Jest też biblioteka gmp. W sumie chyba nią właśnie powinieneś się
> zainteresować.
Dzięki za odpowiedź... będę musiał to przestudiować ;)
> A tak na marginesie, to po co ci takie duże wartości silni?
Dla satysfakcji... nauczę się czegoś i przy okazji sprawdzę wydajność
procka :)
Seweryn Habdank-Wojewódzki
Rzuć okiem na:
http://pl.wikipedia.org/wiki/Silnia/kod
Pozdrawiam.
--
|\/\/| Seweryn Habdank-Wojewódzki
`\/\/
Remek
> program liczący silnię z dużych liczb.
> powiedzmy z 30 000
Obawiam się, że taki program byłby nie
do udźwignięcia przez domowy PC.
Napisałem kiedyś programik, który wywołuje
0FFFFFFFFh razy jedną z funkcji systemowych.
Wykonuje się 27s, co obrazuje ile by trzeba
czasu do liczenia silni z podanej przez Ciebie
liczby, nie wspominając już czy wystarczyłoby
RAM'u do zmagazynowania wyniku.
Do obliczania silni z dużych liczb są wzory
dające jednak przybliżone wyniki.
Jeśli się nie mylę to Twój kod podaje prawidłowy
wynik z liczby max 12d. To świadczy, że operuje
na wielkości dword, czyli na rejestrze 32bit, a
później występuje przekręcenie rejestru i w
efekcie błędny wynik.
--
Remek
Kyle
> Witam!
>
>> program liczący silnię z dużych liczb.
>> powiedzmy z 30 000
>
> Obawiam się, że taki program byłby nie
> do udźwignięcia przez domowy PC.
lol ... mój właśnie udźwignął :p
>
> Napisałem kiedyś programik, który wywołuje
> 0FFFFFFFFh razy jedną z funkcji systemowych.
> Wykonuje się 27s, co obrazuje ile by trzeba
~ 4 * 10**9 operacji to sporo ... ale co to ma do 30k ! ???, twoja
analogia jest chybiona
> czasu do liczenia silni z podanej przez Ciebie
> liczby, nie wspominając już czy wystarczyłoby
> RAM'u do zmagazynowania wyniku.
no nie przesadzaj ...
>
> Do obliczania silni z dużych liczb są wzory
> dające jednak przybliżone wyniki.
>
> Jeśli się nie mylę to Twój kod podaje prawidłowy
> wynik z liczby max 12d. To świadczy, że operuje
> na wielkości dword, czyli na rejestrze 32bit, a
> później występuje przekręcenie rejestru i w
> efekcie błędny wynik.
stąd zapytanie na grupę ... poczytaj dokładnie posta na który
odpowiadasz (dobrze jak poczytasz też inne odpowiedzi)
>
> --
> Remek
>
>
>
Marcin 'Qrczak' Kowalczyk
>> program liczący silnię z dużych liczb.
>> powiedzmy z 30 000
>
> Obawiam się, że taki program byłby nie do udźwignięcia przez domowy PC.
>
> Napisałem kiedyś programik, który wywołuje 0FFFFFFFFh razy jedną z
> funkcji systemowych. Wykonuje się 27s, co obrazuje ile by trzeba
> czasu do liczenia silni z podanej przez Ciebie liczby, nie
> wspominając już czy wystarczyłoby RAM'u do zmagazynowania wyniku.
Jest w zupełności do udźwignięcia. Na moim PC obliczenie silni 30000
zajmuje 6s.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Bob
> Witam!
>
>> program liczący silnię z dużych liczb.
>> powiedzmy z 30 000
>
> Obawiam się, że taki program byłby nie
> do udźwignięcia przez domowy PC.
>
> Napisałem kiedyś programik, który wywołuje
> 0FFFFFFFFh razy jedną z funkcji systemowych.
> Wykonuje się 27s, co obrazuje ile by trzeba
> czasu do liczenia silni z podanej przez Ciebie
> liczby, nie wspominając już czy wystarczyłoby
> RAM'u do zmagazynowania wyniku.
>
A to coś:
http://www.swox.com/gmp/#TRY
wprawdzie odmawia wyświetlenia wyniku 30000!,
ale wyświetla coś takiego:
The result of executing 30000! is:
computation took 28 ms
result is about 121287 digits, not printing it
zatem ani czasu, ani ramu nie potrzeba aż tak dużo.
Robert.
Remek
> poczytaj dokładnie posta na który
odpowiadasz (dobrze jak poczytasz też inne odpowiedzi)
Mógłyś sobie darować takie pouczenia. W dyskusji
biorą udział nie tylko wszechwiedzący jak Ty,
ale również tacy jak ja, którzy wiedzą..., że mało
wiedzą i dlatego pytają, wyrażają wątpliwości i
uczą się od innych.
Pozdrawiam
--
Remek
Remek
> Jest w zupełności do udźwignięcia.
Śledzę Twoje odpowiedzi na grupach i
mam pełną świadomość, że wiesz co piszesz.
Ja walczyłem z takim programikiem w asemblerze
i zbyt daleko nie zaszedłem (początki).
Czy gdzieś można zobaczyć Twój program?
Nie śmiem nawet pomarzyć o źródełku.
Pozdrawiam!
--
Remek
Remek
> Jest w zupełności do udźwignięcia.
Jasne! To nie miała być analogia, a tylko
porównanie. Tak mi się wydawało, że operacje
będą wykonywane na ogromnych liczbach co
poskutkuje długim czasem wykonywania.
Zresztą już ludzie napisali, że stworzyli
takie programy i działają na PC, więc
moje obawy były niesłuszne.
--
Remek
Marcin 'Qrczak' Kowalczyk
> Czy gdzieś można zobaczyć Twój program?
Nie był w C, tylko w moim Kogucie.
Sama artymetyka dużych liczb jest zasługą biblioteki GMP (napisanej
w C ze wstawkami w asemblerze).
W przypadku takiego wielokrotnego mnożenia dużej liczby przez małą
GMP nie ma szans na znaczące optymalizacje; GMP stosuje zaawansowane
algorytmy m.in. do mnożenia dwóch dużych liczb, ale tutaj mamy dużą
mnożoną przez małą, czego i tak nie da się zrobić szybciej niż liniowo
względem długości liczby. Zatem problem w tej skali jest łatwy dla
peceta sam w sobie, każda sensowna implementacja dużych liczb powinna
być szybka.
let t0 = Time();
let x = Product (Between 2 30000);
let t1 = Time();
WriteLine x;
let t2 = Time();
WriteLine (t1 - t0);
WriteLine (t2 - t1);
Seweryn Habdank-Wojewódzki
Marcin 'Qrczak' Kowalczyk wrote:
> let t0 = Time();
> let x = Product (Between 2 30000);
> let t1 = Time();
> WriteLine x;
> let t2 = Time();
> WriteLine (t1 - t0);
> WriteLine (t2 - t1);
Proszę dorzuć ten przykład jako prosty example do Koguta. A tak na marginesie
nie wiem czemu, ale nie działa mi strona WWW o Kogucie na Wikipedii. Kiedy
odpalam ją jako wewnętrzna "Kopia" z google to ja widać, inaczej nic - tylko
niedziałający relink.
Marcin 'Qrczak' Kowalczyk
> A tak na marginesie nie wiem czemu, ale nie działa mi strona WWW
> o Kogucie na Wikipedii.
Została usunięta.
http://en.wikipedia.org/wiki/Wikipedia:Articles_for_deletion/Kogut
Nie brałem udziału ani w zakładaniu, ani w usuwaniu, ale zgadzam się,
że jeszcze nie czas na artykuły encyklopedyczne.