Zadanie SPOJ Dwumian (błąd SIGFPE)

Question

Witam zgłaszam się, ponieważ podczas sprawdzania kodu sędzia pokazuje mi "Błąd SIGFPE".(link do zadania https://pl.spoj.com/problems/BINOMS/ ). Testy przechodzi poprawnie i nie widzę momentu w którym mógłbym dzielić przez 0. Kod do zadania umieszczam niżej! Usunę od razu po uzyskaniu jakieś wskazówki.

Answer 1

Dodaj wypisywanie bufa:

	while (pom <= n)
	{
		cout << buf << " *= " << pom << endl;

Przetestuj ekstremalny przypadek:
1
1000 999

Podpowiem, nawet na największym typie całkowitym w tym przypadku czyli unsigned long long aka uint64_t zmienna przekręci się już przy mnożeniu przez 20. Potem będzie się swobodnie przekręcać aż dojdziemy do 0. 

Czemu w końcu zawsze kończy się na zerze? Sam nie wiedziałem więc wypisałem to binarnie, dla unsigned char'a.

...

208 *= 7:
11010000 = 208
00000111 = 7
10110000 = 176

176 *= 8:
10110000 = 176
00001000 = 8
10000000 = 128

128 *= 9:
10000000 = 128
00001001 = 9
10000000 = 128

128 *= 10:
10000000 = 128
00001010 = 10
00000000 = 0

0 *= 11:
00000000 = 0
00001011 = 11
00000000 = 0

W miare rośnięcia liczby jedynki przechodzą na coraz bardziej znaczące bity aż uciekają całkowicie w pustke przepełnienia :D.

Problemy z przepełnieniami są tutaj ogromne. Zauważ, że w najbardziej ekstremalnym przypadku po skróceniu (1000 500) dalej trzeba będzie obliczyć 500*501*...*1000 / 500!. A 500! = 1.220136825 E+1134. Czyli 1135 cyfrowa liczba :D. Max dla uint64_t to liczba jakoś 20-cyfrowa. Troszke brakuje :D

Odpowiedzią byłaby biblioteka obsługująca bardzo duże liczby. Możesz też sam je obsłużyć w jakiś prymitywny sposób. Idea jest taka, żeby przechowywać liczby w tablicach mniejszych liczb i zaimplementować operacje na tych tablicach. 

Być może istnieje prostsze rozwiązanie. Jak coś wymyślę to będę edytował post.

EDIT: Da się policzyć liczbę kombinacji bez liczenia silni, które powodują bardzo szybkie przepełnienia. Odpowiedź znalazłem tutaj. Jednak jeśli chcesz sam nad tym pomyśleć to nie klikaj bo to odpowiedz dana na tacy. Rozpisz sobie kilka dwumianów po skróceniu to zobaczysz bardzo prosty wzór bez wykorzystywania silni. Można go rozpisać zarówno rekurencyjnie jak i pętlą

https://stackoverflow.com/questions/41225188/issue-with-newton-binomial-coefficient-in-c

Comments

Dzięki wielkie za wskazówkę :D W sumie myślałem czy nie zrobić jakieś funkcji która będzie mi najpierw wykonywała jedno mnożenie z licznika, a następnie jedno dzielenie z mianownika, bo w taki sposób w sumie uniknę sytuacji, że liczba, która ma być odpowiedzią w jakimkolwiek momencie będzie na tyle duża, by wystąpiło jakieś wysypanie. (W zadaniu jest napisane, że liczby dobrane są tak, że ostateczna odp nie przekracza 1 000 000 000).

---

Rozpisz sobie kilka dwumianów po skróceniu to zobaczysz wzór.

---

@RafalS, bardzo dobra odpowiedź!   Przypuszczałem, że chodzi o przekroczenie zakresu inta, ale nie byłem pewien, a nie miałem za bardzo jak odpalić przykładu.

Answer 2

Chyba przekraczasz zakres inta, użyj long int. Ale na 100% nie jestem pewien.

Comments

Tego też próbowałem niestety nic to nie dało :/

---

A próbowałeś robić testy na swoich liczbach n i k, wszystko program liczy OK?

Co robi funkcja skrocenie() ??

---

Na początku chcialem zrobić wszystko na funkcji silna(); ,ale potem zdałem sobie sprawe ze gdy n będzie równe na przykład 1000 to komputer nie obliczy mi silni z tego ,a następnie skróci, bo nie utrzyma w pamięci wynikiu 1000!. Dlatego pomyślałem o takiej funkcji która w dwumianie newtona skraca część obliczeń, ale po dłuższej analizie wydaje mi sie ze i ona jest wadliwa.