Is there any efficient C/C++ implementation or algorithm descritpion for iterative Karatsuba w/o using stack/queue to simulate the function stack in recursive Karatsuba?
Suppose F x G = (F_1 + F_2 x^n) x (G_1 + G_2 x^n), where F and G are polynomials of degree (2n-2).
My hunch is to keep in mind the size & index of the current two operands F_i and G_i. The iterative Karatsuba starts with the multiplication of the smallest operands. Once the index is even, calculate ((F_1 + F_2) x (G_1 + G_2)), merge it with (F_1 x G_1) and (F_2 x G_2), double the "size", and halve the "index".
The problem is that the calculation of ((F_1 + F_2) x (G_1 + G_2)) need another (size, index). I'd like to directly append (F_1 + F_2)/(G_1 + G_2)$ to the end of the F/G-array. In that case, how to deduct the new (size, index) from the old one once the calculation completes?
