nholthaus / units / 912
0%
master: 0%

LAST BUILD BRANCH: v3.x
DEFAULT BRANCH: master
Ran
Jobs 2
Files 1
Run time 20s
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
912

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

Jobs
ID Job ID Ran Files Coverage
1 912.1 (MATRIX_EVAL="CC=gcc && CXX=g++" COVERALLS_SERVICE_NAME=travis-ci COVERALLS_REPO_TOKEN=[secure]) 0
0.0
 Travis Job 912.1
2 912.2 (MATRIX_EVAL="CC=clang && CXX=clang++") 0
0.0
 Travis Job 912.2
Source Files on build 912
Detailed source file information is not available for this build.