用Prolog实现真正的尾递归modInverse()
用Prolog实现真正的尾递归modInverse()
提问于 2020-12-11 05:59:42
Rosetta代码为我提供了以下modinv/3的代码片段。它确实通过egcd/4计算扩展的GCD，然后从它派生modinv/3：
egcd(_, 0, 1, 0) :- !.
egcd(A, B, X, Y) :-
divmod(A, B, Q, R),
egcd(B, R, S, X),
Y is S - Q*X.
modinv(A, B, N) :-
egcd(A, B, X, Y),
A*X + B*Y =:= 1,
N is X mod B.查询示例：
?- modinv(42, 2017, N).
N = 1969.
?- modinv(42, 64, X).
false.这个解决方案有一个小问题。它不是尾递归的。即，( is )/2是egcd/4的最后调用，而不是egcd/4本身。
所以谓词可能会构建一个堆栈，一个可能包含很大很大数字的堆栈。如何实现更加尾部递归的解决方案呢？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-12-11 08:33:47
您提到的同一站点有其他适用于尾递归解决方案的算法。
这里我从C++部分翻译了一个(注意在原始的C++代码中缺少一个约束，它没有检查A的最后一个值)：
modinv(A, B, N):-
modinv(A, B, 1, 0, N1),
(N1 < 0 -> N is N1 + B ; N1 = N).
modinv(A, B, X, Y, N):-
(B=0 -> (A=1, N=X) ;
(
divmod(A, B, Q, R),
Exp is X - Y * Q,
modinv(B, R, Y, Exp, N)
)
).示例查询：
?- modinv(42, 2017, N).
N = 1969.
?- modinv(42, 64, X).
false.页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65242927
复制相关文章
相似问题
腾讯云开发者
