In C++11 is sqrt defined as constexpr?

Question

In C++11 is std::sqrt defined as constexpr, i.e. can it legally be used from other constexpr functions or in compile-time contexts like array sizes or template arguments? g++ seems to allow it (using -std=c++0x), but I'm not sure I can take that as authoritative given that c++0x/c++11 support is still incomplete. The fact that I can't seem to find anything on the Internet makes me unsure.

It seems like this should be something one could easily find out using Google, but I've tried (for 40 minutes now...) and couldn't find anything. I could find several proposals for adding constexpr to various parts of the standard library (like for example this one), but nothing about sqrt or other math functions.

score 35 · Accepted Answer · answered Dec 24 '11 at 02:23

35

std::sqrt is not defined as constexpr, according to section 26.8 of N3291: the C++11 FDIS (and I doubt they added it to the final standard after that). One could possibly write such a version, but the standard library version is not constexpr.

answered Dec 24 '11 at 02:23

Nicol Bolas

449,505
63
781
982

2

Is this stated there explicitly? 26.8 C library makes no reference to constexpr. An implementation would surely still be conformant if it provided constexpr function implementations in addition to those mandated without. – user2023370 May 16 '12 at 22:44
@NicolBolas IIRC adding `constexpr` is not allowed by the standard. – L. F. Aug 30 '19 at 06:44

score 28 · Answer 2 · answered Dec 07 '15 at 12:54

Here is a fast and efficient constexpr implementation for double floating point numbers. You may adapt it to float too, if needed:

#include <limits>   

namespace Detail
{
    double constexpr sqrtNewtonRaphson(double x, double curr, double prev)
    {
        return curr == prev
            ? curr
            : sqrtNewtonRaphson(x, 0.5 * (curr + x / curr), curr);
    }
}

/*
* Constexpr version of the square root
* Return value:
*   - For a finite and non-negative value of "x", returns an approximation for the square root of "x"
*   - Otherwise, returns NaN
*/
double constexpr sqrt(double x)
{
    return x >= 0 && x < std::numeric_limits<double>::infinity()
        ? Detail::sqrtNewtonRaphson(x, x, 0)
        : std::numeric_limits<double>::quiet_NaN();
}

score 24 · Answer 3 · answered Dec 24 '11 at 14:11

24

Just in case anyone is interested in a meta integer square root function, here is one I wrote while a ago:

constexpr std::size_t isqrt_impl
    (std::size_t sq, std::size_t dlt, std::size_t value){
    return sq <= value ?
        isqrt_impl(sq+dlt, dlt+2, value) : (dlt >> 1) - 1;
}

constexpr std::size_t isqrt(std::size_t value){
    return isqrt_impl(1, 3, value);
}

answered Dec 24 '11 at 14:11

Khaled Alshaya

94,250
39
176
234

Umm, that seems to have linear complexity , i.e. Theta(value), rather than logarithmic, which is quite achievable, e.g. in @Linoliumz 's answer. – einpoklum Feb 10 '16 at 11:57

Linoliumz · Answer 4 · 2014-12-31T12:28:07.633

15

Below is a constexpr square root implementation that uses binary search. It works correctly up to 2^64 with gcc and clang, other simpler versions often fail for numbers > 2^32 because compilers limit the recursion depth to e.g. 200.

// C++11 compile time square root using binary search

#define MID ((lo + hi + 1) / 2)

constexpr uint64_t sqrt_helper(uint64_t x, uint64_t lo, uint64_t hi)
{
  return lo == hi ? lo : ((x / MID < MID)
      ? sqrt_helper(x, lo, MID - 1) : sqrt_helper(x, MID, hi));
}

constexpr uint64_t ct_sqrt(uint64_t x)
{
  return sqrt_helper(x, 0, x / 2 + 1);
}

Below is a nicer version (for integer constants) which requires C++14, it is similar to the one presented in Baptiste Wicht's blog post. C++14 constexpr functions are allowed to use local variables and if statements.

// C++14 compile time square root using binary search

template <typename T>
constexpr T sqrt_helper(T x, T lo, T hi)
{
  if (lo == hi)
    return lo;

  const T mid = (lo + hi + 1) / 2;

  if (x / mid < mid)
    return sqrt_helper<T>(x, lo, mid - 1);
  else
    return sqrt_helper(x, mid, hi);
}

template <typename T>
constexpr T ct_sqrt(T x)
{
  return sqrt_helper<T>(x, 0, x / 2 + 1);
}

edited Dec 31 '14 at 12:28

answered Dec 30 '14 at 16:42

Linoliumz

2,381
3
28
35

1

Why is `MID` a macro? – dyp Dec 30 '14 at 16:51
1

Because in C++11 static const variables inside constexpr functions are not allowed. – Linoliumz Dec 30 '14 at 18:17
Is this for show, or do people really use something that takes over 200 recursions to compile? – Mikhail Dec 30 '14 at 19:01
@Mikhail: This version doesn't take 200 recursions. AraK's does. This version just takes about `log_2(x)` iterations, which is pretty reasonable. – Cornstalks Dec 30 '14 at 19:24
I use in my program to calculate the square root of std::numeric_limits::max() at compile time, T can be int32_t, int64_t, __int128_t or __uint128_t which uses up to 128 recursions. – Linoliumz Dec 30 '14 at 19:24
A `static` variable could also be harmful, since this function can be called by multiple threads concurrently at runtime. But why not `constexpr uint64_t mid(uint64_t lo, uint64_t hi) { return (lo + hi + uint64_t(1)) / uint64_t(2); }`? You could compute this once and pass `lo`, `hi` and the result of `mid` to a `sqrt_helper2`, although that could double the amount of recursions. – dyp Dec 30 '14 at 19:59
3

It is even possible to use up only one more level of recursion and make `mid` a function: http://coliru.stacked-crooked.com/a/f6e2be98d2c2aed6 – dyp Dec 30 '14 at 20:06
This only works for integers, right? The answer is unclear on that... if it's true, there should probably some enable_if machinery to forbid specialization for real numbers. – celticminstrel Dec 02 '21 at 15:37

score 11 · Answer 5 · answered Aug 03 '20 at 15:25

11

There is now a proposal P1383R0 More constexpr for <cmath> and <complex> (Edward J. Rosten, Oliver J. Rosten) which unfortunately hasn't gotten into C++20 and from the latest comment may not be in C++23 either. C++26?

answered Aug 03 '20 at 15:25

Alexey Romanov

167,066
35
309
487

score 10 · Answer 6 · edited May 23 '17 at 12:03

If we look at the closest draft standard to C++11 N3337 we can see that sqrt is not marked constexpr, from section 26.8 c.math:

The contents of these headers are the same as the Standard C library headers and respectively, with the following changes:

none of the changes include adding constexpr to sqrt.

We can see from the question Is gcc considering builtins of non-constant expression functions to be constant expressions, that gcc marks many math functions as constexpr as an extension. This extension is a non-conforming extension, as I note in my answer to the linked question when gcc implemented this it looked like it would be a conforming extension but this changed and gcc is likely to fix this this extension to be conforming.

In C++11 is sqrt defined as constexpr?

6 Answers6

Linked