Index Mathematics Conjectures nbv lettuce Widgets

ntt

stdlib/polynomial/ntt.nbv

ntt(let input, root_powers)

apply a number theoretic transform to a vector of elements

Calls
polynomial/bit_reverse_indices
Precompiles
assert_eq!, div_exact!, len!, log2_exact!, loop!
Used by
polynomial/intt_negacyclic, polynomial/ntt_negacyclic

Source

# apply a number theoretic transform to a vector of elements
(let input, root_powers)

static N = len! input
assert_eq! N, len! root_powers

let mut output = bit_reverse_indices(input)

static mut len = 1
loop! (log2_exact! N), i {
  len = len * 2
  static w_len = root_powers[div_exact! N, len]
  loop! (div_exact! N, len), j {
    static j = j * len
    static mut w = 1
    static len_half = div_exact! len, 2
    loop! len_half, k {
      let u = output[j + k]
      let v = output[j + k + len_half] * w
      output[j + k] = u + v
      output[j + k + len_half] = u - v
      w = w * w_len
    }
  }
}

output