module Data.Random.Internal.Find where
findMax :: (Fractional a, Ord a) => (a -> Bool) -> a
findMax p = negate (findMin (p.negate))
findMaxFrom :: (Fractional a, Ord a) => a -> a -> (a -> Bool) -> a
findMaxFrom z 0 p = findMaxFrom z 1 p
findMaxFrom z step1 p = findMinFrom z (negate step1) p
findMin :: (Fractional a, Ord a) => (a -> Bool) -> a
findMin = findMinFrom 0 1
findMinFrom :: (Fractional a, Ord a) => a -> a -> (a -> Bool) -> a
findMinFrom z 0 p = findMinFrom z 1 p
findMinFrom z step1 p
| p z = descend (zstep1) z
| otherwise
= fixZero (ascend z (z+step1))
where
fixZero 0 = 0
fixZero z = z
ascend l x
| p x = bisect l x
| otherwise = ascend x $! 2*xz
descend x h
| p x = (descend $! 2*xz) x
| otherwise = bisect x h
bisect l h
| l >= h = h
| l >= mid || mid >= h
= if p mid then mid else h
| p mid = bisect l mid
| otherwise = bisect mid h
where
a >= b = not (a < b)
mid = (l+h)*0.5