src/math/convolution/bitwise-and-convolution.hpp

• View this file on GitHub
• Last update: 2023-06-24 21:59:36+09:00
• Include: #include "src/math/convolution/bitwise-and-convolution.hpp"

Depends on

• src/cpp-template/header/size-alias.hpp
• src/math/convolution/fast-walsh-hadamard-transform.hpp

Verified with

• test/library-checker/bitwise_and_convolution.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#include <cassert>
#include <vector>

namespace luz {

  // length of f and g must be 2^k
  template < typename T >
  std::vector< T > bitwise_and_convolution(std::vector< T > f,
                                           std::vector< T > g) {
    assert(f.size() == g.size());

    auto zeta   = [](T &lo, T hi) { return lo += hi; };
    auto mobius = [](T &lo, T hi) { return lo -= hi; };

    fast_walsh_hadamard_transform(f, zeta);
    fast_walsh_hadamard_transform(g, zeta);

    for (usize i = 0; i < f.size(); i++) {
      f[i] *= g[i];
    }

    fast_walsh_hadamard_transform(f, mobius);
    return f;
  }

} // namespace luz

#line 2 "src/math/convolution/bitwise-and-convolution.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 2 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#line 4 "src/math/convolution/fast-walsh-hadamard-transform.hpp"

#include <cassert>
#include <vector>

namespace luz {

  // length of f must be 2^k
  template < typename T, typename F >
  void fast_walsh_hadamard_transform(std::vector< T > &f, F op) {
    const usize n = f.size();
    assert((n & (n - 1)) == 0);

    usize i = 1;
    while (i < n) {
      usize j = 0;

      while (j < n) {
        for (usize k = 0; k < i; k++) {
          op(f[j + k], f[j + k + i]);
        }

        j += i << 1;
      }

      i <<= 1;
    }
  }

} // namespace luz
#line 5 "src/math/convolution/bitwise-and-convolution.hpp"

#line 8 "src/math/convolution/bitwise-and-convolution.hpp"

namespace luz {

  // length of f and g must be 2^k
  template < typename T >
  std::vector< T > bitwise_and_convolution(std::vector< T > f,
                                           std::vector< T > g) {
    assert(f.size() == g.size());

    auto zeta   = [](T &lo, T hi) { return lo += hi; };
    auto mobius = [](T &lo, T hi) { return lo -= hi; };

    fast_walsh_hadamard_transform(f, zeta);
    fast_walsh_hadamard_transform(g, zeta);

    for (usize i = 0; i < f.size(); i++) {
      f[i] *= g[i];
    }

    fast_walsh_hadamard_transform(f, mobius);
    return f;
  }

} // namespace luz

Back to top page