Safe Haskell | None |
---|---|

Language | Haskell2010 |

Author : Levent Erkok License : BSD3 Maintainer: erkokl@gmail.com Stability : experimental

The classic "binary-searches are broken" example: http://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

## Synopsis

- midPointBroken :: SInt32 -> SInt32 -> SInt32
- midPointFixed :: SInt32 -> SInt32 -> SInt32
- midPointAlternative :: SInt32 -> SInt32 -> SInt32
- checkArithOverflow :: (SInt32 -> SInt32 -> SInt32) -> IO ()
- checkCorrectMidValue :: (SInt32 -> SInt32 -> SInt32) -> IO ThmResult

# Documentation

midPointBroken :: SInt32 -> SInt32 -> SInt32 Source #

Model the mid-point computation of the binary search, which is broken due to arithmetic overflow. Note how we use the overflow checking variants of the arithmetic operators. We have:

`>>>`

Documentation/SBV/Examples/BitPrecise/BrokenSearch.hs:33:28:+!: SInt32 addition overflows: Violated. Model: low = 1073741824 :: Int32 high = 1073742336 :: Int32`checkArithOverflow midPointBroken`

Indeed:

`>>>`

-1073741568`(1073741824 + 1073742336) `div` (2::Int32)`

giving us a negative mid-point value!

midPointFixed :: SInt32 -> SInt32 -> SInt32 Source #

The correct version of how to compute the mid-point. As expected, this version doesn't have any underflow or overflow issues:

`>>>`

No violations detected.`checkArithOverflow midPointFixed`

As expected, the value is computed correctly too:

`>>>`

Q.E.D.`checkCorrectMidValue midPointFixed`

midPointAlternative :: SInt32 -> SInt32 -> SInt32 Source #

Show that the variant suggested by the blog post is good as well:

mid = ((unsigned int)low + (unsigned int)high) >> 1;

In this case the overflow is eliminated by doing the computation at a wider range:

`>>>`

No violations detected.`checkArithOverflow midPointAlternative`

And the value computed is indeed correct:

`>>>`

Q.E.D.`checkCorrectMidValue midPointAlternative`