C++ header-only fixed-point math library

Overview

fpm

A C++ header-only fixed-point math library. "fpm" stands for "fixed-point math".

It is designed to serve as a drop-in replacement for floating-point types and aims to provide as much of the standard library's functionality as possible with exclusively integers. fpm requires C++11 or higher.

Build Status Build status

fpm is designed to guard against accidental conversion to and from floats and supports many of the standard C++ maths functions, including trigonometry, power and logarithmic functions, with performance and accuracy generally comparable to alternative libraries.

Why use fixed-point math?

There are several reasons why you can not or choose not to use floating-point math, but still want a similar type:

  • Your target platform lacks an FPU, does not support floating-point operations or its floating-point operations are considerably slower than fixed-point integer operations.
  • You require deterministic calculations.

If any of these reasons apply for you, and your problem domain has a clearly outlined range and required resolution, then fixed-point numbers might be a solution for you.

Quick Start

To use fpm, include its header <fpm/fixed.hpp> and use the fpm::fixed_16_16, fpm::fixed_24_8 or fpm::fixed_8_24 types as if they were native floating-pointer types:

#include <fpm/fixed.hpp>  // For fpm::fixed_16_16
#include <fpm/math.hpp>   // For fpm::cos
#include <fpm/ios.hpp>    // For fpm::operator<<
#include <iostream>       // For std::cin, std::cout

int main() {
    std::cout << "Please input a number: ";
    fpm::fixed_16_16 x;
    std::cin >> x;
    std::cout << "The cosine of " << x << " radians is: " << cos(x) << std::endl;
    return 0;
}

To use the fixed-point equivalents of the <math.h> functions such as sqrt, sin and log, include the header <fpm/math.hpp>. To stream fixed-point values to or from streams, include the header <fpm/ios.hpp>.

Documentation

Please refer to the documentation for detailed information how to use fpm, or skip straight to the performance or accuracy results.

Contributions

This library is a work-in-progress. We welcome any contributions that improve the functional coverage or the performance or accuracy of the mathematical functions.

License

See the LICENSE file

Comments
  • Improve accuracy for atan2(y,x) with near-zero x

    Improve accuracy for atan2(y,x) with near-zero x

    Hi,

    I have the following setup:

    #include <fpm/math.hpp>
    using number = fpm::fixed<int64_t, __int128_t, 32>;
    number x = number(50) * (number::pi() / number(100));
    // x is 1.5708, really close to half pi but raw value is off by one (base type) from ::half_pi()
    number cosX = cos(x);
    // inside the cos->sin function we reduce x to a value of two but it is also off by one (base type) and hence returns the wrong result here.
    

    Could this be caused by this: static constexpr fixed pi() { return from_fixed_point<61>(7244019458077122842ll); } I tried changing this to calculate fixed(355)/fixed(113) (approximation of pi) and use this instead and it seems to fix the issue but could the from_fixed_point function not be correctly converting between fixed point types?

    Thanks, Luis

    enhancement 
    opened by grimaldini 10
  • Avoid using floating point arithmetic to compute static_cast<double>(fpm::fixed_16_16)

    Avoid using floating point arithmetic to compute static_cast(fpm::fixed_16_16)

    Hi,

    Before all, thanks for sharing this amazing project. I just wanted to ask for some help regarding this very particular use case I have.

    // My use case
    inline bool parseNumberDoubleWrapper(const char*& ptr, const char* end, double& number)
    {
        // Convert double to fpm fixed representation
        fpm::fixed_16_16 n { number };
        // Execute parsing algorithm built on top of fpm types.
        bool b = parseNumber(ptr, end, n);
        // Create a double from the fpm::fixed_16_16 value
        // This static cast triggers fpm's function pasted below.
        number = static_cast<double>(n);  // <----- my problem is here
        // Return parsing status
        return b;
    }
    

    The static cast above is triggering this function in fpm:

        // Explicit conversion to a floating-point type
        template <typename T, typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>
        constexpr inline explicit operator T() const noexcept
        {
            return static_cast<T>(m_value) / FRACTION_MULT;
        }
    

    operator T() computes the final double using double division. Would it be possible to construct the double without relying on the double data type operations (in this case division)? I was wondering if this function could be re-written to compute the same result using n.raw_value() somehow (and not using any double operation at all).

    To contextualise, my requirement is not to emit any floating point instruction at all but still be able to cast to double. Even a hacky workaround for this is useful.

    Best regards, Manuel.

    opened by m-carrasco 6
  • Conversion of max() and lowest() to float

    Conversion of max() and lowest() to float

    fpm is very nice! Converting numeric_limits values to float is behaving unexpectedly when there are zero integral bits.

    #include <cstdint>
    #include <fpm/fixed.hpp>
    #include <fpm/ios.hpp>
    #include <iostream>
    #include <iomanip>
    
    using fixed_0_15 = fpm::fixed<std::int16_t, std::int32_t, 15>;
    
    int main() {
        auto max = std::numeric_limits<fixed_0_15>::max();
        auto lowest = std::numeric_limits<fixed_0_15>::lowest();
        std::cout << "fixed_0_15"
                << " max " << max
                <<" lowest "<< lowest
                << std::endl;
        std::cout << "static_cast<float>(fixed_0_15)"
                  << " max " << static_cast<float>(max)
                  <<" lowest "<< static_cast<float>(lowest)
                  << std::endl;
        std::cout << "float(fixed_0_15)"
                  << " max " << float(max)
                  <<" lowest "<< float(lowest)
                  << std::endl;
    }
    
    $ c++ -std=c++17 -Ifpm/include fpm_limits.cpp && ./a.out
    fixed_0_15 max 0.999969 lowest -1
    static_cast<float>(fixed_0_15) max -0.999969 lowest 1
    float(fixed_0_15) max -0.999969 lowest 1
    

    The fixed_0_15 is an attempt to model the q15 data type used in the ARM CMSIS DSP library. The trouble may be because FRACTION_MULT cannot be represented in the base type int16_t. I think FRACTION_MULT should use the IntermediateType. The tests pass with this change:

    -    static constexpr BaseType FRACTION_MULT = BaseType(1) << FractionBits;
    +    static constexpr IntermediateType FRACTION_MULT = BaseType(1) << FractionBits;
    
    bug 
    opened by ahooper 6
  • Support for Shift Operators

    Support for Shift Operators

    Hi.

    Thank you for this amazing class. I want to leave my feedback.

    First. There are no shift operators.

    template <typename I, typename std::enable_if<std::is_integral<I>::value>::type* = nullptr>
    inline fixed& operator>>=(I y) noexcept
    {
        m_value >>= y;
        return *this;
    }
    
    template <typename I, typename std::enable_if<std::is_integral<I>::value>::type* = nullptr>
    inline fixed& operator<<=(I y) noexcept
    {
        m_value <<= y;
        return *this;
    }
    
    template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
    constexpr inline fixed<B, I, F> operator>>(const fixed<B, I, F>& x, T y) noexcept
    {
        return fixed<B, I, F>(x) >>= y;
    }
    
    template <typename B, typename I, unsigned int F, typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
    constexpr inline fixed<B, I, F> operator<<(const fixed<B, I, F>& x, T y) noexcept
    {
        return fixed<B, I, F>(x) <<= y;
    }
    

    I spent a whole day to understand why fixed doesn't work in my case. :thinking: The problem was in this string.

    const int count = static_cast<int>(sweep >> (16 - k));
    

    When you use just std::int32_t for type, this will work. But in case of fixed this doesn't return internal value. Because I save inside fixed a floating-point value, this approach is incorrect. It confuses. I am not familiar with fixed-point types. But I do not undersatnd purpose of conversion to integrals.

    Correct code in my case.

    const int count = (sweep >> (16 - k)).raw_value();
    
    opened by dismine 5
  • Howto cast from

    Howto cast from "fpm::fixed_a_b" to "fpm::fixed_c_d" ?

    Is it possible to cast from e.g. fixed_8_24 to fixed_16_16 without an intermediate step via a float value?

    With simple assignments "fixed2 = fixed1" the compiler reports an >no known conversion for argument 1 from 'fpm::fixed_8_24' ... to 'const fpm::fixed<int, long long int, 16>&'

    There is a function from_fixed_point(T value), but i dont understand it. I would have expected that the value is corrected by the difference of the FractionBits between new and old datatype.

    enhancement 
    opened by Klummel69 4
  • Add support for PlatformIO

    Add support for PlatformIO

    This file is needed to get this library to work seamlessly with PlatformIO. Docs for the file can be found at https://docs.platformio.org/en/latest/librarymanager/config.html

    This has been tested with a platformio project by setting

    lib_deps =
        https://github.com/flaviut/fpm.git#aa0a3aa265ea0733f3c6410785f31b53b0a0db03
    

    and works fine.

    opened by flaviut 3
  • Make release for library

    Make release for library

    Hi! Thank you for your library. I want to see this library in Conan (dependency manager for C++). That's not so hard to prepare a recipe for your library, but the only one limitation for now is a lack of any release. Can you please release your library with any version? It will be very helpful. Thanks a lot!

    opened by zamazan4ik 3
  • Unable to compile when minwindef.h is (implicitly) included before fixed.hpp

    Unable to compile when minwindef.h is (implicitly) included before fixed.hpp

    Window's header minwindef.h define the macro min() and max().

    When this file is included before fixed.hpp, this fail to compile because min/max method of numeric_limit<fixed> are refering to the windows macro as showed in the screenshot below.

    screenshot

    I did not look that much into the subject but it seems to be a reccurent problem for libraries that are using min/max methods and are co-existing with the windows header in an application.

    The solution I use for now is the include fixed.hpp before the header that include minwindef.h.

    I think, this information might be worth to be included as a note in the documentation or somewhere else.

    opened by Cerclique 2
  • non-constexpr function 'round'

    non-constexpr function 'round'

    The following code generates an error message under different clang versions, because std::round() is not a constexpr function in C++11/14.

    static constexpr fpm::fixed_16_16 delta {1.234};
    //error: constexpr variable 'delta' must be initialized by a constant expression
    //static constexpr fpm::fixed_16_16 delta {1.234};
    //                                  ^~~~~~~~~~~~~
    //.\include\fpm/fixed.hpp: note: non-constexpr function 'round' cannot be used in a constant expression
    //        : m_value(static_cast<BaseType>(std::round(val * FRACTION_MULT)))
    

    I suggest the following workaround: replace std::round()

        // Converts an floating-point number to the fixed-point type.
        // Like static_cast, this truncates bits that don't fit.
        template <typename T, typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>
        constexpr inline explicit fixed(T val) noexcept
            //: m_value(static_cast<BaseType>(std::round(val * FRACTION_MULT)))
            : m_value(static_cast<BaseType>((val >= 0.0) ? (val * FRACTION_MULT + 0.5) : (val * FRACTION_MULT - 0.5)))
        {}
    

    On Godbolt you can see the behavior (without fpm header)

    https://godbolt.org/z/34cns5fnK

    Advantage: This allows constants to be defined at compile time without the detour via from_fixed_point<..>....

    bug 
    opened by Klummel69 2
  • Risks and limitations of BaseType == IntermediateType?

    Risks and limitations of BaseType == IntermediateType?

    Question for your expertise for what seems to be an uncommon-but-not-rare situation:

    What are the risks and limitations exactly of using the same int type for BaseType and IntermediateType? Eg, fpm::fixed<std::int64_t, std::int64_t, 16>

    I've looked into the fpm code, ran some unit tests, and otherwise messed around with the above for a while, and it seems like the above 64bit with 16 fractional bits type works pretty well. However, I'm not familiar with how the fractional portion works exactly and overall not sure what the limitations and risks of this would be (other than needing to restrict myself to some sub-range of numbers at the risk of very easy underflows and overflows).


    Problem Context: Earlier I attempted to a BaseType of int64_t and IntermediateType of boost's int128_t, but unfortunately that's far too slow for my needs (10x slower than fixed_16_16 and far higher than my performance budget as mentioned in #21). Thus, I'm looking for workarounds for my size constraints

    Notably, I don't really need a very large working number range- I'm creating a game where typically one unit == 1cm (Unreal units), and as long as I get at least 2km (so 20000) for range of world units then I can easily fit all my needs.

    However, that 20,000 max is before any underlying calculations. For example, one of my more problematic operations is getting a length of a vector, which involves squaring and adding 3x. Thus, at the very least my range needs to support 20000^2, and given that's above the range of fixed_16_16 and fixed_24_8, I need to go into the realm of 64bit BaseType numbers.

    And now we're unfortunately back to the beginning where a BaseType of int64_t needs a size above it, and boost's int128_t is unfortunately extremely slow.

    However... my numeric range isn't that large. Thus, if I drop the need for lossless operations and heavily restrict myself to a very limited range (which will definitely be error-prone but doable), then I can use the same IntermediateType as BaseType. In other words, it should be viable to use fpm::fixed<std::int64_t, std::int64_t, 16> (or something akin to it).

    I've tested this (after commenting out the sizeof static assert), and after some tweaking with number of fractional bits, it's surprisingly working well. On the other hand, I'm not sure exactly what the risks and limitations are.

    For example, I'd expect that I'd need a working range that fits the following: [sqrt of range<TOTALBITS - FRACTIONALBITS>]/3

    Thus, with fixed<int64_t, int64_t, 20>, I'd expect the safe numeric working range to be about... sqrt(2^(64-20)-1)/3 = ~1,398,101.3

    However, even 45000 * 45000 overflows with that fixed point type, while fixed<int64_t, int64_t, 16> does not overflow here.

    All in all, I'm largely guess and checking with the limitations of this approach at the moment, and thus would greatly appreciate any insight you can provide here.

    In addition, I hope this write up will also help someone in the future who faces similar issues as well. Cuz dang, this was a surprising amount of work to even get this far. Makes me hella glad this solid library exists again- yay for well-written and flexible yet easy to understand library!

    question 
    opened by DragonJawad 2
  • Constructor of fpm::fixed should be

    Constructor of fpm::fixed should be "= default"

    Currently, doing fixed_16_16 f {}; does not initialize f.m_value. The expected behaviour is to do zero-initialization, like int i{} initializes i to 0. The simple fix is to mark the constructor as default, which is good anyway.

    Moreover, it can't be used in constexpr expressions:

    constexpr void test()
    {
        // fpm::fixed_16_16 f {}; // Error because can contain anything
        fpm::fixed_16_16 f{0}; // Ok
    }
    

    Also some of the operators like += are not marked constexpr but that's another issue.

    opened by Eren121 1
  • Only build tools when a top-level project

    Only build tools when a top-level project

    CPM or FetchContent are frequently used to add dependencies to projects. In that case, it doesn't make sense to add all these extra targets unless they are asked for.

    This is needed, for example, in the case of use in an embedded project. When GoogleBench is included, it depends on threads, which are not available.

    opened by flaviut 0
  • Provide a way to serialize fpm::fixed

    Provide a way to serialize fpm::fixed

    Is the value returned by raw_value() the same across all platforms for a given fixed point value? That's for serialization and sending into network and ensure portability. I assume yes but just to be sure.

    enhancement 
    opened by Eren121 2
  • Signed lowest value may cause stack overflow

    Signed lowest value may cause stack overflow

    For example, in the atan function, if x is signed and x is the lowest value, -x will be equal to x. So the function will keep calling itself and cause a stack overflow.

    bug 
    opened by UFOylzj 0
  • Conversion between different fixed types

    Conversion between different fixed types

    Hi Mike,

    Thanks for the great library!

    I faced an issue when trying to convert a fixed_16_16 number to a fixed<std::int64_t, __int128, 32>. In essence, it seems that the from_fixed_point function in fixed.hpp could not handle an increase number of bits for both the BaseType and the FractionBits jointly. I handled this by modifying the code as follows:

    template <unsigned int NumFractionBits, typename T, typename std::enable_if<(NumFractionBits <= FractionBits)>::type* = nullptr>
        static constexpr inline fixed from_fixed_point(T value) noexcept
        {
        	T tmpT = T(1) << (FractionBits - NumFractionBits);
            BaseType tmpBT = static_cast<BaseType>(value)*static_cast<BaseType>(tmpT);
        	return fixed(tmpBT, raw_construct_tag{});
        }
    

    This seems to do the trick, but I thought I'll mention it in case it may be of interest to others.

    Cheers,

    Mathieu

    opened by mathieu-salzmann 2
  • switch to disable intrinsic functions

    switch to disable intrinsic functions

    When calling the function sqrt() I stumbled across a message from my compiler: Error: Unsupported intrinsic: llvm.ctlz.i64

    Reason: the function find_highest_bit() uses intrinsic functions (for performance reasons). I use a modified gcc here which does not support intrinsic calls.

    I have adapted my code as follows, possibly this would be also an option for the main branch:

    By using a preprocessor switch FPM_NO_INTRINSIC you can prevent the use of intrinsic calls and at the same time the code works on many compilers which are not supported so far.

    inline long find_highest_bit(unsigned long long value) noexcept
    {
        assert(value != 0);
    #if defined(FPM_NO_INTRINSIC) // Note: Non-optimised Version
        int count = 0;
        while (value >>= 1) {count ++;}  
        return count;
    #elif defined(_MSC_VER)
        unsigned long index;
    #if defined(_WIN64)
        _BitScanReverse64(&index, value);
    #else
        if (_BitScanReverse(&index, static_cast<unsigned long>(value >> 32)) != 0) {
            index += 32;
        } else {
            _BitScanReverse(&index, static_cast<unsigned long>(value & 0xfffffffflu));
        }
    #endif
        return index;
    #elif defined(__GNUC__) || defined(__clang__)
        return sizeof(value) * 8 - 1 - __builtin_clzll(value);
    #else
    #   error "your platform does not support find_highest_bit()"
    #endif
    }
    

    (Admittedly, the code is slow, if necessary I can include an optimized version with bitmasks).

    One question: Is there a reason why find_highest_bit() returns a datatype long instead of int?

    enhancement 
    opened by Klummel69 1
Releases(v1.1.0)
  • v1.1.0(Jul 27, 2021)

    Changelog:

    • New feature: allow explicit conversion between different fpm::fixed types
    • New feature: improve accuracy for atan2, asin and acos in edge cases for fpm::fixed types with limited integer bits
    • Fix a C++11 compilation error in fpm/ios.h
    • Fix operator<< for fpm::fixed at its negative limit
    Source code(tar.gz)
    Source code(zip)
  • v1.0.2(Jun 10, 2021)

  • v1.0.1(Mar 11, 2020)

  • v1.0.0(Feb 11, 2020)

Owner
Mike Lankamp
A C++ software engineer working in the Netherlands with game development as a hobby.
Mike Lankamp
linalg.h is a single header, public domain, short vector math library for C++

linalg.h linalg.h is a single header, public domain, short vector math library for C++. It is inspired by the syntax of popular shading and compute la

Sterling Orsten 758 Jan 7, 2023
a lean linear math library, aimed at graphics programming. Supports vec3, vec4, mat4x4 and quaternions

linmath.h -- A small library for linear math as required for computer graphics linmath.h provides the most used types required for programming compute

datenwolf 729 Jan 9, 2023
📽 Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C

Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C`. cglm provides lot of utils to help math operations to be fast and quick to write. It is community friendly, feel free to bring any issues, bugs you faced.

Recep Aslantas 1.6k Jan 2, 2023
Simple long integer math library for C++

SLIMCPP Simple long integer math library for C++ SLIMCPP is C++ header-only library that implements long integers that exceed maximum size of native t

null 23 Dec 1, 2022
C++ Matrix -- High performance and accurate (e.g. edge cases) matrix math library with expression template arithmetic operators

Matrix This is a math and arithmetic matrix library. It has stood many years of performing in mission critical production for financial systems. It ha

Hossein Moein 71 Oct 29, 2022
Math library using hlsl syntax with SSE/NEON support

HLSL++ Small header-only math library for C++ with the same syntax as the hlsl shading language. It supports any SSE (x86/x64 devices like PC, Mac, PS

null 354 Dec 22, 2022
tiny recursive descent expression parser, compiler, and evaluation engine for math expressions

TinyExpr TinyExpr is a very small recursive descent parser and evaluation engine for math expressions. It's handy when you want to add the ability to

Lewis Van Winkle 1.2k Jan 6, 2023
Fast math tool written on asm/c

math_tool fast math tool written on asm/c This project was created for easy use of mathematical / geometric rules and operations. This project contain

portable executable 3 Mar 8, 2022
A C++ header-only library of statistical distribution functions.

StatsLib StatsLib is a templated C++ library of statistical distribution functions, featuring unique compile-time computing capabilities and seamless

Keith O'Hara 423 Jan 3, 2023
RcppFastFloat: Rcpp Bindings for the fastfloat C++ Header-Only Library

Converting ascii text into (floating-point) numeric values is a very common problem. The fast_float header-only C++ library by Daniel Lemire does this very well, and very fast at up to or over to 1 gigabyte per second as described in more detail in a recent arXiv paper.

Dirk Eddelbuettel 18 Nov 15, 2022
Header only FFT library

dj_fft: Header-only FFT library Details This repository provides a header-only library to compute fourier transforms in 1D, 2D, and 3D. Its goal is to

Jonathan Dupuy 134 Dec 29, 2022
C++ header-only library with methods to efficiently encode/decode Morton codes in/from 2D/3D coordinates

Libmorton v0.2.7 Libmorton is a C++ header-only library with methods to efficiently encode/decode 64, 32 and 16-bit Morton codes and coordinates, in 2

Jeroen Baert 488 Dec 31, 2022
Extremely simple yet powerful header-only C++ plotting library built on the popular matplotlib

matplotlib-cpp Welcome to matplotlib-cpp, possibly the simplest C++ plotting library. It is built to resemble the plotting API used by Matlab and matp

Benno Evers 3.6k Dec 30, 2022
A modern, C++20-native, single-file header-only dense 2D matrix library.

A modern, C++20-native, single-file header-only dense 2D matrix library. Contents Example usage creating matrices basic operations row, col, size, sha

feng wang 62 Dec 17, 2022
A header-only C++ library for large scale eigenvalue problems

NOTE: Spectra 1.0.0 is released, with a lot of API-breaking changes. Please see the migration guide for a smooth transition to the new version. NOTE:

Yixuan Qiu 609 Jan 2, 2023
libmpc++ is a C++ header-only library to solve linear and non-linear MPC

libmpc++ libmpc++ is a C++ library to solve linear and non-linear MPC. The library is written in modern C++17 and it is tested to work on Linux, macOS

Nicola Piccinelli 46 Dec 20, 2022
Header-only C++11 library to handle physical measures

cpp-measures Header-only C++11 library to handle physical measures License: This project is released under the Mozilla Public License 2.0. Purpose Thi

Carlo Milanesi 20 Jun 28, 2018
Header only, single file, simple and efficient C++ library to compute the signed distance function to a triangle mesh

TriangleMeshDistance Header only, single file, simple and efficient C++11 library to compute the signed distance function to a triangle mesh. The dist

Interactive Computer Graphics 100 Dec 28, 2022
A work-in-progress C++20/23 header-only maths library for game development, embedded, kernel and general-purpose that works in constant context.

kMath /kmæθ/ A work-in-progress general-purpose C++20/23 header-only maths library that works in constant context Abstract The kMath Project aims to p

The λ Project 13 Sep 5, 2022