W wolnym czasie przygotowuję się do pytań z wywiadu, takich jak: zaimplementować mnożenie liczb reprezentowanych jako tablice cyfr. Oczywiście jestem zmuszony napisać to od zera w języku takim jak Python lub Java, więc odpowiedź typu „użyj GMP” jest niedopuszczalna (jak wspomniano tutaj: Zrozumienie algorytmu Schönhage-Strassena (ogromne mnożenie liczby całkowitej)).
Do czego dokładnie range rozmiarów tych 2 liczb (tj. liczby cyfr), powinienem wybrać
- Algorytm klasy szkolnej
- Algorytm Karatsuba
- Toom-Cook
- Algorytm Schönhage – Strassen?
Czy Schönhage – Strassen O(n log n log log n) zawsze dobre rozwiązanie? Wikipedia wspomina, że Schönhage – Strassen jest wskazany w przypadku liczb powyżej 2^2^15 do 2^2^17. Co robić, gdy jeden numer jest śmiesznie ogromny (np. 10,000 do 40,000 cyfry dziesiętne), ale druga składa się z kilku cyfr?
Czy wszystkie te 4 algorytmy łatwo się równolegają?
Odpowiedzi:
1 dla odpowiedzi № 1Możesz przeglądać źródło GNU Multiple Precision Arithmetic Library i zobaczyć ich progi przełączania między algorytmami.
Bardziej pragmatycznie powinieneś po prostu profiluj swoją implementację algorytmów. GMP stawia los wysiłku w optymalizację, więc ich algorytmybędą miały różne stałe czynniki niż twoje. Różnica mogłaby z łatwością przesunąć progi o rząd wielkości. Dowiedz się, gdzie krzyżują się czasy, gdy zwiększa się rozmiar wejściowy Twój kod i odpowiednio ustaw progi.
Myślę, że wszystkie algorytmy są podatneparalelizacja, ponieważ są one w większości złożone z przejść dzielących i podbijających. Pamiętaj jednak, że równoległość to kolejna rzecz, która znacznie zmieni progi.