TMUL – Not so fast multiplication

Implementując szkolne mnożenie pisemne nie da się rozwiązać tego zadania w czasie oczekiwanym przez spoj, nawet stosując obliczone wcześniej tablice modulo i mnożenia (próbowałem!).

 

Tutaj nie ma sensu wymyślanie własnego alogorytmu, conajwyżej można napisać własną implementację jednego z najszybszych znanych algorytmów:

 

1) Schönhage-Strassen SSA
2) Tom-Cook
3) Karatsuba – Karatsuba c implementation
4) FFT  –   Mutliplication using fft

 

Warto pamiętać że każdy z tych algorytmów ma swój przedział w którym jest najlepszy, ale dla tego zadania wszystkie powyższe będą ok.

 

Zadanie można submitować również w Javie, a ta w klasie BigInteger udostępnia metodę multiply() która dopasowuje rozmiar podanych liczb do najszybszych znanych algorytmów, ale to trochę mało dydaktyczne.

 

Źródła:
Przydał się parę razy do testów:
Rozpisanie istniejących algorytmów:
1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s