batch_inverse.hpp¶
Invert a list of nonzero field elements with one division and O(n) multiplications.
\[
\displaystyle y_i = x_i^{-1}
\]
Implementation¶
#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> &values) {
std::vector<T> prefix(values.size() + 1, T(1));
for (int index = 0; index < int(values.size()); index++) {
assert(values[index] != T{});
prefix[index + 1] = prefix[index] * values[index];
}
T suffix_inverse = T(1) / prefix.back();
std::vector<T> result(values.size());
for (int index = int(values.size()) - 1; index >= 0; index--) {
result[index] = prefix[index] * suffix_inverse;
suffix_inverse *= values[index];
}
return result;
}
} // 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> &values) {
std::vector<T> prefix(values.size() + 1, T(1));
for (int index = 0; index < int(values.size()); index++) {
assert(values[index] != T{});
prefix[index + 1] = prefix[index] * values[index];
}
T suffix_inverse = T(1) / prefix.back();
std::vector<T> result(values.size());
for (int index = int(values.size()) - 1; index >= 0; index--) {
result[index] = prefix[index] * suffix_inverse;
suffix_inverse *= values[index];
}
return result;
}
} // namespace noya