方案中模 m 的乘法逆 [英] multiplicative inverse of modulo m in scheme

问题描述

我已经编写了模 m 的乘法逆的代码.它适用于大多数初始情况，但不适用于某些情况.代码如下:

I've written the code for multiplicative inverse of modulo m. It works for most of the initial cases but not for some. The code is below:

(define (inverse x m)
    (let loop ((x (modulo x m)) (a 1))
      (cond ((zero? x) #f) ((= x 1) a)
            (else (let ((q (- (quotient m x))))
                    (loop (+ m (* q x)) (modulo (* q a) m)))))))

例如它给出了正确的值 (inverse 5 11) -> 9 (inverse 9 11) -> 5 (inverse 7 11 ) -> 8 (inverse 8 12) -> #f 但是当我给出 (inverse 512) 它产生 #f 而它应该是 5.你能看到错误在哪里吗?

For example it gives correct values for (inverse 5 11) -> 9 (inverse 9 11) -> 5 (inverse 7 11 ) - > 8 (inverse 8 12) -> #f but when i give (inverse 5 12) it produces #f while it should have been 5. Can you see where the bug is?

感谢您的帮助.

推荐答案

一定要那个算法吗?如果没有，试试这个，取自 wikibooks:

Does it have to be precisely that algorithm? if not, try this one, taken from wikibooks:

(define (egcd a b)
  (if (zero? a)
      (values b 0 1)
      (let-values (((g y x) (egcd (modulo b a) a)))
        (values g (- x (* (quotient b a) y)) y))))

(define (modinv a m)
  (let-values (((g x y) (egcd a m)))
    (if (not (= g 1))
        #f
        (modulo x m))))

它按预期工作:

(modinv 5 11) ; 9
(modinv 9 11) ; 5
(modinv 7 11) ; 8
(modinv 8 12) ; #f 
(modinv 5 12) ; 5

这篇关于方案中模 m 的乘法逆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！