Yo yo yo sup I’m back! – and ready to rock and roll. If you’re reading this, some general advice is to stop now and go do something useful, this post was not written with you in mind. Truth be told, you’ve probs arrived here by accident. If you’re not reading this, congrats! You’ve come to the right place.
To multiply A and B
To multiply integers
You want to divide,
Split into two or three parts,
Or four or more, you decide.
First put them in binary
Then make even splits:
A1 and B1 are easy,
Just write each as it is;
Now we must consider
What powers of 2
We must divide the other parts by
So they’re integers size n/(2^p)
Now multiply all out
A, B rewritten as above
Replace opposite multiplications
With pairs and minuses to spread da love.
Now all is done
We can find T(n) w.r.t. n/p
And solve the recursive relationship:
It’s quicker, you see!