johnmcfarlane / fixed_point

C++ Binary Fixed-Point Arithmetic

fixed_point Numerics Library

Notice: This library is deprecated. Please consider switching to CNL, the successor to fixed_point for many new features and improvements.

Description

The fixed_point library provides a header-only C++11 API for approximating real numbers using binary fixed-point arithmetic. It forms the reference implementation of a standard library proposal presented in paper, P0037 and is developed as part of study groups, SG14 and SG6.

Download

The library is hosted on GitHub:

$ git clone https://github.com/johnmcfarlane/fixed_point.git

The API is exposed through headers in the include directory. Add this to your system header list and include, e.g.:

#include <sg14/fixed_point>

Tests and Benchmarks

Linux

Tested on Travis (Ubuntu 14.04) using GCC 5.4 and Clang 3.5 and Debian GNU/Linux 8.3 using GCC 5.4 and Clang 3.5.0.

Requires:

• G++ 5.4
• CMake 3.2

Optional:

• Boost - facilitates multiprecision support
• Doxygen - generates documentation in the doc/gh-pages directory
• pandoc - generates proposal papers

For a list of configuration options:

$ cmake -LH

To build everything:

$ cmake -DCMAKE_BUILD_TYPE=Release
$ make

To disable exception handling (incompatible with Boost 1.55 or lower), add -DEXCEPTIONS=OFF to the cmake command:

$ cmake -DCMAKE_BUILD_TYPE=Release -DEXCEPTIONS=OFF
$ make

To run tests:

$ cmake -DCMAKE_BUILD_TYPE=Release
$ make fp_test
$ ./fp_test

To run benchmarks:

$ cmake -DCMAKE_BUILD_TYPE=Release
$ make fp_benchmark
$ ./fp_benchmark

To profile benchmarks:

1. Build with frame pointers included:

   $ cmake -DCMAKE_BUILD_TYPE=Release -DPROFILE=ON
   $ make fp_benchmark
   $ ./fp_benchmark

2. then run:

   $ perf record -g ./fp_benchmark
   $ perf report -g 'graph,0.5,caller'

To install:

$ cmake -DCMAKE_BUILD_TYPE=Release
$ make
$ sudo make install

Windows

Tested on AppVeyor and on Windows 10 Professional with CMake 3.8.0. Requires:

• MSBuild 15.0 (VS 2017)
• CMake 3.8.0

To build vs/Release/fp_test.exe and vs/Release/fp_benchmark.exe:

cmake -G "Visual Studio 15 2017" .
MSBuild.exe /m fixed_point.sln /p:Configuration=Release

For 64-bit builds, append Win64 to the -G option above:

cmake -G "Visual Studio 15 2017 Win64" .

Note that fp_benchmark is unlikely to produce valid results due to missing escape and clobber functions.

Cleaning

To clean the project files:

git clean -Xdff .

(Use with caution!)

Further Reading

• documentation
• latest draft of C++ Standard Library proposal, P0037
• position paper illustrating the compositonal approach, P0554
• forum of Study Group 14

Contact Information

All feedback greatly appreciated.

• GitHub
• SG14 forum
• [email protected]

fixed_point's Issues

Integer mixed-mode arithmetic operations should use `promote_fast`

Generally, common_type involving fixed_point should behave closer to ReprType.

Typo in fixed_point_extras.h

"straddle two 'homes"

Pursue parity between fixed_point and int

In particular:

• compound assignment
• bitwise operations
• shift operators - static and dynamic
• basically anything in this list that can be overloaded

Non-explicit conversions for types that won't cause information loss

GDC2016 Feedback

Mention predictability.

Correct description of `operator<<` and `>>`

Claims no loss of bits. And hey, why not actually implement those!

move multiprecision.h to sg14

but maybe to sub-folder auxiliary and move elastic there too

exploit boost.multiprecision aliases

As with the fp library, make multiprecision.h simpler by using the boost::multiprecision::cpp_int (or whatever) types.

fix up arithmetic functions

move multiply etc. into sg14 and remove promot and trunc etc.

simplify make_fixed

don't throw spare bits at fractional_digits!

Update *Required Specializations*

Section of P0037

Incorporate Ryhor's functions

Convert these functions to C++11 constexpr type and add to fixed_point_utils.h.

Add explanation to p0037

To answer the Jacksonville questions:

• How does resize work with user-supplied representations? and
• The specialization of numeric limits is good. We wonder how it might apply to unbounded types.

Write general purpose arithmetic functions

As mentioned in section Alternative Return Type Policies of P0037R1.

Minor clean-up of type_traits.h and int128.h

Remove code surrounded in _GLIBCXX_USE_INT128 from type_traits.h. It can all live in bits/int128.h.

replace `resize`

cpp_int proves that sizeof and resize are not complements of one another. What about set_width? It takes bits, not bytes. Parameter can be unsigned - for now at least.

Convert code blocks

This style

template <typename N>
struct S;

is not as colorful as

template <typename N>
struct S;

remove all traits specializations

Very touchy subject, so move e.g. std::make_unsigned<fixed_point<>> to sg14 namespace.

solve the compact vs fast problem

With elastic type.

std::is_real should probably fail for fixed_point<>

fixed_point overused

Use the phrase fixed-point more often in line with floating-point and integer/integral.

Boost incompatible with -DEXCEPTIONS=OFF

Excluded it when exceptions are off.

not all c'tors or conversion operators should be explicit

Casting where all three of signage, integer digits and fractional digits of the destination match or exceed the source should not be explicit.

Write simple resize helper

Such that built-in integer resize can be defined as:

template <typename UnsignedInteger>
struct resize 
    : resize_family
    <
        UnsignedInteger, uint8_t, uint16_t, uint32_t, uint64_t, unsigned __128int_t
    > {};

template <typename SignedInteger>
struct resize 
    : resize_family
    <
        SignedInteger, int8_t, int16_t, int32_t, int64_t, signed __128int_t
    > {};

Remove obsolete section

Alternative Return Type Policies suggests work that has since been executed upon.

move stuff from *fixed_point_traits.h* to *fixed_point.h*

Document multiply & other named functions

Prove single-instruction specialization

E.g. an instruction that multiplies with saturation, then shifts right by 15 digits.

improve README.md

Move installation instructions to README.md
Clearer link
link in other direction
Better blurb/highlights in index.md and README.md
Include notes about cmark, Doxygen and boost
Links to source in index.mf

Improved accuracy of comparison operators

Possibly as named function?

Test boost online

add profiling flag to cmake scripts

and replace hacky instruction about -fno-omit-frame-pointer in index.md

`rename _impl` to `_fixed_point_impl`

Wrong perf command

On main instruction page, perf stat ./run_benchmarks should read perf record -g ./run_benchmarks.

P0106 types implemented somewhere

Investigate why tests aren't failing on MSVC

Multiplication between 64-bit numbers should overflow and/or cause compiler errors on platforms with no 128-bit integers and MSVC++ doesn't have 128-bit integers. But tests pass. Make sure tests are robust enough.

README.md fixes

Link to P0037 broken and title sucks

size_t -> unsigned

via an alias

make_fixed_from<...>

Also floating-point literals for elastic equivalent.

make_fixed/ufixed to add spare digits to integer bits

Fix instances of MSVC warning, C4309

Currently disabled via common.cmake.

Ryhor's hints

Follow up on the helpful advice provided by Ryhor.

Mention that '"Exponent" will typically be negative'

Suggestion via Paul Robinson:

"Exponent" will typically be negative
The proposal doesn't discuss this but the typical use-case of a value
with both integer and fractional digits would require Exponent to be
negative. For example make_ufixed<4, 4> would have to be the same type
as fixed_point<uint8_t, -4> (in order for the stated maximum/minimum
values to work out correctly). This is perfectly fine, but when it
comes to working out the wording in the standard, this would definitely
be worthy of an example or footnote.

conversion between elastic and std::bitset

Everything from previous repo

include all_of_this

License

There is no licensing information provided, could this please be clarified? Thank you.

add is_integral to requirements for integer concept

Improve accuracy of description of `promote_` functions

As suggested by Paul Robinson

"Named arithmetic functions" (promote_*)

test fixed_point where Rep is itself fixed_point

Rename ReprType to Rep

And repr_type to rep in line with chrono.