Index Mathematics Conjectures nbv lettuce Widgets

bit_reverse_indices

stdlib/polynomial/bit_reverse_indices.nbv

bit_reverse_indices(let mut input)

take a vector and move each element from it's original index to the index equal to the bit reversal of the original index

Calls
bits/from_bits_static, reverse_static, slice_from_start
Precompiles
if_eq!, if_ne!, len!, log2_exact!, loop!, to_bits_static!
Used by
polynomial/ntt

Source

# take a vector and move each element from it's original index
# to the index equal to the bit reversal of the original index
(let mut input)

static input_len = len! input

static mut moved_indices[input_len]

loop! input_len, i {
  static bits = slice_from_start((to_bits_static! i), log2_exact! input_len)
  # TODO: warn when assigning a static directly to a let?
  # force the user to use wtns! or const!
  static new_i = from_bits_static(reverse_static(bits))
  if_ne! i, new_i {
    if_eq! moved_indices[i], 0 {
      moved_indices[i] = 1
      moved_indices[new_i] = 1
      let v = input[new_i]
      input[new_i] = input[i]
      input[i] = v
    }
  }
}

input