Index Mathematics Conjectures nbv lettuce Widgets

poly_norm_inf_lt

stdlib/polynomial/poly_norm_inf_lt.nbv

poly_norm_inf_lt(N, poly, static bound)

returns the coefficient with the largest norm

Calls
bits/from_bits_static, bits/lt_bits, bits/to_bits_exact, bits/to_bits_exact_static, valloc
Precompiles
assert_eq!, clone!, constrain_eq!, len!, log2_ceil!, loop!
Used by
bdlop/bdlop_linear_nizk_verify

Source

# returns the coefficient with the largest norm
(N, poly, static bound)

assert_eq! N, len! poly

static bitlen = log2_ceil! bound
static midpoint = from_bits_static(valloc(bitlen - 1, 1))
let midpoint_bits = to_bits_exact_static(midpoint, bitlen)

let bound_bits = to_bits_exact_static(bound, bitlen)

loop! N, i {
  let v = poly[i] + midpoint
  let v_bits = to_bits_exact(v, bitlen)

  let is_positive = 1 - lt_bits(v_bits, clone! midpoint_bits)
  let abs_norm = ((v - midpoint) * is_positive) + ((1 - is_positive) * (0 - (v - midpoint)))
  let abs_norm_bits = to_bits_exact(abs_norm, bitlen)
  constrain_eq! 1, lt_bits(abs_norm_bits, clone! bound_bits)
}