C integer pow() and log10()

integer_pow_log10.c

	// https://www.rookieslab.com/posts/fast-power-algorithm-exponentiation-by-squaring-cpp-python-implementation
#define MOD 1000000007
	uint64_t fast_power(uint64_t base, uint64_t power) {
		uint64_t result = 1;
		while (power > 0) {

			if (power % 2 == 1) { // Can also use (power & 1) to make code even faster
				result = (result*base) % MOD;
			}
			base = (base * base) % MOD;
			power = power / 2; // Can also use power >>= 1; to make code even faster
		}
		return result;
	}

	uint64_t ulog2(uint64_t u)
	{
		uint64_t s, t;

		t = (u > 0xffff) << 4; u >>= t;
		s = (u > 0xff)   << 3; u >>= s, t |= s;
		s = (u > 0xf)    << 2; u >>= s, t |= s;
		s = (u > 0x3)    << 1; u >>= s, t |= s;

		return (t | (u >> 1));
	}

	/* Definitions for builtins unavailable on MSVC */
#if defined(_MSC_VER) && !defined(__clang__)
#include <intrin.h>

	uint32_t __inline __builtin_ctz(uint32_t value) {
		unsigned long trailing_zero = 0;
		if (_BitScanForward(&trailing_zero, value))
			return trailing_zero;
		return 32;
	}

	uint32_t __inline __builtin_clz(uint32_t value) {
		unsigned long leading_zero = 0;
		if (_BitScanReverse(&leading_zero, value))
			return 31 - leading_zero;
		return 32;
	}

#if defined(_M_ARM) || defined(_M_X64)
	uint32_t __inline __builtin_clzll(uint64_t value) {
		unsigned long leading_zero = 0;
		if (_BitScanReverse64(&leading_zero, value))
			return 63 - leading_zero;
		return 64;
	}
#else
	uint32_t __inline __builtin_clzll(uint64_t value) {
		if (value == 0)
			return 64;
		uint32_t msh = (uint32_t)(value >> 32);
		uint32_t lsh = (uint32_t)(value & 0xFFFFFFFF);
		if (msh != 0)
			return __builtin_clz(msh);
		return 32 + __builtin_clz(lsh);
	}
#endif

#define __builtin_clzl __builtin_clzll
#endif /* defined(_MSC_VER) && !defined(__clang__) */

// https://gist.github.com/CAFxX/ad150f2403a0604e14cc
#include <cstdint>
	uint64_t thr[64] = {
	  10000000000000000000ULL, -1ULL, -1ULL, -1ULL, 1000000000000000000ULL, -1ULL, -1ULL, 100000000000000000ULL, -1ULL, -1ULL,
		 10000000000000000ULL, -1ULL, -1ULL, -1ULL,    1000000000000000ULL, -1ULL, -1ULL,    100000000000000ULL, -1ULL, -1ULL,
			10000000000000ULL, -1ULL, -1ULL, -1ULL,       1000000000000ULL, -1ULL, -1ULL,       100000000000ULL, -1ULL, -1ULL,
			   10000000000ULL, -1ULL, -1ULL, -1ULL,          1000000000ULL, -1ULL, -1ULL,          100000000ULL, -1ULL, -1ULL,
				  10000000ULL, -1ULL, -1ULL, -1ULL,             1000000ULL, -1ULL, -1ULL,             100000ULL, -1ULL, -1ULL,
					 10000ULL, -1ULL, -1ULL, -1ULL,                1000ULL, -1ULL, -1ULL,                100ULL, -1ULL, -1ULL,
						10ULL, -1ULL, -1ULL, -1ULL
	};
	uint32_t ilog10c(uint64_t v) {
#if 1 // requires c++14
		uint32_t lz = __builtin_clzll(v);
		return (63 - lz) * 77 / 256 + (v >= thr[lz]);
#else  // some versions of gcc require uncommenting the /* 63 & */
		return uint32_t((63 ^ __builtin_clzll(v))) * 77 / 256 + (v >= thr[/* 63 & */ __builtin_clzll(v)]);
#endif
	}