On piclist.com we find lots of basic arithmetic routines including multiplication of two 4 bit numbers giving an 8 bit result . It gives detailed derivation of his code which is small and fast, indeed.
But we can do better! Since this article was published Microchip has brought the enhanced baseline PIC to market which has competitive price, larger instruction set, and more special function registers with increased functionality. This gives the option of simple and fast table lookup in program memory.