--_003_alpineLNX200190517231220032550tinallotropenet_
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

Hi All,

In view of the recent request for fast PIC multiply routines I was=20
wondering if subtraction could be exploited to give better optimisation=20
under certain circumstances. It turns out it can e.g.

x * 127 =3D x * 128 - x

I don't remember ever having done (or read about) this before and thought=20
it might be worth sharing. Anyway it turns out it's quite efficent where=20
the number to be multiplied by has a high ratio of ones to zeros.

x * 0xfc =3D x * 256 - x * 2 - x - x (or further optimised to x * 256 - x *=
=20
4)

Anyway the trick is to subtract by 2^n where n is a zero bit in the=20
pattern.

I've attached some C code that better demonstrates how to do this.

Regards
Sergio Masci=

--_003_alpineLNX200190517231220032550tinallotropenet_
Content-Type: text/x-c; name="pic_mult_test.c"
Content-Description: pic_mult_test.c
Content-Disposition: attachment; filename="pic_mult_test.c"; size=1202;
	creation-date="Fri, 17 May 2019 21:43:52 GMT";
	modification-date="Fri, 17 May 2019 21:43:52 GMT"
Content-ID: <alpine.LNX.2.00.1905172332500.32550@tin.allotrope.net>
Content-Transfer-Encoding: base64

I2luY2x1ZGUgPHN0ZGlvLmg+DQojaW5jbHVkZSA8c3RkbGliLmg+DQoNCmludCBtYWluKGludCBh
cmdjLCBjaGFyICphcmd2W10pDQp7DQoJbG9uZwl4LCB5LCBqLCBrLCB2YWw7DQoNCglpbnQJbXNi
Ow0KCWludAlrYXJyWzMyXTsNCglpbnQJa2NudDsNCg0KCWNoYXIJKnN0ciwgKnN0cjI7DQoNCg0K
CWFyZ2MtLTsNCglhcmd2Kys7DQoNCglkbw0KCXsNCgkJaWYgKGFyZ2MgPT0gMCkNCgkJew0KCQkJ
dmFsID0gMTI3Ow0KCQl9DQoJCWVsc2UNCgkJew0KCQkJc3RyID0gKmFyZ3Y7DQoJCQlhcmdjLS07
DQoJCQlhcmd2Kys7DQoNCgkJCXZhbCA9IHN0cnRvbChzdHIsICZzdHIyLCAwKTsNCg0KCQkJaWYg
KHN0ciA9PSBzdHIyKQ0KCQkJew0KCQkJCWZwcmludGYoc3RkZXJyLCAiaW52YWxpZCBhcmcgJyVz
JyBudW1iZXIgZXhwZWN0ZWRcbiIsDQoJCQkJCXN0cik7DQoJCQkJZXhpdCgxKTsNCgkJCX0NCgkJ
fQ0KDQoJCWZvciAobXNiPTMxOyBtc2I+MDsgbXNiLS0pDQoJCXsNCgkJCWlmICgodmFsICYgKDE8
PG1zYikpICE9IDApDQoJCQl7DQoJCQkJYnJlYWs7DQoJCQl9DQoJCX0NCg0KCQlrY250ID0gMDsN
CgkJZm9yIChrPW1zYi0xOyBrPj0wOyBrLS0pDQoJCXsNCgkJCWlmICgodmFsICYgKDE8PGspKSA9
PSAwKQ0KCQkJew0KCQkJCWthcnJba2NudF0gPSBrOw0KCQkJCWtjbnQrKzsNCgkJCX0NCgkJfQ0K
DQoJCXByaW50ZigiMHgleCA9ICVkIiwgdmFsLCBtc2IpOw0KDQoJCWZvciAoaj0wOyBqPGtjbnQ7
IGorKykNCgkJew0KCQkJcHJpbnRmKCIgMHgleCIsIDEgPDwga2FycltqXSk7DQoJCX0NCg0KCQlw
dXRjaGFyKCdcbicpOw0KDQoJCWZvciAoaj0wOyBqPDI1NjsgaisrKQ0KCQl7DQoJCQkvLyB4ID0g
aiAqIDEyNzsNCgkJCXggPSBqICogdmFsOw0KDQoJCQkvLyB5ID0gKGogPDwgNykgLSBqOw0KDQoJ
CQl5ID0gaiA8PCAobXNiICsgMSk7DQoNCgkJCWZvciAoaz0wOyBrPGtjbnQ7IGsrKykNCgkJCXsN
CgkJCQl5ID0geSAtIChqIDw8IGthcnJba10pOw0KCQkJfQ0KDQoJCQl5ID0geSAtIGo7DQoNCgkJ
CWlmICh4ICE9IHkpDQoJCQl7DQoJCQkJcHJpbnRmKCIleDogJXggIT0gJXhcbiIsIGosIHgsIHkp
Ow0KCQkJfQ0KCQl9DQoJfQ0KCXdoaWxlIChhcmdjID4gMCk7DQoNCglyZXR1cm4gMDsNCn0NCg==

--_003_alpineLNX200190517231220032550tinallotropenet_
Content-Type: text/plain; name="ATT00001.txt"
Content-Description: ATT00001.txt
Content-Disposition: attachment; filename="ATT00001.txt"; size=224;
	creation-date="Fri, 17 May 2019 21:43:52 GMT";
	modification-date="Fri, 17 May 2019 21:43:52 GMT"
Content-Transfer-Encoding: base64

LS0gDQpodHRwOi8vd3d3LnBpY2xpc3QuY29tL3RlY2hyZWYvcGljbGlzdCBQSUMvU1ggRkFRICYg
bGlzdCBhcmNoaXZlDQpWaWV3L2NoYW5nZSB5b3VyIG1lbWJlcnNoaXAgb3B0aW9ucyBhdA0KaHR0
cDovL21haWxtYW4ubWl0LmVkdS9tYWlsbWFuL2xpc3RpbmZvL3BpY2xpc3QNCg==

--_003_alpineLNX200190517231220032550tinallotropenet_--
.