Min/Max operations
This document explains how to compute minimum and maximum between values in Concrete, covering different strategies to make computations faster, depending on the strategy.
Finding the minimum or maximum of two numbers is not a native operation in Concrete, so it needs to be implemented using existing native operations (i.e., additions, clear multiplications, negations, table lookups). Concrete offers two different implementations for this.
Chunked
This is the most general implementation that can be used in any situation. The idea is:
Notes
Initial comparison is chunked as well, which is already very expensive.
Multiplication with operands aren't allowed to increase the bit-width of the inputs, so they are very expensive as well.
Optimal chunk size is selected automatically to reduce the number of table lookups.
Chunked comparisons result in at least 9 and at most 21 table lookups.
It is used if no other implementation can be used.
Pros
Can be used with any integers.
Cons
Extremely expensive.
Example
produces
Min/Max Trick
This implementation uses the fact that [min,max](x, y)
is equal to [min, max](x - y, 0) + y
, which is just a subtraction, a table lookup and an addition!
There are two major problems with this implementation though:
subtraction before the TLU requires up to 2 additional bits to avoid overflows (it is 1 in most cases).
subtraction and addition require the same bit-width across operands.
What this means is that if we are comparing uint3
and uint6
, we need to convert both of them to uint7
in some way to do the subtraction and proceed with the TLU in 7-bits. There are 2 ways to achieve this behavior.
Requirements
1. fhe.MinMaxStrategy.ONE_TLU_PROMOTED
This strategy makes sure that during bit-width assignment, both operands are assigned the same bit-width, and that bit-width contains at least the amount of bits required to store x - y
. The idea is:
Pros
It will always result in a single table lookup.
Cons
It will increase the bit-width of both operands and the result, and lock them together across the whole circuit, which can result in significant slowdowns if the result or the operands are used in other costly operations.
Example
produces
2. fhe.MinMaxStrategy.THREE_TLU_CASTED
This strategy will not put any constraint on bit-widths during bit-width assignment. Instead, operands are cast to a bit-width that can store x - y
during runtime using table lookups. The idea is:
Notes
It can result in a single table lookup as well, if x and y are assigned (because of other operations) the same bit-width, and that bit-width can store
x - y
.Or in two table lookups if only one of the operands is assigned a bit-width bigger than or equal to the bit width that can store
x - y
.
Pros
It will not put any constraints on bit-widths of the operands, which is amazing if they are used in other costly operations.
It will result in at most 3 table lookups, which is still good.
Cons
If you are not doing anything else with the operands, or doing less costly operations compared to comparison, it will introduce up to two unnecessary table lookups and slow down execution compared to
fhe.MinMaxStrategy.ONE_TLU_PROMOTED
.
Example
produces
Summary
Concrete will choose the best strategy available after bit-width assignment, regardless of the specified preference.
Different strategies are good for different circuits. If you want the best runtime for your use case, you can compile your circuit with all different comparison strategy preferences, and pick the one with the lowest complexity.
Last updated