Boost multiprecision:递归模板实例超过最大长度256 [英] Boost multiprecision : Recursive template instantiation exceeded maximum length 256

问题描述

尝试使用Boost的多精度数字有点问题，我遇到了以下错误

Trying to play a little bit with boost's multiprecision numbers I got the following error

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

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

followed with lots of lines with the signature of the instantiation error. The problem arised when compiled the following code:

#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

我不知道为什么会这样，因为用正整数实例化此代码后，该代码可以很好地编译.

I do not know why does this happen, since this code compiles perfectly fine when instantiated with regular integers.

修改:我回答自己.在处理模板和递归时要始终牢记！

Edit: I answer myself. Always remember when dealing with templates and recursion to be explicit!

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;
    }
}

推荐答案

您的解决方法缺乏了解.

Your workaround lacks the understanding.

问题出在编译器返回延迟评估的表达式模板上.这导致递归调用无限地实例化 fastPowMod 中每个递归级别的不同实例.

The problem comes with the compiler returning lazy-evaluated expression templates. This leads to the recursive calls to instantiate different instantiations for each level of recursion in fastPowMod, infinitely.

您建议的修补程序通过强制递归调用的参数进行求值来禁用它.

Your suggested fix disables it by forcing the arguments to the recursive call to get evaluated.

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

Equivalently you might disable ET altogether:

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

在这种特殊情况下，您可能要考虑将递归转换为迭代，您或编译器可能一次展开一些迭代.这样，您可以保留延迟评估带来的好处.

In this particular case you might want to consider morphing recursion into iteration, which you or the compiler might unroll for some iterations at a time. This way you could retain benefits from the lazy-evaluation.

这篇关于Boost multiprecision:递归模板实例超过最大长度256的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！