nholthaus / units
0%
master: 0%

LAST BUILD BRANCH: v3.x
DEFAULT BRANCH: master
Repo Added
Files 0
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

LAST BUILD ON BRANCH 3.0.0.alpha-3
branch: 3.0.0.alpha-3
CHANGE BRANCH
x

914

push

travis-ci

web-flow 
Use exponentiation by squares for pow() (#262)

Multiple pow() implementations were considered:

  1. A naive linear recursive implementation (the existing
     implementation)
  2. A tail-recursive linear implementation
  3. A non-tail-recursive exponentiation by squares implementation
  4. A tail-recursive exponentiation by squares implementation
  5. An iterative implementation ("right-to-left binary method" [0])

Based on quick and dirty benchmarks on a 2015 Retina Pro 2.8 GHz (source
code in [1, 2], results in [3]), implementation 4 was chosen since it
resulted in good benchmark numbers for a wide range of exponents for
both GCC and Clang.

Some implementation notes:

  - No restrictions were placed on the template parameters for pow_acc()
    because it is assumed that it will only be called in one place,
    which means the type of the passed parameters should be definitively
    known.
  - x is possibly promoted before being passed to the helper function as
    it is multiplied by itself in the helper, which can result in
    overflow for smaller types.
  - The implementation for negative exponents is not entirely
    tail-recursive to account for the possbility that someone passes in
    INT_MIN/etc. If this is deemed too unlikely, then the implementation
    can be simplified to (with appropriate promotion):
        return pow(1 / x, static_cast<unsigned long long>(-y));

[0]: https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

[1]: CMakeLists.txt:

    cmake_minimum_required(VERSION 3.18)
    project(pow-benchmarks)
    set(CMAKE_CXX_EXTENSIONS OFF)

    add_subdirectory(benchmark/)

    add_executable(main main.cpp)
    target_link_libraries(main benchmark::benchmark)
    target_compile_features(main
      PRIVATE cxx_std_17
    )
    target_compile_options(main
      PRIVATE -march=native
    )

[2]: main.cpp

    #include <benchmark/benchmark.h>

    conste... (continued)

0 of 0 relevant lines covered (NaN%)

0.0 hits per line

Relevant lines Covered
0 RELEVANT LINES 0 COVERED LINES
0.0 HITS PER LINE
Source Files on 3.0.0.alpha-3

Recent builds

Builds Branch Commit Type Ran Committer Via Coverage
914 3.0.0.alpha-3 Use exponentiation by squares for pow() (#262) Multiple pow() implementations were considered: 1. A naive linear recursive implementation (the existing implementation) 2. A tail-recursive linear implementation 3. A non-tail-recur... push web-flow travis-ci pending completion  
See All Builds (337)