From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id AE9247F198 for ; Wed, 27 Jan 2016 01:34:50 +0100 (CET) IronPort-PHdr: 9a23:8hWq1BWX1a42blcbdFXkzlmGKWnV8LGtZVwlr6E/grcLSJyIuqrYZheEt8tkgFKBZ4jH8fUM07OQ6PC/HzRZqsza+Fk5M7VyFDY9wf0MmAIhBMPXQWbaF9XNKxIAIcJZSVV+9Gu6O0UGUOz3ZlnVv2HgpWVKQka3CwN5K6zPF5LIiIzvjqbpq8KVO1wD3mH1SIgxBSv1hD2ZjtMRj4pmJ/R54TryiVwMRd5rw3h1L0mYhRf265T41pdi9yNNp6BprJYYAu2pN5g/GLdRCTBjN2Eu+OXqswPCRE2B/CgySGITxwJFAg+NuAn3X5C3uCzgqupw3C2XFcLzRLEwHz+l6vE4G1fTlC4bOmthoynsgctqgfcDrQ== Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=peio.borthelle@gmail.com; spf=Pass smtp.mailfrom=peio.borthelle@gmail.com; spf=None smtp.helo=postmaster@mail-wm0-f47.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of peio.borthelle@gmail.com) identity=pra; client-ip=74.125.82.47; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="peio.borthelle@gmail.com"; x-sender="peio.borthelle@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of peio.borthelle@gmail.com designates 74.125.82.47 as permitted sender) identity=mailfrom; client-ip=74.125.82.47; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="peio.borthelle@gmail.com"; x-sender="peio.borthelle@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-wm0-f47.google.com) identity=helo; client-ip=74.125.82.47; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="peio.borthelle@gmail.com"; x-sender="postmaster@mail-wm0-f47.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0B6AQAWEKhWlC9SfUpegw+BaohXoDkEA4cKjEGHXTwQAQEBAQEBAQEQAQEBAQcLCwkfMIItgi0RBBkBGx4DEhAPAiYCJREBBQFXh2MBAxIBn0iCB4ExPjGLNIFpgleFdgoZJw1Rg0sBCxgBBQoEbY86gjWBOgWWeYF1AYthiRmFYY0FMIENN4I9gVhpiEQBAQE X-IPAS-Result: A0B6AQAWEKhWlC9SfUpegw+BaohXoDkEA4cKjEGHXTwQAQEBAQEBAQEQAQEBAQcLCwkfMIItgi0RBBkBGx4DEhAPAiYCJREBBQFXh2MBAxIBn0iCB4ExPjGLNIFpgleFdgoZJw1Rg0sBCxgBBQoEbY86gjWBOgWWeYF1AYthiRmFYY0FMIENN4I9gVhpiEQBAQE X-IronPort-AV: E=Sophos;i="5.22,352,1449529200"; d="scan'208";a="161795458" Received: from mail-wm0-f47.google.com ([74.125.82.47]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 27 Jan 2016 01:34:49 +0100 Received: by mail-wm0-f47.google.com with SMTP id r129so126203012wmr.0 for ; Tue, 26 Jan 2016 16:34:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:subject:from:to:date:content-type:mime-version :content-transfer-encoding; bh=jugKd80DQqxSlt4OByJw7vsE6k/CpCrBvmkIGS5QH90=; b=mdTHCpKGFbyPieGeeQ2tZNpfYZ69gv52AIniyLodupr7Nhab0bjM5uq/CAdH3cDDcF bS2r4izrIfbtSnisPgkTTXVXk0Ne36zoF6nPsSagbvOXkO1A8wWmWZ3RRazialDcuhB4 s0JNSAvQwO1i13W0a+vaocvvBBJSCxgyH2Wx0fqQjR4YfPD7AvxgIoPPxZvK04HwEyKj dZg0YrKAPBhdXhs3VarJCc+ahP3/NG9GbJzx7ePwkClld6ODJZIQG/RGZBGgrnp7f5fK yM6/rxnPBMAaZ1UGE5Gm3SpaM6USlKkdAPNktIoGk4t8EJk02XBo/wdPiu4+7VBCIY+z 2seg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:subject:from:to:date:content-type :mime-version:content-transfer-encoding; bh=jugKd80DQqxSlt4OByJw7vsE6k/CpCrBvmkIGS5QH90=; b=adEP0eXGFj2PP8gVaOVnJJ1R8rUunGBq/J48GygmMsMs07rtVLWhjaRx42/R0ZzQQi Lb+mY9oi42LPalNRy0zklYwbWS4S0S6UuJiVYLqvycWntbr5L2DnJZ8Eok6C1PmHdy+j ephLc5xwWBNorTUdC47ei5u8WwW1pjAvcfcOP0+4mvI1yx39vF9eY9xY0NA9Wpv7lzkN fN2fTOkZtu2FdQTXL4qrtKt0zQ3RbHXp9PpWp09j00mq+pL8RUAJD9r4sFv6YP+Rr1aj IhHiHvT4TPLU47Haa46zQ8NqO8wDjSzd0mjvUytBU++CKu/xpMi5tscaqGIB0WtL6tz+ 5JDg== X-Gm-Message-State: AG10YOS9/wvbYzYCx1XM51pKkY/XXuyDMobAND7U8LHmay374/cBHgF0WGjtlRozwO96/Q== X-Received: by 10.28.72.68 with SMTP id v65mr28358167wma.41.1453854889619; Tue, 26 Jan 2016 16:34:49 -0800 (PST) Received: from anung-un-rama.localdomain ([2a01:e35:2eb2:3960:6e40:8ff:fe8a:b944]) by smtp.googlemail.com with ESMTPSA id m143sm5059787wma.17.2016.01.26.16.34.48 for (version=TLSv1/SSLv3 cipher=OTHER); Tue, 26 Jan 2016 16:34:48 -0800 (PST) Message-ID: <1453854887.31205.2.camel@gmail.com> From: peio To: caml-list@inria.fr Date: Wed, 27 Jan 2016 01:34:47 +0100 Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.18.4 (3.18.4-1.fc23) Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [Caml-list] truncated division, remainder and arithmetics Good evening, while doing some modular arithmetic I discovered that OCaml uses the 'truncated division' convention for the `/` (quotient) operator. Actually this convention may seem innocent but it greatly affects the `mod` (remainder) operator: the sign of the result is the same as dividend. After some research I realized that lots of people (D.Knuth!) criticized this convention in favor of floored division (sign of remainder same as divisor) or euclidean division (remainder always positive). I know such a key component of the language isn't likely to be changed but I would like to get some of the rationals behind this decision. I can't think of any case in which the current behavior more natural but there are clearly situation giving weird results: I encountered one while multiplying big numbers modulo 2**62 (on 64-bit machine): as `max_int` is 2**62 - 1 the product could overflow and become negative. Consequently one can't just write `(a * b) mod m` to get the result of multiplication on the group Z/mZ if a and b are bigger than 2**31. The workaround I found was to redefine quotient and remainder to follow floored division convention: let rem a b = ((a mod b) + b) mod b let quo a b = (a - rem a b) / b Does anyone see a cleaner way to do it? I don't know anything about division algorithm, but is it actually easier/faster to implement the truncated division instead of the floored division? Is there any other reason I missed to choose truncated division? At last another thing that (slightly) bugs me: why don't `ceil` and `floor` have the type `float -> int`? Because the inherent definitions of these functions talks about integers, not floats (floor(x) is the biggest integer less than x). Indeed the `int_of_float (ceil x)` is a very common pattern (according to some very unscientific searching through github code search). Maybe even more subtle is that `truncate` has type `float -> int`. In my opinion the type `float -> float` would be more appropriate here because the truncation operation is about approximating a real number with a decimal (we already got `int_of_float` for rough converting). cheers, peio