Zabawne wyzwanie. :)
Zakładam, że chcesz liczb całkowitych o dowolnej długości. Proponuję następujące podejście:
Rozważ binarną naturę typu danych „int”. Pomyśl o użyciu prostych operacji binarnych do emulacji tego, co robią obwody w twoim procesorze, gdy dodają rzeczy. Jeśli jesteś zainteresowany bardziej szczegółowymi informacjami, rozważ przeczytanie tego artykułu na Wikipedii o pół-dodawaczach i pełnododatkach . Będziesz robić coś podobnego, ale możesz zejść na tak niski poziom - ale będąc leniwym, pomyślałem, że po prostu zrezygnuję i znajdę jeszcze prostsze rozwiązanie.
Ale zanim przejdziemy do szczegółów algorytmicznych dotyczących dodawania, odejmowania, mnożenia, znajdźmy jakąś strukturę danych. Prostym sposobem jest oczywiście przechowywanie rzeczy w std :: vector.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};
Możesz rozważyć, czy chcesz utworzyć wektor o stałym rozmiarze i czy chcesz go wstępnie przydzielić. Powodem jest to, że dla różnych operacji będziesz musiał przejść przez każdy element wektora - O (n). Możesz chcieć wiedzieć od razu, jak skomplikowana będzie operacja, a ustalone n właśnie to robi.
Ale teraz do niektórych algorytmów operujących na liczbach. Możesz to zrobić na poziomie logiki, ale użyjemy tej magicznej mocy procesora do obliczenia wyników. Ale to, co przejmiemy z logicznej ilustracji Half- i FullAdders, to sposób, w jaki radzi sobie z przeniesieniami. Jako przykład zastanów się, jak zaimplementowałbyś operator + = . Dla każdej liczby w BigInt <> :: value_, dodajesz je i sprawdzasz, czy wynik daje jakąś formę przeniesienia. Nie będziemy robić tego bitowo, ale polegamy na naturze naszego BaseType (czy to długiego, int, krótkiego czy cokolwiek): przepełnia.
Z pewnością, jeśli dodasz dwie liczby, wynik musi być większy niż większa z tych liczb, prawda? Jeśli tak nie jest, wynik przepełnił się.
template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8;
}
else carry = 0;
}
return *this;
}
Druga operacja arytmetyczna przebiega analogicznie. Heck, możesz nawet użyć stl-functors std :: plus i std :: minus, std :: times i std :: divides, ..., ale pamiętaj o przeniesieniu. :) Możesz również zaimplementować mnożenie i dzielenie za pomocą operatorów plus i minus, ale jest to bardzo powolne, ponieważ spowoduje to przeliczenie wyników, które już obliczyłeś w poprzednich wywołaniach do plusa i minusa w każdej iteracji. Istnieje wiele dobrych algorytmów do tego prostego zadania, użyj Wikipedii lub sieci.
I oczywiście powinieneś zaimplementować standardowe operatory, takie jak operator<<(po prostu przesuń każdą wartość w value_ w lewo dla n bitów, zaczynając od value_.size()-1... och i pamiętaj o przeniesieniu :), operator<- możesz nawet trochę zoptymalizować tutaj, sprawdzając przybliżona liczba cyfr z size()pierwszą. I tak dalej. Następnie uczyń swoją klasę użyteczną, zaprzyjaźnij się ze std :: ostream operator<<.
Mam nadzieję, że to podejście jest pomocne!