From b2ae6ce3b6fc237e85cc988ad4a47a8453250b88 Mon Sep 17 00:00:00 2001
From: Yedidya Feldblum <yfeldblum@fb.com>
Date: Sat, 30 Dec 2017 16:08:32 -0800
Subject: [PATCH] constexpr_pow

Summary:
[Folly] `constexpr_pow`.

The power function. Initially, supports nonnegative integers only.

Reviewed By: spalamarchuk

Differential Revision: D6646376

fbshipit-source-id: 33a5a45f496b6f3be52d0cd7e3a5f2cd7edb3026
---
 folly/ConstexprMath.h            | 14 ++++++++++++++
 folly/test/ConstexprMathTest.cpp | 15 +++++++++++++++
 2 files changed, 29 insertions(+)

diff --git a/folly/ConstexprMath.h b/folly/ConstexprMath.h
index a15f098c..871b1943 100644
--- a/folly/ConstexprMath.h
+++ b/folly/ConstexprMath.h
@@ -113,6 +113,11 @@ template <typename T>
 constexpr T constexpr_log2_ceil_(T l2, T t) {
   return l2 + T(T(1) << l2 < t ? 1 : 0);
 }
+
+template <typename T>
+constexpr T constexpr_square_(T t) {
+  return t * t;
+}
 } // namespace detail
 
 template <typename T>
@@ -132,4 +137,13 @@ constexpr T constexpr_ceil(T t, T round) {
       : ((t + (t < T(0) ? T(0) : round - T(1))) / round) * round;
 }
 
+template <typename T>
+constexpr T constexpr_pow(T base, std::size_t exp) {
+  return exp == 0
+      ? T(1)
+      : exp == 1 ? base
+                 : detail::constexpr_square_(constexpr_pow(base, exp / 2)) *
+              (exp % 2 ? base : T(1));
+}
+
 } // namespace folly
diff --git a/folly/test/ConstexprMathTest.cpp b/folly/test/ConstexprMathTest.cpp
index a0f9b102..fb5956e2 100644
--- a/folly/test/ConstexprMathTest.cpp
+++ b/folly/test/ConstexprMathTest.cpp
@@ -178,3 +178,18 @@ TEST_F(ConstexprMathTest, constexpr_ceil) {
     EXPECT_EQ(-20ll, rounded);
   }
 }
+
+TEST_F(ConstexprMathTest, constexpr_pow) {
+  {
+    constexpr auto a = folly::constexpr_pow(uint64_t(0), 15);
+    EXPECT_EQ(0, a);
+  }
+  {
+    constexpr auto a = folly::constexpr_pow(uint64_t(15), 0);
+    EXPECT_EQ(1, a);
+  }
+  {
+    constexpr auto a = folly::constexpr_pow(uint64_t(2), 6);
+    EXPECT_EQ(64, a);
+  }
+}
-- 
2.34.1