Повышайте мультиточность: создание экземпляра рекурсивного шаблона превысило максимальную длину 256

Пытаясь немного поиграть с числами многоточности 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;
    }
}

c++ boost templates multiprecision
person Lezkus    schedule 13.11.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вашему обходному пути не хватает понимания.

Проблема возникает из-за того, что компилятор возвращает шаблоны выражений с ленивой оценкой. Это приводит к рекурсивным вызовам для создания различных экземпляров для каждого уровня рекурсии в fastPowMod бесконечно.

Предлагаемое вами исправление отключает его, заставляя аргументы рекурсивного вызова оцениваться.

Точно так же вы можете полностью отключить ET:

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

В этом конкретном случае вы можете рассмотреть возможность преобразования рекурсии в итерацию, которую вы или компилятор можете развернуть для нескольких итераций за раз. Таким образом, вы можете сохранить преимущества отложенной оценки.

person sehe    schedule 13.11.2015
comment
Я не совсем понял. Не могли бы вы объяснить процесс немного подробнее? И да, я переписал функцию итеративно, чтобы избежать этих проблем. - person Lezkus; 14.11.2015
comment
Переписывание его итеративным способом на самом деле не позволяет избежать его лучше, чем ваша рекурсивная версия. Преимущество возникает при развертывании итераций, поскольку вы можете извлечь выгоду из отложенной итерации шаблонов выражений. Шаблоны выражений позволяют библиотеке упростить, например. ((i * 3) + 9)/3 в i + (9/3) - достижение снижения мощности. Кроме того, это может уменьшить сложность ((i*j) < 0) до просто сравнения знаков вместо полного умножения. Библиотеки матриц используют те же механизмы только для расчета необходимых элементов матрицы результатов по запросу. - person sehe; 14.11.2015
comment
Ленивые вычисления — очень мощный метод оптимизации. Применимо ли это к вашим формулам я не рассматривал, но вы должны быстро выяснить это с помощью своего профилировщика - person sehe; 14.11.2015