Jak liczby całkowite mnożą się w C++?

Question

Zastanawiałem się, jaka metoda została użyta do pomnożenia liczb w C++. Czy to tradycyjne rozmnażanie w tradycyjnej szkole? Fürer's algorithm? Toom-Cook?

Zastanawiałem się, bo będę musiał rozmnażać bardzo duże liczby i potrzebuję wysokiego stopnia wydajności. W związku z tym tradycyjne mnożenie przez długi czas szkolny w szkole średniej O(n^2) może być zbyt nieefektywne i musiałbym uciekać się do innej metody namnażania.

Jakiego rodzaju mnożenia używa C++?

Answer 1

Wydaje się, że brakuje kilku istotnych rzeczy tutaj:

1. Istnieje różnica między rodzimy arytmetyki i bignum arytmetyki.
2. Wygląda na to, że interesuje Cię bignum arytmetyczna.
3. C++ nie obsługuje bignum arytmetyczna. Pierwotne typy danych są ogólnie arytmetyczne dla procesora.

Aby uzyskać arytmetykę bignum (arbitralna precyzja), musisz ją zaimplementować samodzielnie lub skorzystać z biblioteki. (takich jak GMP) W przeciwieństwie do Java i C# (między innymi), C++ nie ma biblioteki dla arbitralnej arytmetycznej precyzji.

Wszystkie te wyszukane algorytmy:

• Karatsuba: O(n^1.585)
• Toom-Cook < O(n^1.465)
• FFT oparte: ~ O(n log(n))

są stosowane tylko do bignum arytmetyczne, które są realizowane w bibliotekach bignum. To, czego procesor używa do swoich natywnych operacji arytmetycznych, jest w pewnym stopniu nieistotne, ponieważ zwykle jest to stały czas.

---

W żadnym wypadku nie polecam próby zaimplementowania biblioteki bignum. Zrobiłem to już wcześniej i jest to dość wymagające (zwłaszcza matematyka). Więc lepiej korzystaj z biblioteki.

Answer 2

Wszystko zależy od używanej biblioteki i kompilatora.

Answer 3

W C++ wielokrotność mnożenia jest obsługiwana przez układ. Nie ma odpowiednika Perl's BigNum w standardowym języku, chociaż jestem pewien, że takie biblioteki istnieją.

Answer 4

Co masz na myśli przez "bardzo duże liczby"?

C++, podobnie jak większość innych języków programowania, używa sprzętu mnożącego wbudowanego w procesor. Dokładnie, jak to działa, nie jest określone przez język C++. Ale dla normalnych liczb całkowitych i liczb zmiennoprzecinkowych, nie będziesz w stanie napisać czegoś szybciej w oprogramowaniu.

Największe numery, które mogą być reprezentowane przez różne typy danych mogą się różnić pomiędzy różnymi implementacjami, ale niektóre wartości są typowe dla 2147483647 int, 9223372036854775807 dla długi i 1.79769e + 308 do podwójnym.

Answer 5

Wykonuje się sprzętowo. z tego samego powodu ogromne liczby nie będą działać. Największa liczba C++ może reprezentować w 64-bitowym sprzęcie 18446744073709551616. jeśli potrzebujesz większych liczb, potrzebujesz dowolnej biblioteki precyzji.

Answer 6

czystym C++ używa instrukcji mult CPU (lub schoolbook mnożenia za pomocą bitshifts i uzupełnień, jeśli CPU nie ma takiej instrukcji.)

jeśli potrzebujesz szybkiego mnożenia dla dużych liczb, chciałbym zaproponować spojrzenie na GMP (http://gmplib.org) i używać C++ interfejs z gmpxx.h

Answer 7

Jeśli pracujesz z dużą liczbą standardowych całkowitą mnożenia w C++ nie będą już działać i trzeba zastosować bibliotekę zapewniającą dowolną dokładnością mnożenie, jak GMP http://gmplib.org/

Również nie powinieneś martwić się wydajnością przed napisaniem aplikacji (= przedwczesna optymalizacja). Te multiplikacje będą szybkie i najprawdopodobniej wiele innych komponentów w twoim oprogramowaniu spowoduje znacznie więcej spowolnienia.

Answer 8

Jak duże są te liczby? Nawet języki takie jak python mogą wykonywać 1e100*1e100 z dowolnie wybranymi liczbami całkowitymi ponad 3 miliony razy na sekundę na standardowym procesorze. To mnożenie do 100 znaczących miejsc zajmujących mniej niż milionową część sekundy. Aby umieścić to w kontekście, istnieje tylko około 10^80 atomów w obserwowalnym wszechświecie.

Napisz, co chcesz osiągnąć, a następnie zoptymalizuj w razie potrzeby.