From: "marcandre (Marc-Andre Lafortune)" <ruby-core@...>
Date: 2013-01-24T04:38:54+09:00
Subject: [ruby-core:51608] [ruby-trunk - Bug #7724] 6 bugs with Range#bsearch over floats


Issue #7724 has been updated by marcandre (Marc-Andre Lafortune).


mame (Yusuke Endoh) wrote:
> Thanks Marc-Andre!
> 
> But I'm very sorry that I'll have no enough time to pursue this issues.
> Could you please create a patch for C implementation?

Sure, I'll do it.

> Notice that the current implementation does NOT assume that the internal
> representation of double is IEEE 754.  Please do not depend on it but
> use C's constants about double, such as FLT_RADIX and DBL_MANT_DIG.

Actually, I don't think there is need to know how many bits are used for the mantissa vs exponent; I only need to know that double is represented with exponent bits then by mantissa bits. Apart from VAX (which had strange byte ordering, but we don't support), I believe this to be true.

So floatings can be seen as [exp, mantissa], thus have the same ordering as the the corresponding integers (forgetting about the sign). I.e. (double)(++(int64_t)a_float) is the smallest float strictly greater than a_float (assuming 0 <= a_float < infinity)

Do we have a list of non IEEE architectures we're hoping to support? Are there systems where sizeof(double) != sizeof(int_64_t)?

----------------------------------------
Bug #7724: 6 bugs with Range#bsearch over floats
https://bugs.ruby-lang.org/issues/7724#change-35563

Author: marcandre (Marc-Andre Lafortune)
Status: Assigned
Priority: Normal
Assignee: marcandre (Marc-Andre Lafortune)
Category: core
Target version: 2.0.0
ruby -v: r38825


Take the following code, with from, to and search all Integer or all Float:

  (from...to).bsearch{|f| f >= search}

I expected it to:
0) never yield and return nil if range is empty, i.e. from >= to ("trivial test")
1) never yield more than 65 times for floats
   or Math.log(to-from, 2)+1 for Integer ("log test")
2) return search if from <= search < to, nil otherwise ("coverage test")
3) never yield the same `f` ("uniqueness test")
4) if range is exclusive, never yield `to` nor return `to`; if range is inclusive and block returns false always yield `to` ("end of range test")
5) never yield a number < from or > to ("out of range test")

These conditions are all respected for Integers but all can be broken for Floats
Test 0, 1, 3, 4 & 5 fail even for small ordinary float values, while test 2 requires some larger floats, say 1e100 to fail.
For example bsearch can yield over 2000 times (instead of at most 65).


These tests and a correct Ruby implementation of bsearch can be found here: https://github.com/marcandre/backports/compare/marcandre:master...marcandre:bsearch
My implementation also passes the MRI tests.


-- 
http://bugs.ruby-lang.org/