37 lines
750 B
C++
37 lines
750 B
C++
/*
|
|
* Project Euler Solutions - Shared Utilities Module
|
|
* -----------------------------------------------
|
|
* File : sqrt.hpp
|
|
*
|
|
* Author : erick-alcachofa
|
|
* Created : Monday, August 04 2025
|
|
*
|
|
* Notes:
|
|
* - constexpr sqrt function
|
|
*
|
|
* License : GNU Affero General Public License v3.0 (AGPLv3)
|
|
* https://www.gnu.org/licenses/agpl-3.0.html
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
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);
|
|
}
|