Forum: Ruby-core [ruby-trunk - Bug #7724][Open] 6 bugs with Range#bsearch over floats

0e610136db92027148906c92d57fdb36?d=identicon&s=25 marcandre (Marc-Andre Lafortune) (Guest)
on 2013-01-22 10:49
(Received via mailing list)
Issue #7724 has been reported by marcandre (Marc-Andre Lafortune).

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

Author: marcandre (Marc-Andre Lafortune)
Status: Open
Priority: Normal
Assignee:
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/mar...
My implementation also passes the MRI tests.
9361878d459f1709feec780518946ee5?d=identicon&s=25 naruse (Yui NARUSE) (Guest)
on 2013-01-23 09:48
(Received via mailing list)
Issue #7724 has been updated by naruse (Yui NARUSE).

Status changed from Open to Assigned
Assignee set to mame (Yusuke Endoh)


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

Author: marcandre (Marc-Andre Lafortune)
Status: Assigned
Priority: Normal
Assignee: mame (Yusuke Endoh)
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/mar...
My implementation also passes the MRI tests.
F24ff61beb80aa5f13371aa22a35619c?d=identicon&s=25 mame (Yusuke Endoh) (Guest)
on 2013-01-23 10:43
(Received via mailing list)
Issue #7724 has been updated by mame (Yusuke Endoh).

Assignee changed from mame (Yusuke Endoh) to marcandre (Marc-Andre
Lafortune)

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?

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.

--
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Bug #7724: 6 bugs with Range#bsearch over floats
https://bugs.ruby-lang.org/issues/7724#change-35546

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/mar...
My implementation also passes the MRI tests.
0e610136db92027148906c92d57fdb36?d=identicon&s=25 marcandre (Marc-Andre Lafortune) (Guest)
on 2013-01-23 20:39
(Received via mailing list)
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/mar...
My implementation also passes the MRI tests.
This topic is locked and can not be replied to.