Why is your bisection search wrong

[•Cosmin]

http://www.infoarena.ro/blog/your-bisection-search-is-wrong

[•DaeMoohn]

The relative error concept looks interesting

[•MciprianM]

Hello!

I have a few questions and observations.

First of all, when I first tried to solve this problem, instead of using the simple thing that you did for applying the algorithm to negative numbers, I tried to complicate things by using (-MAX, MAX) range. That was not such a good idea, but it led me to finding that lo + (hi - lo) might overflow too. Namely, if lo is low enough(and negative too) and hi is hi enough, then hi - lo will turn into an large number that could overflow. So hi - lo is good enough, if hi and lo are greater than or equal to 0. In general, always check the range of values that can occur as inputs and check whether the outputs and the intermediate values fit the type.

Second, could you please specify how do we compute that magic constant(120) that you used for the number of iterations? Are there any risks, if that number is too high (besides TLE, smth like roundoff errors)? As an example, my python interpreter shows 999999999999.3113 as a result for cubicRoot(1e36); the exact result would be 1e12. The difference is greater than 0.1

Third, who considered float is a good enough default type for real numbers?

How does this algorithm perform for really small, really large and really close too zero numbers(close to the limits of what the type can hold)?

Thanks!

L.E.: Just noticed the "Tomek" addition to the text. My C++ compiler says that 3.4028235e+038 is the max value for float(numeric_limits<float>::max()).

[•Cosmin]

As you can see Tomek already pointed out that for large numbers my number of iterations is bad and you need about 1100 steps instead of 120. Will add a paragraph about that tomorrow. It's 2am here . I think python doesn't have floats it uses doubles.

[•MciprianM]

Sorry!

I didn't see that comment when I started writing my comment. Also, there are also other questions in my comment that I would like you to address besides that tomorrow.

Thank you and have a good night.

L.E.: It looks like in python it is called float(as in floating type), but it has the value range of C++'s double: [2.2250738585072014e-308, 1.7976931348623157e+308]. So it might be that in python there's, in fact, only "double".

[•Cosmin]

I think your only question left unanswered is the one about the behavior for really small numbers and really large numbers. I see that the code returns reasonable results for c = 1e+305 and c = 1e-305 and the results are equal to those of pow(c, 1.0/3).

[•raduberinde]

When you are interested in guaranteeing relative error, doesn't it make more sense to use the geometric mean as the midpoint, i.e. sqrt(low*high) ?   (equivalent to "regular" binary search of ln(x))

[•Cosmin]

@Radu yes, good point, binary searching on the logarithm works. Also it converges faster, especially on large numbers. In fact it takes 64 steps since now at each step you find a bit of the answer. But it's a bit of a cheat since I mentioned using only +,-,*,/

[•rgrig]

You made me implement this :p
I did it quickly, so very likely I have bugs.

Python3:

Cod:

from math import frexp

def cube(y):
  return y * y * y

def cr_subunit(x):
  assert (0 <= x and x <= 1)
  delta = 1
  y = 0
  while cube(y) != cube(y + delta):
    delta /= 2
    if cube(y + delta) < x:
      y += delta
  return y

cr_two = 1.2599210498948731647672106072782283505702

def cr_powtwo_nn(e):
  if e == 0:
    return 1
  x = cr_powtwo_nn(e // 2)
  x = x * x
  if e % 2 == 1:
    x *= cr_two
  return x

def cr_powtwo(e):
  if e >= 0:
    return cr_powtwo_nn(e)
  else:
    return 1/cr_powtwo_nn(-e)

def cr_pos(x):
  m, e = frexp(x)
  return cr_subunit(m) * cr_powtwo(e)

def cr(x):
  if x > 0:
    return cr_pos(x)
  else:
    return -cr_pos(-x)

[•Cosmin]

haha, neat. good job. looks reasonable to me.

[•madno]

Just a small typo, I think you meant:

"while abs(c - lo * lo * lo) >= 1e-3:"