1

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

with

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;
    }
}
Lezkus
  • 160
  • 1
  • 12

1 Answers1

0

Your workaround lacks the understanding.

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.

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.

sehe
  • 374,641
  • 47
  • 450
  • 633
  • I did not quite get it. Could you explain the process a little bit more in detail? And yes, I rewrote the function in an iterative way to avoid these problems. – Lezkus Nov 14 '15 at 16:03
  • Rewriting it in an iterative way doesn't actually avoid it any better than your recursive version. The benefit comes when unrolling iterations because you may benefit from the expression templates lazy iteration. Expression templates allow the library to simplify e.g. `((i * 3) + 9)/3` into `i + (9/3)` - achieving power reduction. Also, it could reduce the complexity of `((i*j) < 0)` to _just_ sign comparisons, instead of doing the multiplication in full. Matrix libraries use the same mechanisms to only calculate required result matrix elements on demand. – sehe Nov 14 '15 at 16:16
  • Lazy computation is a very powerful optimization technique. Whether it applies to your formulae I haven't considered, but you should quickly find out using your profiler – sehe Nov 14 '15 at 16:16