Fast Walsh-Hadamard Transform
(lib/convolution/fast_walsh_hadamard_transform.hpp)

• View this file on GitHub
• Last update: 2024-11-13 13:43:26+09:00
• Include: #include "lib/convolution/fast_walsh_hadamard_transform.hpp"

Required by

• Bitwise XOR Convolution (lib/convolution/bitwise_xor_convolution.hpp)

Verified with

• test/library_checker/convolution/bitwise_xor_convolution.test.cpp

Code

#pragma once

/**
 * @brief Fast Walsh-Hadamard Transform
 */

#include <vector>
#include <cassert>

template <typename T>
void fast_walsh_hadamard_transform(std::vector<T> &f, bool inv = false){
    const int n = (int) f.size();
    assert((n & (n - 1)) == 0);
    for(int i = 1; i < n; i <<= 1){
        for(int j = 0; j < n; j += i << 1){
            for(int k = 0; k < i; ++k){
                T s = f[j + k], t = f[j + k + i];
                f[j + k] = s + t;
                f[j + k + i] = s - t;
            }
        }
    }
    if(inv){
        T inv_n = T(1) / n;
        for(auto &x : f) x *= inv_n;
    }
}

#line 2 "lib/convolution/fast_walsh_hadamard_transform.hpp"

/**
 * @brief Fast Walsh-Hadamard Transform
 */

#include <vector>
#include <cassert>

template <typename T>
void fast_walsh_hadamard_transform(std::vector<T> &f, bool inv = false){
    const int n = (int) f.size();
    assert((n & (n - 1)) == 0);
    for(int i = 1; i < n; i <<= 1){
        for(int j = 0; j < n; j += i << 1){
            for(int k = 0; k < i; ++k){
                T s = f[j + k], t = f[j + k + i];
                f[j + k] = s + t;
                f[j + k + i] = s - t;
            }
        }
    }
    if(inv){
        T inv_n = T(1) / n;
        for(auto &x : f) x *= inv_n;
    }
}

Back to top page