Reimplemented pow5Factor using modular inverse. (#188)

cassioneri · web-flow · commit 77e767f5e056 · 2021-01-27T15:52:42.000+01:00
* Reimplemented pow5Factor using modular inverse.

* Put back assert inadvertently removed.

* Added tests for pow5Factor.

* Fixed comment.
diff --git a/ryu/d2s_intrinsics.h b/ryu/d2s_intrinsics.h
@@ -189,15 +189,14 @@ static inline uint32_t mod1e9(const uint64_t x) {
 #endif // defined(RYU_32_BIT_PLATFORM)
 
 static inline uint32_t pow5Factor(uint64_t value) {
+  const uint64_t m_inv_5 = 14757395258967641293u; // 5 * m_inv_5 = 1 (mod 2^64)
+  const uint64_t n_div_5 = 3689348814741910323u;  // #{ n | n = 0 (mod 2^64) } = 2^64 / 5
   uint32_t count = 0;
   for (;;) {
     assert(value != 0);
-    const uint64_t q = div5(value);
-    const uint32_t r = ((uint32_t) value) - 5 * ((uint32_t) q);
-    if (r != 0) {
+    value *= m_inv_5;
+    if (value > n_div_5)
       break;
-    }
-    value = q;
     ++count;
   }
   return count;
diff --git a/ryu/tests/d2s_intrinsics_test.cc b/ryu/tests/d2s_intrinsics_test.cc
@@ -43,3 +43,43 @@ TEST(D2sIntrinsicsTest, mod1e9) {
 TEST(D2sIntrinsicsTest, shiftRight128) {
   EXPECT_EQ(0x100000000ull, shiftright128(0x1ull, 0x1ull, 32));
 }
+
+TEST(D2sIntrinsicsTest, pow5Factor) {
+  EXPECT_EQ(0u, pow5Factor(1ull));
+  EXPECT_EQ(0u, pow5Factor(2ull));
+  EXPECT_EQ(0u, pow5Factor(3ull));
+  EXPECT_EQ(0u, pow5Factor(4ull));
+  EXPECT_EQ(1u, pow5Factor(5ull));
+  EXPECT_EQ(0u, pow5Factor(6ull));
+  EXPECT_EQ(0u, pow5Factor(7ull));
+  EXPECT_EQ(0u, pow5Factor(8ull));
+  EXPECT_EQ(0u, pow5Factor(9ull));
+  EXPECT_EQ(1u, pow5Factor(10ull));
+
+  EXPECT_EQ(0u, pow5Factor(12ull));
+  EXPECT_EQ(0u, pow5Factor(14ull));
+  EXPECT_EQ(0u, pow5Factor(16ull));
+  EXPECT_EQ(0u, pow5Factor(18ull));
+  EXPECT_EQ(1u, pow5Factor(20ull));
+
+  EXPECT_EQ(2u, pow5Factor(5*5ull));
+  EXPECT_EQ(3u, pow5Factor(5*5*5ull));
+  EXPECT_EQ(4u, pow5Factor(5*5*5*5ull));
+  EXPECT_EQ(5u, pow5Factor(5*5*5*5*5ull));
+  EXPECT_EQ(6u, pow5Factor(5*5*5*5*5*5ull));
+  EXPECT_EQ(7u, pow5Factor(5*5*5*5*5*5*5ull));
+  EXPECT_EQ(8u, pow5Factor(5*5*5*5*5*5*5*5ull));
+  EXPECT_EQ(9u, pow5Factor(5*5*5*5*5*5*5*5*5ull));
+  EXPECT_EQ(10u, pow5Factor(5*5*5*5*5*5*5*5*5*5ull));
+
+  EXPECT_EQ(0u, pow5Factor(42ull));
+  EXPECT_EQ(1u, pow5Factor(42*5ull));
+  EXPECT_EQ(2u, pow5Factor(42*5*5ull));
+  EXPECT_EQ(3u, pow5Factor(42*5*5*5ull));
+  EXPECT_EQ(4u, pow5Factor(42*5*5*5*5ull));
+  EXPECT_EQ(5u, pow5Factor(42*5*5*5*5*5ull));
+
+  EXPECT_EQ(27u, pow5Factor(7450580596923828125ull)); // 5^27, largest power of 5 < 2^64.
+  EXPECT_EQ(1u, pow5Factor(18446744073709551615ull)); // 2^64 - 1, largest multiple of 5 < 2^64.
+  EXPECT_EQ(0u, pow5Factor(18446744073709551614ull)); // 2^64 - 2, largest non-multiple of 5 < 2^64.
+}
