Crate fwht

Crate fwht 

Source
Expand description

Fast Walsh-Hadamard Transform (FWHT) library

This library provides efficient implementations of the Fast Walsh-Hadamard Transform for various container types including Vec<T>, static arrays [T; N], and optionally ndarray::Array1<T>.

§Features

  • Fast: O(n log n) implementation using butterfly operations
  • Generic: Works with any numeric type implementing Add + Sub + Copy
  • Flexible: Uniform API across different container types via traits
  • Optional dependencies: ndarray support is feature-gated

§Quick Start

use fwht::FWHT;

let mut data = vec![1.0, 1.0, 1.0, 0.0];
data.fwht_mut().unwrap();
assert_eq!(data, vec![3.0, 1.0, 1.0, -1.0]);

let data2 = vec![1.0, 1.0, 1.0, 0.0];
let result = data2.fwht().unwrap();
assert_eq!(result, vec![3.0, 1.0, 1.0, -1.0]);
assert_eq!(data2, vec![1.0, 1.0, 1.0, 0.0]); // Original unchanged

// With ndarray (requires "ndarray" feature)
use ndarray::Array1;
let data = Array1::from(vec![1.0, 1.0, 1.0, 0.0]);
let result = data.fwht();

§API Overview

The main interface is the FWHT trait which provides:

§Function-based API

The original functions are also available:

  • fwht_mut: In-place transformation for any AsMut<[T]>
  • fwht: Copy-based transformation for any Clone + AsMut<[T]>

§Requirements

  • Container length must be a power of 2
  • Elements must implement Add<Output = T> + Sub<Output = T> + Copy

§Examples

§Basic Usage

use fwht::FWHT;

let data = vec![1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0];
let result = data.fwht().unwrap();
assert_eq!(result, vec![4.0, 0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 0.0]);

§Involution Property

FWHT is its own inverse (up to scaling):

use fwht::FWHT;

let original = vec![1.0, 2.0, 3.0, 4.0];
let mut data = original.clone();

// Apply FWHT twice
data.fwht_mut().unwrap();
data.fwht_mut().unwrap();

// Scale by 1/n to recover original
let n = data.len() as f64;
for x in &mut data { *x /= n; }

// Should equal original (within floating point precision)
for (a, b) in data.iter().zip(original.iter()) {
    assert!((a - b).abs() < 1e-10);
}

Re-exports§

pub use functions::fwht;
pub use functions::fwht_mut;
pub use traits::FWHT;
pub use core::fwht_slice;
pub use core::is_valid_fwht_length;
pub use core::next_power_of_two;

Modules§

core
Core FWHT algorithm implementation
functions
Function-based FWHT API
impls
Implementation modules for different container types
traits
Trait definitions for FWHT operations