c++ - 如何使用模板在编译时找到 2 个数字的 HCF？

Question

我想使用带有模板递归的枚举值来计算 2 个数字的 HCF:

#include <stdio.h>
template<int x,int y,int r>
struct s{
    enum{e=x%r==0 && y%r==0?r:s<x,y,r-1>::e};
};

int main(){
    printf("%d\n",s<3,5,MIN(3,5)>::e);
    return 0;
};

其中x和y是2个数，r是要测试的值，原理是找一个数来除x和y，从x和y的最小值开始，然后减1，直到r的值可以除 x 和 y。但是由于以下错误，此代码无法编译:

xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -252>'     requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -251>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -250>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -249>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -248>' requested here
xxx.cpp:4:31: note: (skipping 246 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all)
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -1>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 0>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 1>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 2>' requested here
xxx.cpp:8:19: note: in instantiation of template class 's<3, 5, 3>' requested here
printf("%d\n",s<3,5,3>::e);
              ^
xxx.cpp:4:31: note: use -ftemplate-depth=N to increase recursive template instantiation depth
enum{e=x%r==0 && y%r==0?r:s<x,y,r-1>::e};
                          ^
1 error generated.

问题是什么？

Answer 1

@moonshadow 的评论是核心答案，但让我将其扩展为完整答案。

幸运的是，编译器输出显示了相关实例:

xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, -1>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 0>' requested here
xxx.cpp:4:31: note: in instantiation of template class 's<3, 5, 1>' requested here

让我们看看实际的实例化

template<int x = 3, int y = 5, int r = 0>
struct s{
    enum{e = 3%0==0 && 5%0==0 ? 0 : s<5,3,-1>::e};
};

显然，有两件事是错误的:

1. 3 % 0被零除
2. s<5,3,-1> 的实例化是不必要的。

这很容易用 constexpr 修复，但让我们坚持使用模板化解决方案。递归需要一个特例来结束，HCF(x,y)=1是共同质数的特例。

template <int x, int y> 
struct s<x,y,1> { enum e = 1 };

也就是说，你真的应该使用 Euclid's algorithm因为这种蛮力搜索不适用于像 s<300,300,300> 这样简单的东西.