[ C ] implementacja długich liczb

mam następujacy problem:

musze zaimplementowac w C mnożenie dlugich liczb (do 50 000 znakow) a za bardzo nie wiem jak sie do tego zabrac. Czy ktos spotkal sie juz z tym problemem?? jakies pomysly?? prosze o pomoc... :|

Np. tak jak sie to robilo w podstawowce - mnozenie pisemne.

pozdrawiam
johny

<url>www.main.edu.pl</url>
Taw w dziale Kursy->Algorytmika jest to ładnie opisane.

Ja bym tylko poradził zamiast
p += a[j]*b[i] + c[j+i];
c[j+i] = p % RADIX;
p /= RADIX

napisać<code>
p += a[j]*b[i] + c[j+i];
t = p/RADIX;
c[j+i] = p - t*RADIX;
p = t;

Będziemy tu być może nawet 2'500'000'000 razy.
Czy istnieje kompilator który by na i86 załatwił to jedną instrukcją dzielenia?

http://carramba.homelinux.org/ftp/4programmers/vlong.zip

kiedys to bylo w downloadzie do dopisania pozostala wciaz oblsuga liczb ujemnych + ew. potegowanie

Link podany przez Krajeka jest rzeczywiście godny polecenia. Warto podumać o Karatsubie, szkoda, że nie wspomniano o FFT. W parę minut napisałem sobie jak może wyglądać mnożenie. 50'000 dziewiątek podnoszę do kwadratu, wyszło 283 sekund, z poprawką Dobrowolskiego 181 sek (warto pamiętać, że dzielenie całkowitoliczbowe jest najwolniejszą operacją na i86).
radix
100 49,86
1000 20,87
10000 11,16
z 4:43 zrobiło się 11 sekund
Mój kompilator bardzo nieefektywnie liczy na 64 bitach. Warto sprawdzić jak twój kompilator (i procesor) sobie z tym radzi. Może się okazać się, że lepiej pozostać przy 32 bitach. Wtedy radix=10'000 jest dobrym wyborem, ponieważ 10'000^{2 < 2}32.
Mnożenie na sposób Fourier'a poradziło sobie w mniej niż sekundę.

http://swox.com/gmp/