[C]Implementazione Karatsuba?

[kingal]

ragazzi, non è per studio, ma per puro interesse personale (direte: che interessi che hai! ). Ho trovato un algoritmo particolare per fare delle moltiplicazioni con interi lunghi a piacere, l'algoritmo di karatsuba, volevo provare una possibile implementazione in c.
é un algoritmo ricorsivo con tecnica divide et impera...per poter facilitare il lavoro di "spezzamento" del problema, potrei memorizzare i numeri in array, ogni cifra, una cella, che sarebbe utile anche per rendere davvero arbitraria la lunghezza dei numeri. Avete qualche idea per il resto se conoscete l'algoritmo. Se interessa posso postare qualche informazione in più e una sorta di pseudo-codice.
Grazie

[71104]

per i tuoi scopi il C mi pare fuor di luogo: usa il C++, è inutile mettersi delle limitazioni, qualche feature del C++ potrebbe sempre servire anche per un problema come questo, che è esclusivamente algoritmico.

edit - ecco vedi, una feature del C++ che ti serve assolutamente è la classe vector

[kingal]

cerco di usare quello che conosco meglio, in ogni caso, non è tanto un problema di vector, o array, mi interessava vedere come guadagno in termini di operazioni e tempo rispetto alla comune moltiplicazione perchè mi sembra molto particolare come algoritmo.

[songoge]

Originariamente inviato da kingal

ragazzi, non è per studio, ma per puro interesse personale (direte: che interessi che hai! ). Ho trovato un algoritmo particolare per fare delle moltiplicazioni con interi lunghi a piacere, l'algoritmo di karatsuba, volevo provare una possibile implementazione in c.
é un algoritmo ricorsivo con tecnica divide et impera...per poter facilitare il lavoro di "spezzamento" del problema, potrei memorizzare i numeri in array, ogni cifra, una cella, che sarebbe utile anche per rendere davvero arbitraria la lunghezza dei numeri. Avete qualche idea per il resto se conoscete l'algoritmo. Se interessa posso postare qualche informazione in più e una sorta di pseudo-codice.
Grazie

Se sei in grado di fare uno pseudo-codice di questo algoritmo, che difficoltà hai nel tradurlo in c?

[kingal]

MOLTIPLICAZIONE(A, B, N) :
if (N == 1)
return (A * B);
else
// dividi A e B in due meta' uguali A1, A2 e B1, B2 rispettivamente
X = MOLTIPLICAZIONE(A1, B1, N/2);
Y = MOLTIPLICAZIONE(A2, B2, N/2);
Z := MOLTIPLICAZIONE_VELOCE(A1+A2, B1+B2, N/2) - X - Y;
return X * DIECI_ENNE + Z * DIECI_ENNE_MEZZI + Y;

Non mi sembra proprio così immediato passare da questo ad una implementazione vera e propria.