1

尝试使用boost的多精度数字玩一点我得到了以下错误

In file included from main.cpp:1:
In file included from /usr/include/boost/multiprecision/cpp_int.hpp:12:
In file included from /usr/include/boost/multiprecision/number.hpp:16:
In file included from /usr/include/boost/type_traits/is_signed.hpp:15:
In file included from /usr/include/boost/type_traits/is_enum.hpp:14:
In file included from /usr/include/boost/type_traits/intrinsics.hpp:149:
/usr/include/boost/type_traits/is_reference.hpp:32:19: fatal error: recursive template instantiation exceeded maximum
      depth of 256

后面有很多带有实例化错误签名的行。编译以下代码时出现问题：

#include<boost/multiprecision/cpp_int.hpp>

using big_int = boost::multiprecision::cpp_int;

big_int getOne(big_int){ return (big_int) 1;}

template<typename T, typename U>
T fastPowMod(T a, U b, T p){
    if(b==0)
        return getOne(a);
    if(b%2 != 0){
        return (a*fastPowMod(a,b-1,p))%p;
    }
    else{
        T aux = fastPowMod(a,b/2,p);
        return (aux*aux)%p;
    }
}

int main(){
    std::cout << fastPowMod<big_int,big_int>(108041234,180611234, 81243) std::endl;
}

和

clang++ -std=c++11 main.cpp

我不知道为什么会发生这种情况，因为这段代码在用常规整数实例化时编译得非常好。

编辑：我自己回答。永远记住在处理模板和递归时要明确！

template<typename T, typename U>
T fastPowMod(T a, U b, T p){
    if(b==0)
        return getOne(a);
    if(b%2 != 0){
        return (a*fastPowMod<T,U>(a,b-1,p))%p;
    }
    else{
        T aux = fastPowMod<T,U>(a,b/2,p);
        return (aux*aux)%p;
    }
}
4

1 回答 1

0

您的解决方法缺乏理解。

问题在于编译器返回惰性求值表达式模板。这导致递归调用以fastPowMod无限地为每个递归级别实例化不同的实例化。

您建议的修复通过强制对递归调用的参数进行评估来禁用它。

等效地，您可以完全禁用 ET：

using big_int = bmp::number<bmp::cpp_int::backend_type, bmp::et_off>;

在这种特殊情况下，您可能需要考虑将递归转换为迭代，您或编译器可能会一次展开一些迭代。这样你就可以保留惰性评估的好处。

于 2015-11-13T15:18:04.980 回答