Modern Fast Inverse Square Root

This repository contains a C++20 implementation of the classic Quake III fast inverse‑square‑root algorithm, along with highly‑optimised SIMD batch variants. The code is portable across Windows (MSVC or clang‑cl), Linux and macOS (Only Windows tested), supports SSE, AVX2 and AVX‑512 when available, and includes a small test harness and benchmark.

Features

• Scalar fast inverse square root (FastInverseSqrt) – one Newton–Raphson iteration on a 32‑bit float.
• Hardware reciprocal square root (InverseSqrtSIMD) – single‑step _mm_rsqrt_ss for a scalar value, and _mm_rsqrt_ps for a batch of four floats.
• Batch SIMD implementation (FastInverseSqrtBatch) – processes an array of floats in 4/8/16‑wide chunks using SSE/AVX2/AVX‑512 respectively. The vector width is chosen automatically at compile time, but dedicated overloads are available for AVX2 and AVX‑512.
• Portable API – all functions live in the fisq namespace; overloads accept either raw pointers with size or std::span for ergonomics.
• C++20 only – uses <bit>, <concepts> and other modern features.

Build Instructions

The project is built with CMake and ships several presets that configure a release build for the most common toolchains. All builds target an x86‑64 CPU; SSE support is required by default, while AVX2/AVX‑512 are optional and can be enabled via dedicated presets.

Windows (MSVC or clang‑cl)

# Configure a Release build with the default preset
cmake --preset x64-release

# Build the library, tests and benchmark
cmake --build out\build\x64-release --config Release

If you want to target AVX‑512 you can use the dedicated preset:

cmake --preset avx512-release
cmake --build out\build\avx512-release --config Release

Linux / macOS (Clang/GCC)

# Configure a Release build with the default preset
cmake --preset x64-release

# Build everything
cmake --build out/build/x64-release --config Release

Use cmake --preset avx512-release for AVX‑512 builds on Linux/macOS as well.

The presets automatically set the compiler (clang-cl.exe, cl.exe, gcc or clang++) and enable C++20. You can also use standard CMake arguments if you prefer a custom build directory.

Usage Example

#include "fast_inverse_sqrt.hpp"
#include <iostream>
#include <vector>

int main() {
    // Scalar usage
    float value = 4.0f;
    std::cout << "FastInverseSqrt(" << value << ") = "
              << fisq::FastInverseSqrt(value) << '\n';

    // Batch processing with automatic SIMD selection
    std::vector<float> data{1.f, 2.f, 3.f, 4.f};
    std::vector<float> out(data.size());
    fisq::FastInverseSqrtBatch(std::as_const(data), out);

    for (float v : out)
        std::cout << v << ' ';
}

Compile with a C++20 compiler and link against the static library fisq.lib/libfisq.a. The header can also be used as a header‑only solution by including it in your project; no separate build is required.

API Documentation

template<std::same_as<float> T> inline constexpr T FastInverseSqrt(T number) noexcept

• Parameters: number – a 32‑bit floating point value.
• Returns: Approximate value of 1 / sqrt(number) after one Newton–Raphson iteration.
• Behavior:
  • Positive, finite inputs: relative error ≤ 0.2 % (verified by the unit tests).
  • 0 → large finite number (~ 1.98 × 10¹⁹), effectively representing infinity.
  • Negative numbers → NaN.
  • ±∞ or NaN propagate unchanged.

[[nodiscard]] float InverseSqrtSIMD(float number) noexcept

• Parameters: number – a 32‑bit floating point value.
• Returns: Approximate value of 1 / sqrt(number) using the single‑step _mm_rsqrt_ss.
• Behavior:
  • Positive, finite inputs: relative error ≤ 0.6 % (no Newton refinement).
  • 0 → IEEE infinity.
  • Negative numbers → NaN.

void FastInverseSqrtBatch(std::span<const float> src, std::span<float> dst) noexcept

• Parameters:
  • src – input values.
  • dst – output buffer (must be pre‑allocated and the same size as src).
• Description: Processes the array in chunks of 4/8/16 floats depending on the available SIMD width. The function is safe to call with any length; elements that do not fill a full vector are ignored, so callers should pass sizes that are multiples of the chosen width.

void FastInverseSqrtSIMDBatch(std::span<const float> src, std::span<float> dst) noexcept

• Description: Same as above but uses SSE intrinsics (_mm_rsqrt_ps) and requires the size to be a multiple of 4.

void FastInverseSqrtAVX2Batch(std::span<const float> src, std::span<float> dst) noexcept (conditionally compiled)

• Description: AVX2 implementation; requires the length to be a multiple of 8. Only available when compiling with AVX2 support (__AVX__ && __AVX2__).

void FastInverseSqrtAVX512Batch(std::span<const float> src, std::span<float> dst) noexcept (conditionally compiled)

• Description: AVX‑512 implementation; requires the length to be a multiple of 16. Only available when compiling with AVX‑512 support (__AVX512F__).

Overloads for raw pointers

All batch functions also have overloads that accept const float* src, float* dst and a size parameter, which are useful in low‑level code or when interfacing with legacy APIs.

Benchmarks

The repository ships benchmark.cpp, which measures execution time (in milliseconds) and prints detailed error metrics for each variant. Example output on an Intel CPU:

Warm-up iterations: 5
Iterations per function: 1000000
Total elapsed time (ms): 2.1601

Time
Q3(C++20):      4.3970e-01 ms   (avg=4.3970e-01 ns)
Q3(SIMD):       2.9590e-01 ms   (avg=2.9590e-01 ns)
RSqrt(SIMD):    1.0796e+00 ms   (avg=1.0796e+00 ns)
Std:            1.4245e+00 ms

Error metrics
                mean_abs,               max_abs,                mean_rel
Q3(C++20):      0x1.f2fc97efe0ce1p-15,  0x1.47ec000000000p-8,   0x1.f82dc4cee149ap-11
Q3(SIMD):       0x1.3e75bc44bf4cbp-29,  0x1.0000000000000p-21,  0x1.39df740d6494dp-25
RSqrt(SIMD):    0x1.91c80a2877ee5p-18,  0x1.7a60000000000p-11,  0x1.8ded4c7a47243p-14

Checksums -> Q3 (C++20): 0x1.e85653c9d2000p+15, Q3(SIMD): 0x1.e8cd4b2584400p+15, RSqrt(SIMD): 0x1.e8cd509700000p+15, Std: 0x1.e8cd4b8475800p+15

When building with AVX‑512 support the benchmark also reports Q3(AVX512) and Q3(AVX2). The SIMD variant is roughly 30 % faster than the classic implementation and competitive with the standard library.

Tests

Unit tests are located in tests/test_fast_inverse_sqrt.cpp. They validate:

• Correctness of all scalar functions against the exact value 1 / sqrt(x) with a relative‑error tolerance of 0.2 %.
• Correctness of batch functions on small, medium and large input sizes.
• Edge cases: zero (expects infinity for InverseSqrtSIMD and a large finite number for FastInverseSqrt), negative numbers (expect NaN), random values in the range [1e‑30, 1e+38].

Run the tests with:

# From the build directory
./fisq_tests.exe   # on Windows
./fisq_tests       # on Linux/macOS

or use CTest:

ctest -V

All tests should pass.

License

This project is released into the public domain under the CC0 1.0 Universal license.