Podstawy systemów liczbowych w BigIntach

Witam

Zastanawiam się, jak mając na wejściu string z cyframi w systemie dziesiętnym, przekonwertować je na system o podstawie 2^{n. Konkretniej, chcę napisać w C++ arytmetykę dla dużych liczb ale chciałbym, żeby podstawą było 2}32, a nie np 1.000.000, gdzie konwersja ze stringa byłaby stosunkowo prosta. Warto sobie w ogóle zawracać głowę tym, żeby mieć podstawę, która jest potęgą dwójki? Łatwiej byłoby na pewno zaimplementować wtedy przesunięcie bitowe no i zysk pamięciowy byłby. Docelowo ma mi to pomóc przy redukcji montgomery'ego.

Pozdr

Każdy char ze stringa przerób na byte reprezentujący cyfrę. Wygeneruj sobie kolejne potęgi dwójki w reprezentacji dziesiętnej (poprzez dodawanie do siebie z przeniesieniem), aż dojdziesz do potęgi większej od wejściowej liczby (zwykłe strlen i strcpy tu wystarczą). Potem odejmuj po kolei największe potęgi dwójki jakie tylko się da.

Jeśli od razu chcesz oszacować wielkość liczby po skonwertowaniu to podziel długość stringa przez log2 10.

Jeśli chcesz oszczędzić pamięć przy konwersji to zamiast generowania wszystkich potęg dwójki, pamiętaj tylko ostatnią, a potem ją mnóż/ dziel przez 2. Mnożenie/ dzielenie przez 2 jest stosunkowo proste.

Jeśli chodzi o arytmetykę (dodawanie, odejmowanie, mnożenie i dzielenie), to najprostszym rozwiązaniem wydaje się być przechowywanie tych liczb w tablicach bajtów. Przejście ze string do byte[] to żaden problem. Wielkość tablicy określa maksymalną ilość cyfr, z których składa się liczba.

Wykonanie działania, to wykonanie operacji na dwóch takich tablicach.

Dodawanie i odejmowanie jest najprostsze, bo wygląda tak samo, jak każdy się uczył w podstawówce, czyli zapis liczb jedna pod drugą i wykonywanie działania na poszczególnych cyfrach od końca. Mnożenie jest nieco bardziej skomplikowane, bo to jest przemnożenie pierwszej liczby przez każdą cyfrę drugiej liczby i zsumowanie wyników z uwzględnieniem pozycji cyfry w drugiej liczbie. Dzielenie jest najtrudniejsze do zrealizowania (realizacja również w "szkolny" sposób), tylko, że wykonywane jest najdłużej ze wszystkich działań.

W ten sposób można opracować arytmetykę dla liczb systemu o dowolnej podstawie od 2 do 127.

A może po prostu użyj tego:
http://gmplib.org/
:)

Działania na liczbach o podstawie 2^{8, 2}16, 2^32 na pewno będą bardzo szybkie, zwłaszcza gdy napisane w asemblerze. Ale z konwersją na stringa w systemie dziesiętnym będzie już bardzo nieciekawie. Jeżeli więc zamierzasz przeprowadzać dużo obliczeń, a wyświetlać rzadko, może się to opłacić.

A pomogła by mi ta podstawa bardziej niż podstawa np. 1000000, jeśli chciałbym później dokonać redukcji Montgomery'ego. Generalnie będzie mi to potrzebne do obliczeń w skończonych ciałach.

To czemu pytasz, a nie zrobisz?