There is a site that describes a method to do different types of interpolation with only addition. And it's a site by an ARM programmer too!
I know it's only interpolation, but faster interpolation would mean faster drawing, right?
His site also has an article on fast circle filling, an algorithm which might be adapted for other implicitly defined figures (i.e. defined by a function such as f(x,y)<0).
I actually wrote a Perlin Noise generator a while back using this technique to calculate a high-quality (cubic interp that is) fixed-res Perlin Noise for the PPC. I can post the source and/or binaries somewhere if anyone wants it. It also has a *very* simple script parser (two actually, a C-like one and one that is very similar to FORTH). If you want it, be forewarned, the coding is *very very very* bad.
And if I understand it right, you could probably use it to make a mix between persp-correct texmapping and affine. Just calculate the deltas for a quadratic (or cubic or higher if you want) approximation of the texture co-ords, and use this technique to interpolate. No divs or muls, and it would probably look better than affine.
[edit]Oops, I took a while to post and was beaten to it
