With this CPU that supports addition and subtraction, but not bit-shifting, I would assume that there are only a handful of registers available on the chip, which could yield even simple algorithms to be too complicated. I'm not sure C# would be the optimal language for programming this chip. It would also help to know the rest of the constraints that your embedded system has.

Assuming only 8 bit integers (a chip with no bit shifting would not support 64 bit integers!), there are only 16 squares that need to be calculated, the rest overflow. These could be easily stored as a 16 byte array in ROM - much faster and at a comparable size to a callable function.

As you have indicated performance is an issue, and in the chance that you need to support 32 bit integers, using the same method an array of $2^{20}$ bytes - 1MB of ROM would support every 32 bit square without overflow. This yields optimal performance while taking all the load off your minimalist CPU.

With this CPU that supports addition and subtraction, but not bit-shifting, I would assume that there are only a handful of registers available on the chip, which could yield even simple algorithms to be too complicated. I'm not sure C# would be the optimal language for programming this chip. It would also help to know the rest of the constraints that your embedded system has.

Assuming only 8 bit integers (a chip with no bit shifting would not support 64 bit integers!), there are only 16 squares that need to be calculated, the rest overflow. These could be easily stored as a 16 byte array in ROM - much faster and at a comparable size to a callable function.

As you have indicated performance is an issue, and in the chance that you need to support 32 bit integers, using the same method an array of \$2^{20}\$ bytes - 1MB of ROM would support every 32 bit square without overflow. This yields optimal performance while taking all the load off your minimalist CPU.