batch_inverse.hpp¶

SECTIONMath INCLUDEnoya/batch_inverse.hpp

只做一次除法和线性次乘法，批量求一组非零域元素的逆元。

\[ \displaystyle y_i = x_i^{-1} \]

Complexity: Time: O(n) field operations. Space: O(n).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n) field operations.
/// Space: O(n).

#include <cassert>
#include <vector>

namespace noya {

/// @brief Invert a list of nonzero field elements with one division and O(n)
/// multiplications.
template <class T> std::vector<T> batch_inverse(const std::vector<T> &vs) {
  std::vector<T> pre(vs.size() + 1, T(1));
  for (int idx = 0; idx < int(vs.size()); idx++) {
    assert(vs[idx] != T{});
    pre[idx + 1] = pre[idx] * vs[idx];
  }
  T isf = T(1) / pre.back();
  std::vector<T> res(vs.size());
  for (int idx = int(vs.size()) - 1; idx >= 0; idx--) {
    res[idx] = pre[idx] * isf;
    isf *= vs[idx];
  }
  return res;
}

} // namespace noya

#ifndef NOYA_BATCH_INVERSE_HPP
#define NOYA_BATCH_INVERSE_HPP 1

/// @complexity Time: O(n) field operations.
/// Space: O(n).

#include <cassert>
#include <vector>

namespace noya {

/// @brief Invert a list of nonzero field elements with one division and O(n)
/// multiplications.
template <class T> std::vector<T> batch_inverse(const std::vector<T> &vs) {
  std::vector<T> pre(vs.size() + 1, T(1));
  for (int idx = 0; idx < int(vs.size()); idx++) {
    assert(vs[idx] != T{});
    pre[idx + 1] = pre[idx] * vs[idx];
  }
  T isf = T(1) / pre.back();
  std::vector<T> res(vs.size());
  for (int idx = int(vs.size()) - 1; idx >= 0; idx--) {
    res[idx] = pre[idx] * isf;
    isf *= vs[idx];
  }
  return res;
}

} // namespace noya

#endif // NOYA_BATCH_INVERSE_HPP

#include <cassert>
#include <vector>

/// @complexity Time: O(n) field operations.
/// Space: O(n).

namespace noya {

/// @brief Invert a list of nonzero field elements with one division and O(n)
/// multiplications.
template <class T> std::vector<T> batch_inverse(const std::vector<T> &vs) {
  std::vector<T> pre(vs.size() + 1, T(1));
  for (int idx = 0; idx < int(vs.size()); idx++) {
    assert(vs[idx] != T{});
    pre[idx + 1] = pre[idx] * vs[idx];
  }
  T isf = T(1) / pre.back();
  std::vector<T> res(vs.size());
  for (int idx = int(vs.size()) - 1; idx >= 0; idx--) {
    res[idx] = pre[idx] * isf;
    isf *= vs[idx];
  }
  return res;
}

} // namespace noya