浮動小数点が使えない環境での平方根の計算

浮動小数点がない組み込み環境で平方根を計算しないといけないので下記のサイトを参考に高速化してみた。
https://talavax.com/math-sqrtint.html

動機としては値が大きくなると遅くなるのでどうにかしたい。
なので計算が簡単な2のべき乗の平方根はメモ化して定数化、そこを起点に計算をするように変更した。

（追記）Nが大きい場合は二分法を使ったほうが速いようです

# include <cmath>
# include <iostream>
# include <type_traits>

template <typename T>
inline T sqrti(T val) {
  // static_assert(std::is_integral<T>::value == true);
  const struct _intern {
    static constexpr T compute_substractor(T root) {
      T c = 1;
      for (T num = root * root; num >= c; num -= c, c += 2)
        ;
      return c;
    }

    T table[sizeof(T) * 4];

    _intern(void) {
      for (T i = 0; i < (T)(sizeof(T) * 4); ++i) {
        table[i] = compute_substractor(1 << i);
      }
    }
  } intern;

  if (val == 0) {
    return 0;
  }

  T rank_base2 = (T)(sizeof(T) * 8 - 1);
  for (; rank_base2 > 0; --rank_base2) {
    if ((val & (1 << rank_base2)) != 0) {
      break;
    }
  }

  const T min_root_rank_base2 = rank_base2 >> 1;
  T root = 1 << min_root_rank_base2;
  for (T num = val - root * root, c = intern.table[min_root_rank_base2];
       num >= c; num -= c, c += 2, ++root)
    ;

  return root;
}

int main() {
  std::cout << "test" << std::endl;
  for (unsigned short i = 1; i < 0xFFFFU; ++i) {
    if (sqrti(i) != (unsigned short)sqrt(i)) {
      std::cout << "ng" << std::endl;
      return -1;
    }
  }
  std::cout << "ok" << std::endl;
  return 0;
}