1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
use crate::ArcisMath;
impl ArcisMath {
/// Fast Euclidean division between an unsigned integer and an unsigned integer whose value is
/// known by the interpreter.
/// Returns the division, remainder and whether it was successful.
/// Fails for `b <= 0` and with `< 2^-64` probability for `1 <= b < 256` and `0 <= x < 2^128`.
/// `b > 255` is currently unsupported.
/// If `b` is a power of `2`, using standard `%` or `/` will be faster.
/// In case of failure, it returns `(0, 0, false)`.
///
/// Example:
/// ```
/// use arcis::*;
/// #[encrypted]
/// mod circuits {
/// use arcis::*;
/// #[instruction]
/// fn slow_modulo_u128_3() -> u8 {
/// let input = ArcisRNG::gen_uniform::<u128>();
/// let res = (input % 3) as u8;
/// res.reveal()
/// }
/// #[instruction]
/// fn fast_modulo_u128_3() -> u8 {
/// let input = ArcisRNG::gen_uniform::<u128>();
/// let res = ArcisMath::fast_euclidean_division_by_known(input, 3).1;
/// res.reveal()
/// }
/// }
/// ```
/// * slow_modulo_u128_3 uses 24819918 ACUs
/// * fast_modulo_u128_3 uses 13936434 ACUs (44% reduction)
pub fn fast_euclidean_division_by_known<
T: Into<u128> + TryFrom<u128>,
U: Into<i128> + TryFrom<i128>, // i128 so that it works for literals coerced to i32
>(
a: T,
b: U,
) -> (T, U, bool) {
let a = a.into();
let b = b.into();
if b == 0 {
return (
T::try_from(0).map_err(|_| "0 not a T ???").unwrap(),
U::try_from(0).map_err(|_| "0 not a U ???").unwrap(),
false,
);
}
let b_128 = b as u128;
let (q, r, success) = (a / b_128, a % b_128, true);
(
T::try_from(q)
.map_err(|_| "division result not a T ???")
.unwrap(),
U::try_from(r as i128)
.map_err(|_| "division result not a U ???")
.unwrap(),
success,
)
}
}