[Algorytmy] Konwersja olbrzymiej liczby na postać binarną

[adambak]

Mam zadanie w którym największą trudnością jest zamiana olbrzymiej liczby na postać binarną. Liczba ta może wynosić nawet \(\displaystyle{ 2^{32000}}\).. W dodatku limit czasu jest surowy.. Podpowiedzią jest aby wczytać tą liczbę jako łańcuch znaków po czym podzielić ją na integery. Następnie wykonać konwersję na postać binarną na tychże integerach i po kłopocie.. Problem w tym, że zupełnie nie wiem jak taka konwersja ma przebiegać. Mógłby ktoś mi to przybliżyć na przykładzie? Powiedzmy że wczytujemy liczbę: 11347882. Następnie dzielimy ją na inty przy podstawie 1000 i mamy liczbę: 11-347-882 (podstawa 1000, myślniki oddzielają kolejne komórki). Jak będą teraz wyglądać operacje po których otrzymam tą liczbę w postaci dwójkowej?

[PMichalak]

Raczej nie ma sensu trzymanie liczb jako łańcuch znaków, trzymaj je jako tablicę long longów i jako podstawę możesz obrać np. \(\displaystyle{ 10^{9}}\), wtedy dodawanie będzie działało ~10 razy szybciej a mnożenie ~100 razy szybciej. Wtedy jesteś w stanie dzielić przez małe liczby (\(\displaystyle{ <10^{9}}\)) w czasie \(\displaystyle{ O(n/c)}\), gdzie c to rozmiar long longa takie dzielenie wykonasz O(n) razy, więc powinno się zmieścić w limicie. Jako n rozumiem długość liczby, która jest rzędu logarytmu z niej. Dawałoby to złożoność \(\displaystyle{ O( \frac{n^{2}}{c})}\).

[sonicwork]

a jak robi się tą tablice long longów, odczytuje i wykonuje na niej obliczenia ? mógłby ktoś wrzucić przykładowy kod najlepiej w c/c++?

[adambak]

w sumie o to mi chodziło w temacie.. nie problem gdybać, ale JAK to zrobić? jak wyglądają takie operacje na liczbach które reprezentujemy w postaci tablicy long longów.. odczytać nie jest problem - można wczytać liczbę do tablicy charów i potem iść przez nią po jednej cyfrze.. 18 cyfr na jednego long longa i idziemy dalej w tablicy long longów.. ale już operacje na takich liczbach nie są dla mnie takie oczywiste.. pomoże ktoś?

PS dzięki sonicwork, za odświeżenie tematu -- 27 sie 2011, o 19:59 --nawet myślę, że wcale żaden kod nie jest potrzebny, ale gdyby tak pokazać na przykładzie dwie liczby i to jak zostały podzielone na long longi (na potrzeby tłumaczenia mogą być to mniejsze liczby np 4-cyfrowe) i jak na czymś takim wykonywać obliczenia.. bardzo by to pomogło

[Zordon]

czy to jest zadanie ze spoja? jeśli tak to daj linka do treści, zobacze moje rozwiązanie i podpowiem

[adambak]

i tak i nie pomysł na temat wziął się z tego zadania: ale jako że już je zaliczyłem na maksimum punktów to postanowiłem problem uogólnić i napisać z prośbą o pomoc.. moje rozwiązanie do tego zadania bazuje na podpowiedzi w treści - tzn wczytuję liczbę jako string i zamieniam na postać binarną dzieląc pod kreską, dalej wiadomo co.. czas słabiutki.. pomyślałem, że może warto by było reprezentować tą liczbę jako właśnie tablicę long longów i korzystając z tego, jak szybkie są operacje na intach (przesunięcia chyba się przydadzą), znacznie przyspieszyć algorytm.. od dawna zabieram się za porządne i szybkie napisanie klasy bignumów, ale jakoś tak nie wychodzi

[Zordon]

bignumy się robi tak, że masz vector intów v, który przedstawia liczbę:
\(\displaystyle{ v[0]+v[1]B+...+v[n]B^n}\), gdzie za B najczęściej przyjmuje się (tzn. ja tak robię) \(\displaystyle{ 10^9}\). Dlaczego inty, a nie long longi? Bo long longi zajmują dużo miejsca, a praktycznie więcej i tak się w nich nie mieści, bo nie pomnożysz dwóch long longów rzędu \(\displaystyle{ 10^{10}}\) (przepełnienie), a inty \(\displaystyle{ <10^9}\)pomnożysz, wyjdzie co prawda long long, ale to akurat nie szkodzi (widać przy implementacji).
Jak teraz przekonwertować to na liczbę binarną? Normalny algorytm jest taki:

Kod: Zaznacz cały

bin(0)=""
bin(x)=bin(x/2)++(x%2)

Czyli trzeba wykonać aż \(\displaystyle{ log x}\) dzieleń przez 2, a złożoność dzielenia bignuma v przez 2 to \(\displaystyle{ O(v.size()\cdot log(10^9))}\). Można to znacznie poprawić wyznaczając jednocześnie 29 cyfr binarnych zamiast jednej .

Kod: Zaznacz cały

bin(0)=""
bin(x)=bin(x/2^29)++(x%2^29)

z tym, że napis \(\displaystyle{ (x\% 2^{29})}\) traktujemy jako zapis binarny tej liczby.
Dlaczego akurat 29? Bo \(\displaystyle{ 2^{29}<10^{9}}\), a dzielenie bignuma przez liczbę \(\displaystyle{ <10^9}\) jest proste, a dzielenie przez coś większego trudne .
czyli mamy koszt około \(\displaystyle{ v.size()}\) (bo mniej więcej po każdym kroku v skróci się o 1)
U siebie w submicie widzę podejście z dzieleniem przez 2, ale przechodzi z czasem <2s

edit: czyli wszystko sprowadza się tutaj do dzielenia bignuma przez małą liczbę, to się robi standardowo, mniej więcej jak w szkole podstawowej