Mnożenie, dodawanie itd na wielkich liczbach. Wiem, że można na stringach, ale jest to za wolne. Kalkulatory i podobne korzystają z operacji na bitach, przesunięcia, xor, etc.
Nie wiem jednak czego konkretnie szukać... jaki to jest 'dział' matematyki/informatyki? Muszę napisać coś szybszego niż zwykłe mnożenie w słupku, a nie uśmiecha mi się przekopywanie przez źródła takich kolosów jak choćby GNU bc.
Pisał ktoś coś podobnego? Szukam jakiegoś tropu od czego zacząć...
Załóżmy przypadek liczb dziesiętnych: 123*1001
W systemie dziesiętnym uproszczone obliczenia mogą wyglądać tak: 1231000+1231 = 123000+123 = 123123
Ponieważ drugi czynnik (1001) jest blisko trzeciej potęgi podstawy systemu (10), można dokonać przesunięcia o 3 miejsca i dosumować brakujące składniki.
Podobnie jest z systemem dwójkowym (wszystkie liczby binarnie): 1011 * 1001 = 1011 * 1000 + 1011 * 1 = (1001 shr 3) + 1011 = 101 1000 + 1011 = 110 0011.
Szczawik napisał(a)
...Podobnie jest z systemem dwójkowym (wszystkie liczby binarnie): 1011 * 1001 = 1011 * 1000 + 1011 * 1 = (1001 shr 3) + 1011 = 101 1000 + 1011 = 110 0011.
Wszystko ok, prócz literówki: ma być (1001 shl 3).
Co do autora posta, to chodzi Ci o to, by wykonać mnożenie dwóch liczb szybciej, niż zwykła operacja mnożenia? Czy raczej o to, że nie potrafisz objąć dwóch dużych liczb?
Pozdrawiam.
Dannte napisał(a)
Co do autora posta, to chodzi Ci o to, by wykonać mnożenie dwóch liczb szybciej, niż zwykła operacja mnożenia? Czy raczej o to, że nie potrafisz objąć dwóch dużych liczb?
To drugie. Gdyby można było (w C/C++/Pascalach itp) napisać po prostu: 68432643754632...32132 * 342423 nie było by problemu, ale niestety nie można. Potrafię napisać mnożenie przy użyciu zwykłych tablic znakowych czy stringów, ale do konkretnego zadania jest to zbyt wolne...
Rozwiązanie zaproponowane w poście wyżej jest pewnie szybsze, ale to nadal problem z przechowywaniem wielkich liczb...
Nie wiem, czy rozwiązanie Szczawika będzie szybsze... być może nieznacznie; raczej chodziło o rozumowanie - zakładam, że znasz podstawowe operacje na bitach. Najlepiej jest wziąć pierwszy czynnik (zapisany bitowo w kilku lub kilkudziesięciu bajtach) i podzielić go na składniki, w których najważniejszy bit jest ustawiony, a reszta bitów to zera i przemnożyć przez te kolejne składniki drugi czynnik, czyli przeglądać pierwszy czynnik i gdy natrafi się na jedynkę to przesunąć drugi czynnik o tyle miejsc w lewo, na którym miejscu trafiliśmy jedynkę, itd. Prawdopodobnie będzie trzeba skorzystać z Carry Flag, by sprawdzić, czy nastąpiło przeniesienie, ale dokładnie się na tym nie znam... Może niech deus się wypowie - on jest MasterMind'em z asemblera :P
Dokładnie nie wiem na czym polega (tzn. w jaki sposób mnoży) instrukcja mul, ale takie operacje jak shl i shr są elementarnymi dla liczb 4-bajtowych, więc raczej taka wiedza nic nie pomoże...
Poza tym i tak problemem będzie wyświetlenie tak dużych liczb - i tak będziesz musiał skorzystać z łańcuchów znaków.
Ogólnie ciekawy problem ;)
EDIT: Znalazłem ciekawy sposób: http://en.wikipedia.org/wiki/Karatsuba_algorithm, który na pewno pomoże (prawdę mówiąc pierwszy raz to spotykam - może na studiach będzie o tym więcej ;)). Dzięki temu algorytmowi możesz zamienić mnożenie 2 liczb n-cyfrowych na 3 mnożenia 2 liczb m-cyfrowych (gdzie n = 2m), przez co ułatwić sobie znacznie zadanie. Np. masz do pomnożenia dwie cyfry: x 9-bajtową i y 7-bajtową. Zamieniasz je na 10-bajtowe (poprzez dopisanie do pierwszej jednego i do drugiej trzech pustych bajtów, przez co uzyskujesz x shl 8 i y shl 24), no i rozbijasz je na podaną na wiki sumę: x1y1 shl 10 +(x1y2 + x2y1) shl 5 +x2y2, gdzie x1 to 5 bardziej znaczących bajtów liczby (x shl 8), a x2 to 5 mniej znaczących bajtów liczby (x shl 8); to samo z y1 i y2.
Nie próbowałem tego zaimplementować, ale teraz jest już trochę późno...
Pozdrawiam.
Jeżeli myślimy o naprawdę wielkich liczbach, to żadne bitowe sztuczki nie pomogą. Najbardziej skomplikowaną (czasochłonną) operacją okazuje się mnożenie, by dzielić też okazuje się, że należy efektywnie mnożyć. Zwykłe podejście do mnożenia jest kwadratowe (czas wykonania proporcjonalny do iloczyny długości czynników), okazuje się, że można to robić szybciej, znacznie szybciej. Warto poczytać o sposobie Karatsuby, Tooma i przede wszystkim o splocie poprzez Szybką Transormatę Fouriera (FFT convolution).
Mam doświadczenie w operacjach na dużych liczbach (kilka zadań na studiach z tego robiłem)
Do przechowywania liczby warto stosować tablicę np unsigned int-ów.
Więc do mnożenia najłatwiejszym w implementacji jest algorytm Karatsuby (dziel i rządź). Na odpowiedniej głębokości tego algorytmu włącza się mnożenie szkolne. poza tym są jeszcze algorytmy ToomCook, Szybka Transformata Fouriera (dla bardzo dużych liczb).
Dodatkowo polecam pakowanie kilku cyfr do jednej komórki tablicy (np 9 cyfr dla unsigned int)
Krytyczną część kodu można przepisać w języku asemblera (zawiera on dużo instrukcji przydatnych do obsługi dużych liczb)
W profesjonalnych bibliotekach do obsługi dużych liczb koduje się całą liczbę do postaci binarnej, tak że operacje przebiegają bardzo szybko, jednak implementacja "optymalnej" konwersji systemu liczbowego jest dość trudna.
Dannte napisał(a)
x1y1 shl 10 +(x1y2 + x2y1) shl 5 +x2y2
Późno już było i dlatego wkradł tu się mały błąd: powinno być shl 80 i shl 40. Za bardzo próbowałem to uprościć ;)
Ale ogólnie rzecz biorąc, to niepotrzebne są w ogóle operacje na bitach, bo można sprowadzać mnożenie dowolnie dużych liczb, do pewnej liczby mnożeń liczb z zakresu 1-10, a jako wynik takiego mnożenia można sięgnąć do wcześniej zaimplementowanej 100-elementowej tablicy przechowującej tabliczkę mnożenia i wyjdzie na to, że nie potrzeba żadnego mnożenia (hmm... oprócz mnożenia indeksów :P). Jednak mówię tu o Karatsubie; do reszty nie zaglądałem.
No to teraz powinno dać radę zrobić wszystko jak trzeba.
Pozdrawiam.