d3.range produces extra array element for fractional strides

[andreasplesch]

The d3.range function produces an extra element as the last in the array for some fractional strides. For example:

    > d3.range(0,1,1/18).length
    < 19

is unexpected while

   > d3.range(0,1,1/17).length
   < 17

is expected.
This is perhaps due to floating point precision epsilons not being taken into account, or loss of precision at some type conversion.

[andreasplesch]

I tried to see what happens in array/range.js if step is 1/18. The k upscale factor will be 1e17.
The upscaled step size will be 5555555555555555 due to floating point precision loss and truncation. Therefore

    > 18 * 5555555555555555
    < 99999999999999980

which is smaller than the upscale stop value of 1e17, and leads to the extra element.

Not sure how to go about this issue properly but here are some thoughts:
Since the upscaled step size is never too large, a fix may be to adjust stop in line 16 with something like:

stop = (stop - 1e-16) * k;

although this may need to be reversed for negative steps.
And the adjustment would need to scale with stop, so probably more like stop-stop*1e-16. It looks like it is time to look up how to do floating point precision management.
For gory details (too much for me):
http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

[andreasplesch]

As a workaround without fixing the range function what works in my case is:

var eps = 1e-16
d3.range(0,1-eps,1/18).length
18

I empirically tested this workaround by

d3.range(1,10000).forEach( function(d) {
  if (d3.range(0, 1-eps, 1/d).length !== d) {console.log(d) ;}})

which does not find any unexpected range for eps = 1e-16 but does find many for eps = 1e-17;
This is equivalent to the suggestion above though it is just for the [0,1[ domain.

I also tried other domains as in:

var rmax = 100;
d3.range(1,1000).forEach( function(d) {
  if (d3.range(0, rmax*(1-eps), rmax/d).length !== d) {console.log(d) ;}})
791
1582
3164

which does find problematic fractions (rmax=111 is worse) so above is not perfect (but much better than without the 1-eps adjustment). However, upping the eps to 1e-15 and going through domains:

d3.range(1,64).forEach(function(m){rmax=Math.pow(2,m);
  d3.range(1,1000).forEach( function(d) {rmax=Math.pow(2,m);
  if (d3.range(0, rmax*(1-eps), rmax/d).length !== d) {console.log(d) ;}})})

does not find a problem.

[andreasplesch]

Ok. I noticed that the API documentation actually mentions that the result is less predictable with fractional step sizes. Now, I know what that means and the behaviour can be considered somewhat documented with this issue. Perhaps there is no good fix ?

[andreasplesch]

d3/d3-arrays/src/range.js approach works much better. So I think this issue will become resolved in the next version of d3. Therefore the issue is closed.

[andreasplesch]

Hm, while the new range.js works better, a little bit deeper empirical testing finds the same issue there. See d3/d3-array#5