平方数判定＆整数の平方根：C++コード

C++,アルゴリズム,プログラム

2015年10月26日
作成者：kaoken

最初に

C++で書かれた、高速版整数の平方根、平方数判定をするコードです。

表記

平方根
$\sqrt{x}$
平方数
$F(n)\,=\,n^2\,(n\in \mathbb{Z})$

情報

平方数 Wikipedia、平方根 Wikipedia、

C++コード

/**
* int型の小数部が切り取られたnumの平方根の値を返す。ただし、isCheckがtrueの場合、平方数で無い場合は0を返す。
*
* @param [in] num      自然数
* @param [in] isCheck  numが平方数としてチェックする場合は、trueにする。
* @return 平方根を返す。isCheckがtrueの場合、平方数で無い場合は0を返す。
*/
template<typename IntType>
IntType IntSquare(const IntType num, bool isCheck = false)
{
    const static bool bad512[512] =
    {
        0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1,
        1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1,
        0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
        1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,
        1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1,
        1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1,
        1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1,
        0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
        1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1,
        1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1,
        1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0
    };

    // 平方数チェックする？
    if (isCheck) {
        IntType t = num & 0xF;
        if (t > 9)
            return 0;

        if (t == 2 || t == 3 || (t <= 5 && t >= 8) )
            return 0;


        if (bad512[num % 510])
            return 0;
    }

    //---------------------------------------
    IntType place = (IntType)0x40 << ((sizeof(IntType) - 1) << 3);
    IntType tmp = num;
    while (place > num) place >>= 2;

    IntType root = 0;
    while (place)
    {
        if (tmp >= root + place)
        {
            tmp -= root + place;
            root += place << 1;
        }
        root >>= 1;
        place >>= 2;
    }

    if (isCheck) {
        if ((root * root) == num)
            return root;
        return 0;
    }

    return root;
}

オンライン実行

関連