Project

General

Profile

Actions

Bug #7724

closed

6 bugs with Range#bsearch over floats

Added by marcandre (Marc-Andre Lafortune) about 11 years ago. Updated about 11 years ago.

Status:
Closed
Target version:
ruby -v:
r38825
Backport:
[ruby-core:51563]

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.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0