PDA

Zobacz pełną wersję : dzielenie wielkich liczb



macol
08-12-07, 21:03
Mam do napisania program(w C/C++) wykazujący czy liczba b jest dzielnikiem liczby a, tzn czy a/b daje/nie daje reszty. Wartości a i b mogą należeć do przedziału liczb całkowitych z zakresu od 1 do 10^1000.

Do tej pory realizowałem to przez dodawanie - zwielokrotniałem b(lub b*(10^n)) aż otrzymałem a lub wartość większą. Niestety nie mieszczę się w zadanym czasie.

Ma ktoś pomysł na inny algorytm?

RRybak
08-12-07, 21:37
Kiedy, lata temu - chyba jeszcze w technikum bawiem si w program do "megawielkich" oblicze. Teoretycznie kady skadnik dziaania mg mie w okolicach 32 tysicy znakw, a wynik musia si mieci w 65 tysicach znakw. Schemat by prosty - naleao rozbi ca liczb na tablic znakw/liczb na pojedyncze cyfry i zastosowa do nich metody oblicze, ktrych ucz w podstawwce. Dodawanie i odejmowanie - supkowo, dzielenie i mnoenie - zgodnie z zasadami przenoszenia/poyczania.
Np.
123.4 * 31.46

'1' '2' '3' '.' '4' '0'
*
'0' '3' '1' '.' '4' '6'
Praktycznie jedynym "problemem" byo wyznaczenie miejsca przecinka, by w obu liczbach by na tym samym miejscu, oraz wyliczy, gdzie bdzie po wykonaniu dziaania (proste - wzi pod uwag dziaanie i ile miejsc jest przed przecinkiem w kadej z nich: )
Poniewa byy to proste operacje, to nawet 30 tysicy mnoe pojedynczych cyfr, uwzgldniajc przeniesienia wykonywao si w mgnieniu oka.
Nie wiem czy o taki pomys Ci chodzi, ale w moim przypadku si sprawdzao. W Twoim pewnie wystarczyo by obliczy miejsce przecinka, i wykona obliczenia tylko do dotarcia do tego miejsca. Jeli po przecinku bdzie zero, to masz dzielnik, jeli nie - to.. go nie masz ;) ..no i dalsze obliczenia s zbdne..

stilgar
09-12-07, 01:21
pora późna, więc nie podam pełnego algorytmu, aczkolwiek ja bym to robił w systemie binarnym - przecież mnożenie i dzielenie można przedstawić jako przesuwanie liczb i łapanie bitów spadających poza zakres. czyli technicznie rzecz biorąc, można w ten sposób po prostu podzielić jedną liczbę przez drugą i zbadac resztę z dzielenia...

no dobra, ide spać, bo chyba już gadam od rzeczy...

no dobra, teraz jak to przemyslalem, to ten pomysl wydaje sie calkiem głupi :)

macol
24-12-07, 12:26
Dzięki za pomoc.

Liczyłem odrobinę na ominiecie dzielenie pisemnego, w końcu i tak, to co zrobiłem przypomina permutacje dzielenia i odejmowania... :D Jak by ktoś był zainteresowany kodem, to będę mógł go udostępnić.. za dwa miesiące :D

szopa123
03-08-08, 20:54
Powiem tylko, że czasami dobrze jest wrócić do podstaw.. matematyki. :p
Dowolną liczbę możemy zapiać na wiele sposobów, np. 10x10+1
A żeby 1 liczba była dzielnikiem drugiej musi zachodzić podobieństwo między tymi liczbami. Jakie... matematyka podpowie... :)