<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">2015-02-14 2:20 GMT+01:00  <span dir="ltr">&lt;<a href="mailto:commits@source.squeak.org" target="_blank">commits@source.squeak.org</a>&gt;</span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Nicolas Cellier uploaded a new version of Kernel to project The Inbox:<br>
<a href="http://source.squeak.org/inbox/Kernel-nice.903.mcz" target="_blank">http://source.squeak.org/inbox/Kernel-nice.903.mcz</a><br>
<br>
==================== Summary ====================<br>
<br>
Name: Kernel-nice.903<br>
Author: nice<br>
Time: 14 February 2015, 2:19:44.184 am<br>
UUID: d4f06790-d47b-4cb0-b9ff-9e0ff7dea9fc<br>
Ancestors: Kernel-nice.902<br>
<br>
Introduce two new alternatives to integer division: #ratio: and #residue: are like #quo: and #rem: except that they round the quotient to nearest integer (tie to even) instead of truncating (note that // and \\ floor the quotient...).<br>
<br>
The second thing that they do differently is that they compute the exact ratio and exact residue when given a pair of Float.<br>
<br>
The third thing that they do differently is that they first coerce a pair of numbers to the highest generality before attempting any operation.<br>
<br>
=============== Diff against Kernel-nice.902 ===============<br>
<br></blockquote><div><br>Hi folks,<br>I&#39;ve 
already bent Squeak/Pharo handling of Float a bit, and I&#39;d like to 
increase further Smalltalk dialects compliance to language independent 
arithmetic standard (ISO/IEC 10967).<br>





<br><div>The subject of the day is state of the art quotient and remainder operations for Floats.<br></div><div><div>I
 noticed that the libm function fmod which computes the remainder of 
division of two floats (quotient being the truncated fraction) is and 
should be exact.<br>



</div><div>Our equivalent Float version of #rem: is not, and I had the feeling that it ain&#39;t good.<br>

</div></div>So I wrote a pair of methods #fquo: and #fmod: that 
evaluates the (truncated) quotient (quo:) and remainder (rem:) of 2 
floats exactly.<div><br></div>Then I plugged these functions to implementors of quo: and rem:.<br>

<div>They are not only exact, they also support extreme Floats without overflow, like<br>(Float fmax quo: Float fmin*5).<br>(Float fmax rem: Float fmin*5).<br></div><div>



<br></div>We will let // and \\  apart for the moment - see below for the reason.<br>

<br>Once plugged, some results might unfortunately look surprising like:<br><br>(1 to: 100) count: [:i | ((i/100.0) fquo: 0.01) ~= i].<br>-&gt; 58<br>(1 to: 100) count: [:i | ((i/100.0) fmod: 0.01) ~= 0].<br>-&gt; 93<br><br><div>The seven exact multiple are of course (0 to: 6) collect:[:i | 0.01 timesTwoPower: i]<br></div><div>The others just tell the awful truth about floating point...<br><br></div>



While with the old implementation was a little less surprising:<br><br>(1 to: 100) count: [:i | ((i/100.0) / 0.01) truncated ~= i].<br>-&gt; 6<br>(1 to: 100) count: [:i | (((i/100.0) / 0.01) truncated * 0.01 - (i/100.0)) ~= 0].<br>




-&gt; 13<br>
<br>Then I realized that language independent arithmetic standard 
and also older floating point standard (IEEE 754), do rather define 
quotient and remainder (ratio and residue) in term of rounded rather 
than truncated quotient.<br>





<br><div>So I implemented fratio: and fresidue: as prescribed by the standard (with an unbiased roundedTieToEven).<br></div>And these two operations better fit our expectations, at least for the ratio:<br><br>(1 to: 100) count: [:i | ((i/100.0) fratio: 0.01) ~= i].<br>





-&gt; 0<br><br>The residues are exact allways small:<br><br>(1 to: 100) count: [:i |<br>    | a b fa fb ea eb |<br>    a := 1/100. fa := a asFloat. ea := a - fa asFraction. &quot;exact, float, and error&quot;<br>    b := i*a. fb := b asFloat.. eb := b - fb asFraction.<br>



    [eb &lt;= (0.5*fb ulp) and: [ea &lt;= (0.5*fa ulp)]] assert.<br>    (fb fresidue: fa) abs &gt; (ea*i-eb) abs].<br>-&gt; 0<br><br>The naive implementation works well too for the ratio:<br>



<br>(1 to: 100) count: [:i | ((i/100.0) / 0.01) rounded ~= i].<br>-&gt; 0<br><br>but of course with inexact residue:<br><br>(1 to: 100) count: [:i |<br>    | a b fa fb ea eb |<br>    a := 1/100. fa := a asFloat. ea := a - fa asFraction. &quot;exact, float, and error&quot;<br>



    b := i*a. fb := b asFloat.. eb := b - fb asFraction.<br>    [eb &lt;= (0.5*fb ulp) and: [ea &lt;= (0.5*fa ulp)]] assert.<br>    (fb - ((fb/fa) rounded*fb)) abs &gt; (ea*i-eb) abs].<br>-&gt; 99<br><br>Rounded quotient is exactly what we want for Float. The rounding problems still exist, but they are rejected near exact tie.<br>



But that means implementing yet another quo/rem message (#ratio: 
#residue: using terms of the standard) while we already have two 
pairs...<br>
<br>Do you think that such extension ratio/residue is valuable?<br>Do you think that modification of quo:/rem: is bearable?<br><br>The
 alternative would be to provide an external package (eventually with 
overrides) to turn Squeak/Pharo behavior into standard, but I don&#39;t like
 the idea that the kernel does not respect the standards by default...<br>





<br><div>------------------------------------------------<br><br></div><div>About // and \\:<br></div><div>The problem with \\ is that it can&#39;t always be exact when expressed as Float.<br></div><div>(b \\ a) can be near a when b abs &lt; a abs, a*b &lt; 0.<br>



So when b is of very small magnitude relative to a, remainder requires many bits.<br>For example Float fmin negated asFraction \\ 1.0 asFraction
would exactly be (1.0 asFraction - Float fmin asFraction) and thus 
require a significand of 1074 bits.<br>We don&#39;t have ArbitraryPrecisionFloat 
in trunk, and Fraction is overkill...<br>We can&#39;t either let the exact 
remainder be rounded to nearest Float because it will be equal to the divider  (it should be less than in magnitude).<br></div><div>So, there is no easy solution for this case in Float...<br></div>But note that current naive implementation suffers exactly from same problem and would answer 1.0 (the divider). <br><br>------------------------------------------------<br><br></div><div>I&#39;ve also asked peers for a good reason to implement an exact #rem: but knowledgeable peers are unreachable yet ;)<br><br><a href="http://cs.stackexchange.com/questions/24362/why-does-floating-point-modulus-exactness-matters">http://cs.stackexchange.com/questions/24362/why-does-floating-point-modulus-exactness-matters</a><br><br></div><div>So maybe it&#39;s time to push this stuff<br></div><div><br></div><br></div></div></div>