Jak zaimplementować duży int w C ++

Chciałbym zaimplementować dużą klasę int w C ++ jako ćwiczenie programistyczne - klasę, która może obsługiwać liczby większe niż długie int. Wiem, że istnieje już kilka implementacji open source, ale chciałbym napisać własne. Próbuję wyczuć, jakie jest właściwe podejście.

Rozumiem, że ogólna strategia polega na uzyskaniu liczby jako ciągu, a następnie podzieleniu jej na mniejsze liczby (na przykład na pojedyncze cyfry) i umieszczeniu ich w tablicy. W tym momencie implementacja różnych operatorów porównania powinna być stosunkowo prosta. Moim głównym zmartwieniem jest to, jak wprowadziłbym takie rzeczy jak dodawanie i mnożenie.

Szukam ogólnego podejścia i porady w przeciwieństwie do faktycznie działającego kodu.

Kwestie do rozważenia w przypadku dużej klasy int:

1. Operatory matematyczne: +, -, /, *,% Nie zapominaj, że twoja klasa może znajdować się po dowolnej stronie operatora, że ​​operatory mogą być połączone w łańcuch, że jeden z operandów może być int, float, double itd. .

2. Operatory I / O: >>, << W tym miejscu dowiesz się, jak poprawnie utworzyć klasę na podstawie danych wejściowych użytkownika, a także jak sformatować ją na wyjście.

3. Konwersje / rzutowanie: Dowiedz się, na jakie typy / klasy powinna być możliwa konwersja Twojej dużej klasy int i jak prawidłowo obsłużyć konwersję. Szybka lista zawierałaby double i float oraz może zawierać int (z odpowiednim sprawdzaniem granic) i złożoną (zakładając, że może obsłużyć zakres).

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; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

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!

Jest na ten temat pełna sekcja: [Sztuka programowania komputerowego, tom 2: Algorytmy półliczbowe, sekcja 4.3 Arytmetyka wieloprecyzyjna, str. 265-318 (wyd. 3)]. Inne interesujące materiały można znaleźć w rozdziale 4, Arytmetyka.

Jeśli naprawdę nie chcesz patrzeć na inną implementację, czy zastanawiałeś się, czego masz się nauczyć? Można popełnić niezliczone błędy, a ich odkrycie jest pouczające, a także niebezpieczne. Istnieją również wyzwania związane z identyfikacją ważnych ekonomii obliczeniowych i posiadaniem odpowiednich struktur pamięci, aby uniknąć poważnych problemów z wydajnością.

Pytanie-wyzwanie dla Ciebie: Jak zamierzasz przetestować swoją implementację i jak proponujesz wykazać, że arytmetyka jest poprawna?

Możesz chcieć przetestować inną implementację (bez patrzenia na to, jak to robi), ale zajmie to więcej niż to, aby móc uogólniać bez oczekiwania eksterminującego poziomu testowania. Nie zapomnij wziąć pod uwagę trybów awarii (problemy z pamięcią, brak stosu, zbyt długie działanie itp.).

Baw się dobrze!

dodanie prawdopodobnie musiałoby być wykonane w standardowym algorytmie czasu liniowego
ale w przypadku mnożenia można spróbować http://en.wikipedia.org/wiki/Karatsuba_algorithm

Gdy masz już cyfry liczby w tablicy, możesz dodawać i mnożyć dokładnie tak, jak robiłbyś to odręcznie.

Nie zapominaj, że nie musisz ograniczać się do cyfr 0-9, tj. Używać bajtów jako cyfr (0-255) i nadal możesz wykonywać arytmetykę z długiej ręki tak samo, jak w przypadku cyfr dziesiętnych. Możesz nawet użyć tablicy long.

Nie jestem przekonany, że użycie ciągu znaków jest właściwą drogą - chociaż sam nigdy nie pisałem kodu, myślę, że użycie tablicy bazowego typu liczbowego może być lepszym rozwiązaniem. Chodzi o to, że po prostu rozszerzasz to, co już masz, w ten sam sposób, w jaki procesor rozszerza pojedynczy bit do liczby całkowitej.

Na przykład, jeśli masz strukturę

typedef struct {
    int high, low;
} BiggerInt;

Następnie możesz ręcznie wykonać natywne operacje na każdej z „cyfr” (w tym przypadku wysoka i niska), pamiętając o przepełnieniu:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

To trochę uproszczony przykład, ale powinno być dość oczywiste, jak rozszerzyć do struktury, która ma zmienną liczbę dowolnej bazowej klasy numerycznej, której używasz.

Użyj algorytmów, których nauczyłeś się w klasie od 1 do 4.
Zacznij od kolumny jedności, potem dziesiątek i tak dalej.

Jak mówili inni, zrób to w staroświecki sposób, ale trzymaj się z daleka od robienia tego wszystkiego w bazie 10. Sugerowałbym zrobienie tego wszystkiego w bazie 65536 i przechowywanie rzeczy w szeregu długich pozycji.

Jeśli Twoja architektura docelowa obsługuje reprezentację liczb w formacie BCD (binarnie kodowana dziesiętnie), możesz uzyskać sprzętową obsługę mnożenia / dodawania odręcznego, które musisz wykonać. Sprawienie, aby kompilator wyemitował instrukcję BCD, to coś, co musisz przeczytać ...

Miały to chipy Motorola z serii 68K. Nie żebym był zgorzkniały czy coś.

Moim początkiem byłoby mieć tablicę liczb całkowitych o dowolnej wielkości, używając 31 bitów i 32n'd jako przepełnienia.

Operacją startową byłoby DODAJ, a następnie MAKE-NEGATYWNA, używając dopełnienia 2. Po tym odejmowanie przebiega trywialnie, a kiedy już dodasz / sub, wszystko inne jest wykonalne.

Prawdopodobnie istnieją bardziej wyrafinowane podejścia. Ale byłoby to naiwne podejście logiki cyfrowej.

Możesz spróbować zaimplementować coś takiego:

http://www.docjar.org/html/api/java/math/BigInteger.java.html

Potrzebowałbyś tylko 4 bitów na jedną cyfrę 0 - 9

Tak więc wartość Int może mieć maksymalnie 8 cyfr. Postanowiłem trzymać się tablicy znaków, więc używam dwukrotnie większej pamięci, ale dla mnie jest ona używana tylko 1 raz.

Również podczas przechowywania wszystkich cyfr w jednym int powoduje to nadmierne komplikacje, a jeśli już, może nawet spowolnić.

Nie mam żadnych testów szybkości, ale patrząc na wersję Java BigInteger wygląda na to, że wykonuje strasznie dużo pracy.

Dla mnie robię poniższe

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

odejmij 48 od swojego ciągu liczb całkowitych i wydrukuj, aby uzyskać liczbę dużej cyfry. następnie wykonaj podstawowe operacje matematyczne. w przeciwnym razie zapewnię kompletne rozwiązanie.