This guide teaches how to improve the execution time of Concrete circuits by reducing the amount of table lookups.

Reducing the amount of table lookups is probably the most complicated guide in this section as it's not automated. The idea is to use mathematical properties of operations to reduce the amount of table lookups needed to achieve the result.

One great example is in adding big integers in bitmap representation. Here is the basic implementation:

defadd_bitmaps(x,y): result = fhe.zeros((N,)) carry =0 addition = x + yfor i inrange(N): addition_and_carry = addition[i]+ carry carry = addition_and_carry >>1 result[i]= addition_and_carry %2return result

There are two table lookups within the loop body, one for >> and one for %.

This implementation is not optimal though, since the same output can be achieved with just a single table lookup:

defadd_bitmaps(x,y): result = fhe.zeros((N,)) carry =0 addition = x + yfor i inrange(N): addition_and_carry = addition[i]+ carry carry = addition_and_carry >>1 result[i]= addition_and_carry - (carry *2)return result

It was possible to do this because the original operations had a mathematical equivalence with the optimized operations and optimized operations achieved the same output with less table lookups!

Here is the full code example and some numbers for this optimization: