Chcę poznać różne technikiużywane do wykonywania operacji arytmetycznych na bardzo dużych liczbach całkowitych w C. Jedna, o której wiem, używa łańcucha do przechowywania liczby i definiowania operacji dodawania, odejmowania itp. Nie jestem zainteresowany korzystaniem z bibliotek, pytanie dotyczy wyłącznie wiedzy. Proszę zaproponować inne zastosowane metody / techniki.
Odpowiedzi:
3 dla odpowiedzi № 1Możesz przejść tak niski poziom, jak reprezentowanie swojegoliczby całkowite jako tablica bajtów i wykonuj wszystkie operacje (takie jak dodawanie, odejmowanie, mnożenie, dzielenie lub porównywanie), tak jak robi to CPU, na poziomie słów.
Najprostsze algorytmy służą do dodawania i odejmowania, w których po prostu dodajesz lub odejmujesz cyfry po kolei, przenosząc w razie potrzeby.
Liczby ujemne można przedstawić jako uzupełnienie 2.
Dla porównania po prostu porównujesz cyfry najwyższego rzędu, aż do znalezienia różnicy.
W celu zwielokrotnienia najprostszym algorytmem (i najwolniejszym), jaki można zastosować, jest wielokrotne dodawanie.
W przypadku podziału rzeczy są nieco bardziej skomplikowane niż mnożenie, patrz: http://en.wikipedia.org/wiki/Division_algorithm
Częstym zastosowaniem tego jest kryptografia klucza publicznego, której algorytmy często wykorzystują arytmetykę z liczbami całkowitymi zawierającymi setki cyfr.
Sprawdź w dokumentacji OpenSSL BIGNUM: https://www.openssl.org/docs/crypto/bn.html
1 dla odpowiedzi nr 2
Możesz użyć 3 połączonych list, jednej dla liczby A, jednej dla liczby B i jednej dla wyniku.
Następnie odczytujesz każdą cyfrę jako znak wprowadzony przez użytkownika, czynisz ją liczbą całkowitą i zapisujesz ją w nowym węźle na liście, odpowiadającym liczbie, którą odczytujesz w tej chwili.
I na koniec po prostu napiszesz jako funkcjeoperacje dodawania, odejmowania itp. W każdym z nich postępujesz zgodnie z ich odpowiednim algorytmem, którego nauczyłeś się w szkole, zaczynając od węzła LSB, aż do węzła MSB, zawsze pamiętając o podstawowych mocach każdej liczby (1 węzeł * 10 ^ 0, 2 węzły * 10 ^ 1 , 3 węzeł * 10 ^ 2, ..., n węzeł * 10 ^ n).