如何在Scheme中实现模运算和余数？

Question

我正在阅读R5RS规范，它显示了这个：

(modulo 13 4)                   ===>  1
(remainder 13 4)                ===>  1

(modulo -13 4)                  ===>  3
(remainder -13 4)               ===>  -1

(modulo 13 -4)                  ===>  -3
(remainder 13 -4)               ===>  1

(modulo -13 -4)                 ===>  -1
(remainder -13 -4)              ===>  -1

(remainder -13 -4.0)            ===>  -1.0  ; inexact

这是否正确？我认为取模和余数只在符号上有所不同。但是这里显示(modulo -13 4)应该返回3，在JavaScript中它返回1。

计算取模和余数的适当算法是什么？我需要这个来实现我的Scheme in JavaScript。

我在quora找到了这段代码。

function modulo(num1, num2) {
  if (num2 === 0 || isNaN(num1) || isNaN(num2)) {
    return NaN;
  }

  var isPositive = num1 >= 0;

  num1 = Math.abs(num1);
  num2 = Math.abs(num2);

  while (num1 >= num2) {
    num1 = num1 - num2;
  }

  return isPositive ? num1 : -num1;
}

但它的工作方式与R5RS规范不同，它返回-1用于modulo(-13, 4)。此外，我认为JavaScript的%与remainder相同。如何在JavaScript或Scheme中实现这两个函数？我的确切问题是：这两个函数的算法应该是什么样子的，或者计算它们的JavaScript代码应该是什么样子的？

- jcubic

---

问题是我不知道应该如何实现这个，我只看到了规范中的示例，没有任何解释。R5RS 第6.2.5节 - jcubic

我在上面链接的Python文章中给了你一些提示，但我猜你还得自己解决。或者，你可以查看已经提供的许多Scheme解释器之一的源代码，看看他们是如何做到的。 - Óscar López

@ÓscarLópez，我曾经看过guile，但没有帮助。我尝试了检查biwacheme，但它的TODO列表中有余数和模运算。无论如何，感谢您的帮助。 - jcubic

你自己的链接提供了一个解释，“在”例子之上。我已经编辑了你的问题，添加了更精确的链接，请查看。 :) - Will Ness

我不知道Java和Javascript有什么区别。 :) C代码有用吗？Scheme呢？ - Will Ness

Answer 1

这是Chibi的实现：

• remainder: https://github.com/ashinn/chibi-scheme/blob/12636f4b19e732bcf257ab50808a93c323823099/bignum.c#L1784

• modulo: https://github.com/ashinn/chibi-scheme/blob/12636f4b19e732bcf257ab50808a93c323823099/lib/init-7.scm#L1403

作者是R7RS的作者之一。

- ceving

---

在编程方面，Chibi中的Scheme代码会很有帮助。我一直在寻找源代码，已经检查了Kawa和Guile，但大部分代码都是用主机语言编写的，难以阅读。 - jcubic

Answer 2

以下是我在Urlang中实现函数的方法：

    (define/export/arity (quotient n m) 
      (Math.floor (/ n m)))

    (define/export/arity (remainder n m)
      (% n m))

    (define/export/arity (quotient/remainder n m)
      (values (quotient n m) (remainder n m)))

    (define/export/arity (modulo n m)
      (var [who (λ() (string->symbol "modulo"))])
      (unless (and (number? n) (not (infinite? n))) 
         (raise-argument-error (who) "integer?" 1 n m))
      (unless (and (number? m) (not (infinite? m))) 
         (raise-argument-error (who) "integer?" 2 n m))
      (% (+ (% n m) m) m))

这里的Math.floor、%和+是标准的JavaScript函数/运算符。

对于好奇的人，这是生成的JavaScript代码：

function remainder(n,m){if(!((arguments.length===2)===false))VOID;else (raise_arity_error_m((string__gsymbol("remainder")),2,arguments));;return (n%m);};
function quotient_qremainder(n,m){if(!((arguments.length===2)===false))VOID;else (raise_arity_error_m((string__gsymbol("quotient/remainder")),2,arguments));;return (values((quotient(n,m)),(remainder(n,m))));};
function modulo(n,m){if(!((arguments.length===2)===false))VOID;else (raise_arity_error_m((string__gsymbol("modulo")),2,arguments));;var who=(function(){return (string__gsymbol("modulo"));});(((!((number_p(n))&&(!(infinite_p(n)))))===false)?undefined:((function(){return (raise_argument_error((who()),"integer?",1,n,m));})()));(((!((number_p(m))&&(!(infinite_p(m)))))===false)?undefined:((function(){return (raise_argument_error((who()),"integer?",2,n,m));})()));return (((n%m)+m)%m);};

更新

这里有一些上下文。代码实现了Scheme运行时的余数和模运算。该运行时是在Urlang中实现的（它是带有s表达式语法的JavaScript）。

从输出的JavaScript中，您可以看到：

• Scheme的remainder被实现为n％m。
• Scheme的modulo被实现为((n％m)+m)％m

这假定Scheme数字表示为JavaScript数字（即没有大整数）。

- soegaard

---

Urlang不管是什么语言都没什么用。在每种语言中，代码中的%运算符的作用都不同，在JavaScript中，%不是余数，因此我无法使用这个实现。我可以使用任何不使用%的语言，虽然有JS代码，但它已被混淆。 - jcubic

@jcubic 我已经添加了一些上下文。 - soegaard

我认为quotient不正确，如果n为负数，则需要使用ceil。 - jcubic

你的“reminder”比Scheme中的实现要短得多，我以为JS的“%”不是Scheme的“reminder”，但似乎它确实是，只有“modulo”不同。谢谢。 - jcubic

一开始我很困惑 - 我习惯了C语言中%表示取模。 - soegaard

我知道在JavaScript中%不是模运算符，我只是尝试将其用作方案提醒器，但我认为它实际上并不是方案提醒器。我在我的答案中针对这个“list”进行了测试，但我没有仔细检查%的余数是否正确地工作。 - jcubic

Answer 3

如果有人感兴趣，我已在Reddit上提出了相同的问题（并附上了此问题的链接），并得到了精确的方案代码答案：

https://www.reddit.com/r/scheme/comments/fpt1b8/help_with_modulo_and_reminder_in_r5rs/

(define (modulo a b)
  (- a (* b (floor (/ a b)))))

(define (remainder a b)
  (- a (* b (truncate (/ a b)))))

;; as @soegaard show reminder is just JavaScript % so this can be
;; if % is proper function
(define (remainder a b)
  (% a b))

它与R5RS中的示例相同：

它的工作方式相同：

(list
  (= (modulo 13 4) 1)
  (= (remainder 13 4) 1)      ;; ===>  1

  (= (modulo -13 4) 3)        ;; ===>  3
  (= (remainder -13 4) -1)    ;; ===>  -1

  (= (modulo 13 -4) -3)       ;; ===>  -3
  (= (remainder 13 -4) 1)     ;; ===>  1

  (= (modulo -13 -4) -1)      ;; ===>  -1
  (= (remainder -13 -4) -1)   ;; ===>  -1

  (= (remainder -13 -4.0) -1.0)) ;; ===>  -1.0  ; inexact

"

floor 是 Math.floor，而 truncate 是：

"

var truncate = (function() {
    if (Math.trunc) {
        return Math.trunc;
    } else {
        return function(x) {
            if (x === 0) {
                return 0;
            } else if (x < 0) {
                return Math.ceil(x);
            } else {
                return Math.floor(x);
            }
        };
    }
})();

- jcubic

Answer 4

您可能会对Taylor Campbell的SRFI 141：整数除法感兴趣。它是Scheme的一个拟议扩展，提供了“相当完整的整数除法和余数运算符集合”。

- Arthur A. Gleckler

---

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅有链接的答案可能会失效。-【来自审查】 - L8R

抱歉，我是一个 Stack Overflow 新手。我本意是提供补充信息而不是答案。如果我把它作为评论放在原问题下面会更好吗？ - Arthur A. Gleckler