Targetting 8-bit CPUs with no division instruction (in hardware), this snippet finds the number X that, given N (both 8-bit unsigned) so that N*X=1 (mod 256).

## Background

Finding the multiplicative inverse in modular arithmetics can be accomplished with Extended Euclid's Algorithm, but that requires division operations and looping/recursion for an average of 6 iterations/depth (over all input values from 1..255).

This is a piece of ugly code that CLANG (or also GCC a bit less optimized) boils down to something finishing in less than 100~200 cycles on the tinyest 8-bit CPUs, in constant time, with no lookup tables, no multiplication/division/modulo instructions.

## The Code

typedef unsigned char byte;
struct bit8
{ int a:1,b:1,c:1,d:1,e:1,f:1,g:1,h:1;
};
__attribute__((noinline))
byte inv8(byte _i)
{
byte is {_i}, ix; bit8 i_1,i_2,i_3,i_4,i_5;
is>>=1; ix=_i^is; i_1=*(bit8*)&ix;
is>>=1; ix=_i^is; i_2=*(bit8*)&ix;
is>>=1; ix=_i^is; i_3=*(bit8*)&ix;
is>>=1; ix=_i^is; i_4=*(bit8*)&ix;
is>>=1; ix=_i^is; i_5=*(bit8*)&ix;
bit8 k {0,0,0, i_1.b, i_1.c&i_2.b,
i_3.b^(i_1.d&!i_2.c&!i_3.b),
(!i_4.b&!i_1.e&(i_3.c|!i_2.d)) ^ (!i_1.c&!i_2.b),
(i_5.b^(i_1.e&i_2.c&!i_3.b))
| (((i_2.e|i_1.f)^i_4.c) & (i_4.c|!i_3.d&!i_5.b))
};
return _i^*(byte*)&k;
};

## Points of Interest

Note that the input parameter should be an ODD number, so the result can make sense, if you think about it.

The scheme does not seem to me to be extendable to wider integers... ideas, comments and questions welcome!

## History

- 8
^{th} July, 2022: Initial version

has been working a total of 14 years as programmer and system developer, plus some years of working as network technician and application supporter. Also experienced modeling, optimizing and administering FireBird and SqlServer databases. Loathes MySql.

Works with C++, C++/CLI, C#, JavaScript, PHP, PSQL and TextPad.