Bug #7724

6 bugs with Range#bsearch over floats

Added by Marc-Andre Lafortune over 2 years ago. Updated about 2 years ago.

[ruby-core:51563]
Status:Closed
Priority:Normal
Assignee:Marc-Andre Lafortune
ruby -v:r38825 Backport:

Description

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.

Associated revisions

Revision 38978
Added by Marc-Andre Lafortune about 2 years ago

  • range.c: Fix Range#bsearch for floats [Bug #7724]

Revision 38978
Added by Marc-Andre Lafortune about 2 years ago

  • range.c: Fix Range#bsearch for floats [Bug #7724]

History

#1 Updated by Yui NARUSE over 2 years ago

  • Status changed from Open to Assigned
  • Assignee set to Yusuke Endoh

#2 Updated by Yusuke Endoh over 2 years ago

  • Assignee changed from Yusuke Endoh to 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

#3 Updated by Marc-Andre Lafortune over 2 years ago

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)?

#4 Updated by Marc-Andre Lafortune about 2 years ago

  • Status changed from Assigned to Closed
  • % Done changed from 0 to 100

This issue was solved with changeset r38978.
Marc-Andre, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.


  • range.c: Fix Range#bsearch for floats [Bug #7724]

Also available in: Atom PDF