Boost多精度:递归模板实例化超过最大长度256

Question

试图用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;
    }
}

Answer 1

您的解决方法缺乏理解。

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

建议的修复程序通过强制对递归调用的参数进行求值来禁用它。

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

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

在这种特殊情况下，可能希望考虑将递归变形为迭代，您或编译器可能会一次展开一些迭代。通过这种方式，可以保留懒惰评估带来的好处。