module AERN2.BoxFun.Optimisation where

import qualified Prelude
import MixedTypesNumPrelude
import qualified Numeric.CollectErrors as CN
import AERN2.MP.Dyadic
import AERN2.MP.Ball
import AERN2.BoxFun.Box (Box)
import qualified AERN2.BoxFun.Box as Box
import AERN2.BoxFun.Type
import AERN2.Kleenean
import AERN2.Linear.Vector.Type as V
import AERN2.Linear.Matrix.Type
import AERN2.Linear.Matrix.Inverse

import qualified Data.List as List

import qualified AERN2.PQueue as Q

import AERN2.Util.Util

import Debug.Trace (trace)

globalMinimumGreaterThanN :: BoxFun -> Accuracy -> CN Rational -> Precision -> Bool
globalMinimumGreaterThanN :: BoxFun -> Accuracy -> CN Rational -> Precision -> Bool
globalMinimumGreaterThanN BoxFun
f Accuracy
ac CN Rational
n Precision
initialPrecision =
    String -> CN MPBall -> CN MPBall
forall a. String -> a -> a
trace (CN MPBall -> String
forall a. Show a => a -> String
show CN MPBall
x)
    CN MPBall
x CN MPBall -> CN Rational -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! CN Rational
n
    where x :: CN MPBall
x = BoxFun -> Accuracy -> Precision -> CN MPBall
globalMinimum BoxFun
f Accuracy
ac Precision
initialPrecision 

minFun :: BoxFun -> Accuracy -> Precision -> (Integer, CN MPBall)
minFun :: BoxFun -> Accuracy -> Precision -> (Integer, CN MPBall)
minFun BoxFun
f Accuracy
ac Precision
initialPrecision = 
    BoxFun -> Box -> Accuracy -> Precision -> (Integer, CN MPBall)
bestLocalMinimum BoxFun
f (BoxFun -> Box
domain BoxFun
f) Accuracy
ac Precision
initialPrecision

data SearchBox =
    SearchBox
    {
            SearchBox -> Box
extents :: Box
        ,   SearchBox -> CN MPBall
minimum :: CN MPBall 
    } deriving (Int -> SearchBox -> ShowS
[SearchBox] -> ShowS
SearchBox -> String
(Int -> SearchBox -> ShowS)
-> (SearchBox -> String)
-> ([SearchBox] -> ShowS)
-> Show SearchBox
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SearchBox] -> ShowS
$cshowList :: [SearchBox] -> ShowS
show :: SearchBox -> String
$cshow :: SearchBox -> String
showsPrec :: Int -> SearchBox -> ShowS
$cshowsPrec :: Int -> SearchBox -> ShowS
Show)

instance 
    HasPrecision SearchBox
    where
    getPrecision :: SearchBox -> Precision
getPrecision (SearchBox Box
b CN MPBall
_) = Box -> Precision
forall t. HasPrecision t => t -> Precision
getPrecision Box
b

instance 
    CanSetPrecision SearchBox
    where
    setPrecision :: Precision -> SearchBox -> SearchBox
setPrecision Precision
p (SearchBox Box
b CN MPBall
m) = Box -> CN MPBall -> SearchBox
SearchBox (Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision Precision
p Box
b) CN MPBall
m

instance Prelude.Eq SearchBox where
    == :: SearchBox -> SearchBox -> Bool
(==) (SearchBox Box
_ CN MPBall
_) (SearchBox Box
_ CN MPBall
_) =
        Bool
False -- TODO: safe?

instance Prelude.Ord SearchBox where
    <= :: SearchBox -> SearchBox -> Bool
(<=) (SearchBox Box
_ CN MPBall
min0) (SearchBox Box
_ CN MPBall
min1) = 
        case (CN MPBall -> Either NumErrors MPBall
forall es v. CanBeErrors es => CollectErrors es v -> Either es v
CN.toEither (CN MPBall -> Either NumErrors MPBall)
-> CN MPBall -> Either NumErrors MPBall
forall a b. (a -> b) -> a -> b
$ (CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
lowerBound CN MPBall
min0 :: CN MPBall), CN MPBall -> Either NumErrors MPBall
forall es v. CanBeErrors es => CollectErrors es v -> Either es v
CN.toEither (CN MPBall -> Either NumErrors MPBall)
-> CN MPBall -> Either NumErrors MPBall
forall a b. (a -> b) -> a -> b
$ (CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
lowerBound CN MPBall
min1 :: CN MPBall)) of
            (Left NumErrors
_, Left NumErrors
_) -> Bool
True
            (Left NumErrors
_, Right MPBall
_ ) -> Bool
True
            (Right MPBall
_ , Left NumErrors
_) -> Bool
False
            (Right MPBall
m0, Right MPBall
m1) -> 
                MPBall -> CentreType MPBall
forall t. IsBall t => t -> CentreType t
centre MPBall
m0 Dyadic -> Dyadic -> SubType Dyadic Dyadic
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- (ErrorBound -> Dyadic
forall t. CanBeDyadic t => t -> Dyadic
dyadic (ErrorBound -> Dyadic) -> ErrorBound -> Dyadic
forall a b. (a -> b) -> a -> b
$ MPBall -> ErrorBound
forall t. IsBall t => t -> ErrorBound
radius MPBall
m0) Dyadic -> Dyadic -> OrderCompareType Dyadic Dyadic
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
<= MPBall -> CentreType MPBall
forall t. IsBall t => t -> CentreType t
centre MPBall
m1 Dyadic -> Dyadic -> SubType Dyadic Dyadic
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- (ErrorBound -> Dyadic
forall t. CanBeDyadic t => t -> Dyadic
dyadic (ErrorBound -> Dyadic) -> ErrorBound -> Dyadic
forall a b. (a -> b) -> a -> b
$ MPBall -> ErrorBound
forall t. IsBall t => t -> ErrorBound
radius MPBall
m1) -- TODO: radius should be 0

---

globalMinimumWithCutoff :: BoxFun -> Accuracy -> CN MPBall -> Precision -> CN MPBall
globalMinimumWithCutoff :: BoxFun -> Accuracy -> CN MPBall -> Precision -> CN MPBall
globalMinimumWithCutoff BoxFun
f Accuracy
ac CN MPBall
cutoff Precision
initialPrecision =
    if BoxFun -> Integer
dimension BoxFun
f Integer -> Integer -> EqCompareType Integer Integer
forall a b. HasEqAsymmetric a b => a -> b -> EqCompareType a b
== Integer
1 then
        let
            fl :: CN MPBall
fl       = BoxFun -> Box -> CN MPBall
apply BoxFun
f ((CN MPBall -> CN MPBall) -> Box -> Box
forall a b. (a -> b) -> Vector a -> Vector b
V.map CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
lowerBound (Box -> Box) -> Box -> Box
forall a b. (a -> b) -> a -> b
$ BoxFun -> Box
domain BoxFun
f)
            fr :: CN MPBall
fr       = BoxFun -> Box -> CN MPBall
apply BoxFun
f ((CN MPBall -> CN MPBall) -> Box -> Box
forall a b. (a -> b) -> Vector a -> Vector b
V.map CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
upperBound (Box -> Box) -> Box -> Box
forall a b. (a -> b) -> a -> b
$ BoxFun -> Box
domain BoxFun
f)
            localMin :: CN MPBall
localMin = (Integer, CN MPBall) -> CN MPBall
forall a b. (a, b) -> b
snd ((Integer, CN MPBall) -> CN MPBall)
-> (Integer, CN MPBall) -> CN MPBall
forall a b. (a -> b) -> a -> b
$ BoxFun
-> Box
-> Accuracy
-> CN MPBall
-> Precision
-> (Integer, CN MPBall)
bestLocalMinimumWithCutoff BoxFun
f (BoxFun -> Box
domain BoxFun
f) Accuracy
ac CN MPBall
cutoff Precision
initialPrecision
        in
            CN MPBall -> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min CN MPBall
fl (CN MPBall -> MinMaxType (CN MPBall) (CN MPBall))
-> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall a b. (a -> b) -> a -> b
$ CN MPBall -> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min CN MPBall
localMin CN MPBall
fr
    else 
        let
            localMin :: CN MPBall
localMin       = (Integer, CN MPBall) -> CN MPBall
forall a b. (a, b) -> b
snd ((Integer, CN MPBall) -> CN MPBall)
-> (Integer, CN MPBall) -> CN MPBall
forall a b. (a -> b) -> a -> b
$ BoxFun
-> Box
-> Accuracy
-> CN MPBall
-> Precision
-> (Integer, CN MPBall)
bestLocalMinimumWithCutoff BoxFun
f (BoxFun -> Box
domain BoxFun
f) Accuracy
ac CN MPBall
cutoff Precision
initialPrecision
            boundaryFuns :: [BoxFun]
boundaryFuns   = BoxFun -> [BoxFun]
boundaryRestrictions BoxFun
f
            boundaryMinima :: [CN MPBall]
boundaryMinima = (BoxFun -> CN MPBall) -> [BoxFun] -> [CN MPBall]
forall a b. (a -> b) -> [a] -> [b]
List.map (\BoxFun
g -> BoxFun -> Accuracy -> CN MPBall -> Precision -> CN MPBall
globalMinimumWithCutoff BoxFun
g Accuracy
ac (CN MPBall -> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min CN MPBall
cutoff ((CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
upperBound CN MPBall
localMin :: CN MPBall))) Precision
initialPrecision) [BoxFun]
boundaryFuns
        in
            (CN MPBall -> CN MPBall -> CN MPBall)
-> CN MPBall -> [CN MPBall] -> CN MPBall
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' CN MPBall -> CN MPBall -> CN MPBall
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min CN MPBall
localMin [CN MPBall]
boundaryMinima


globalMinimum :: BoxFun -> Accuracy -> Precision -> CN MPBall
globalMinimum :: BoxFun -> Accuracy -> Precision -> CN MPBall
globalMinimum BoxFun
f Accuracy
ac Precision
initialPrecision =
    BoxFun -> Accuracy -> CN MPBall -> Precision -> CN MPBall
globalMinimumWithCutoff BoxFun
f Accuracy
ac (BoxFun -> Box -> CN MPBall
apply BoxFun
f (Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
boxp)) Precision
initialPrecision
    where
    boxp :: Box
boxp = Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision Precision
initialPrecision (BoxFun -> Box
domain BoxFun
f)

bestLocalMinimum :: BoxFun -> Box -> Accuracy -> Precision -> (Integer, CN MPBall)
bestLocalMinimum :: BoxFun -> Box -> Accuracy -> Precision -> (Integer, CN MPBall)
bestLocalMinimum BoxFun
f Box
box Accuracy
ac Precision
initialPrecision =
    BoxFun
-> Box
-> Accuracy
-> CN MPBall
-> Precision
-> (Integer, CN MPBall)
bestLocalMinimumWithCutoff BoxFun
f Box
box Accuracy
ac (BoxFun -> Box -> CN MPBall
apply BoxFun
f (Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
boxp)) Precision
initialPrecision
    where
    boxp :: Box
boxp = Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision Precision
initialPrecision Box
box

bestLocalMinimumWithCutoff :: BoxFun -> Box -> Accuracy -> CN MPBall -> Precision -> (Integer, CN MPBall)
bestLocalMinimumWithCutoff :: BoxFun
-> Box
-> Accuracy
-> CN MPBall
-> Precision
-> (Integer, CN MPBall)
bestLocalMinimumWithCutoff BoxFun
f Box
box Accuracy
ac CN MPBall
initialCutoff Precision
initialPrecision =
    PQueue SearchBox
-> CN MPBall -> Integer -> SearchBox -> (Integer, CN MPBall)
aux PQueue SearchBox
initialQueue CN MPBall
initialCutoff Integer
0 SearchBox
dummyBox
    where
    boxp :: Box
boxp             = Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision Precision
initialPrecision Box
box
    initialRange :: CN MPBall
initialRange     = BoxFun -> Box -> CN MPBall
apply BoxFun
f Box
boxp
    initialSearchBox :: SearchBox
initialSearchBox = Box -> CN MPBall -> SearchBox
SearchBox Box
boxp CN MPBall
initialRange
    initialQueue :: PQueue SearchBox
initialQueue     = SearchBox -> PQueue SearchBox
forall p. Ord p => p -> PQueue p
Q.singleton SearchBox
initialSearchBox
    dummyBox :: SearchBox
dummyBox         = Box -> CN MPBall -> SearchBox
SearchBox ([CN MPBall] -> Box
forall a. [a] -> Vector a
V.fromList [MPBall -> CN MPBall
forall v. v -> CN v
cn (MPBall -> CN MPBall) -> MPBall -> CN MPBall
forall a b. (a -> b) -> a -> b
$ Integer -> MPBall
forall t. CanBeMPBall t => t -> MPBall
mpBall (Integer -> MPBall) -> Integer -> MPBall
forall a b. (a -> b) -> a -> b
$ Integer
10Integer -> Integer -> PowType Integer Integer
forall t1 t2. CanPow t1 t2 => t1 -> t2 -> PowType t1 t2
^Integer
6]) CN MPBall
initialRange -- TODO: hack...

    aux :: PQueue SearchBox
-> CN MPBall -> Integer -> SearchBox -> (Integer, CN MPBall)
aux PQueue SearchBox
q CN MPBall
cutoff Integer
steps (SearchBox Box
_lastBox CN MPBall
rng) =  
        case PQueue SearchBox -> Maybe (SearchBox, PQueue SearchBox)
forall p. Ord p => PQueue p -> Maybe (p, PQueue p)
Q.minView PQueue SearchBox
q of
            Maybe (SearchBox, PQueue SearchBox)
Nothing -> String -> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a. String -> a -> a
trace (String
"no local minimum.") ((Integer, CN MPBall) -> (Integer, CN MPBall))
-> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a b. (a -> b) -> a -> b
$ (Integer
steps, CN MPBall
rng)
            Just (SearchBox
minBox, PQueue SearchBox
q') ->
                --trace ("value: "++ (show $ val)) $
                String -> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a. String -> a -> a
trace (String
"min box: "String -> ShowS
forall a. [a] -> [a] -> [a]
++ (SearchBox -> String
forall a. Show a => a -> String
show (SearchBox -> String) -> SearchBox -> String
forall a b. (a -> b) -> a -> b
$ SearchBox
minBox)) ((Integer, CN MPBall) -> (Integer, CN MPBall))
-> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a b. (a -> b) -> a -> b
$
                --trace ("box acc: "++ (show $ getAccuracy $ ext)) $
                --trace (show $ Box.width (extents minBox)) $
                --trace ("lower bound "++ (show $ Box.lowerBound $ val)) $
                --trace ("val' "++ (show $ val')) $
                String -> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a. String -> a -> a
trace (String
"cutoff: "String -> ShowS
forall a. [a] -> [a] -> [a]
++ (CN MPBall -> String
forall a. Show a => a -> String
show (CN MPBall -> String) -> CN MPBall -> String
forall a b. (a -> b) -> a -> b
$ CN MPBall
cutoff)) ((Integer, CN MPBall) -> (Integer, CN MPBall))
-> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a b. (a -> b) -> a -> b
$
                String -> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a. String -> a -> a
trace (String
"queue size: "String -> ShowS
forall a. [a] -> [a] -> [a]
++ (Int -> String
forall a. Show a => a -> String
show (Int -> String) -> Int -> String
forall a b. (a -> b) -> a -> b
$ PQueue SearchBox -> Int
forall p. PQueue p -> Int
Q.size PQueue SearchBox
q)) ((Integer, CN MPBall) -> (Integer, CN MPBall))
-> (Integer, CN MPBall) -> (Integer, CN MPBall)
forall a b. (a -> b) -> a -> b
$
                --trace ("cutoff == 0? "++(show $ cutoff == (mpBall 0))) $
                --trace ("precision: "++ (show $ precision)) $
                --trace ("dist to last "++ (show $ distToLast)) $
                --trace ("accuracy: "++ (show $ getAccuracy val')) $
                --trace ("precision centre: "++ (show $ fmap (getPrecision . centre) val)) $
                if CN MPBall -> Accuracy
forall a. HasAccuracy a => a -> Accuracy
getAccuracy CN MPBall
val' Accuracy -> Accuracy -> OrderCompareType Accuracy Accuracy
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
>= Accuracy
ac then
                    (Integer
steps, CN MPBall
val')
                else 
                    PQueue SearchBox
-> CN MPBall -> Integer -> SearchBox -> (Integer, CN MPBall)
aux PQueue SearchBox
q'' CN MPBall
newCutoff (Integer
steps Integer -> Integer -> AddType Integer Integer
forall t1 t2. CanAddAsymmetric t1 t2 => t1 -> t2 -> AddType t1 t2
+ Integer
1) (Box -> CN MPBall -> SearchBox
SearchBox Box
ext CN MPBall
rng)
                where
                val' :: CN MPBall
val' = CN MPBall -> CN MPBall -> CN MPBall
forall i.
(IsInterval i, CanMinMaxSameType (IntervalEndpoint i)) =>
i -> i -> i
fromEndpointsAsIntervals (CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
lowerBound CN MPBall
val) (CN MPBall
cutoff)
                SearchBox Box
ext CN MPBall
val = SearchBox
minBox

                (CN MPBall
newCutoff, [SearchBox]
newBoxes) = 
                    BoxFun
-> Accuracy -> CN MPBall -> SearchBox -> (CN MPBall, [SearchBox])
processBox BoxFun
f Accuracy
ac CN MPBall
cutoff SearchBox
minBox

                q'' :: PQueue SearchBox
q'' = (SearchBox -> PQueue SearchBox -> PQueue SearchBox)
-> PQueue SearchBox -> [SearchBox] -> PQueue SearchBox
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (SearchBox -> PQueue SearchBox -> PQueue SearchBox
forall p. Ord p => p -> PQueue p -> PQueue p
Q.insert) PQueue SearchBox
q' [SearchBox]
newBoxes

lipschitzContraction :: BoxFun -> Box -> SearchBox -> SearchBox
lipschitzContraction :: BoxFun -> Box -> SearchBox -> SearchBox
lipschitzContraction BoxFun
f Box
g (SearchBox Box
box CN MPBall
m) =
    {-trace("fa: "++(show $ getAccuracy (apply f box))) $
    trace("la: "++(show $ getAccuracy $ dotProduct)) $
    trace("ba: "++(show $ getAccuracy $ box ! int 0)) $-}
    {-if (radius $ (~!) $ newRange) < (radius $ (~!) $ m) then
        trace ("Lipschitz better.")
        SearchBox box m'
    else -}
    Box -> CN MPBall -> SearchBox
SearchBox Box
box CN MPBall
m'
    where
    boxCentre :: CentreType Box
boxCentre      = Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
box
    centreValue :: CN MPBall
centreValue    = BoxFun -> Box -> CN MPBall
apply BoxFun
f CentreType Box
Box
boxCentre
    difference :: SubType Box Box
difference     = Box
box Box -> Box -> SubType Box Box
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- CentreType Box
Box
boxCentre
    dotProduct :: MulType Box Box
dotProduct     = Box
g Box -> Box -> MulType Box Box
forall t1 t2. CanMulAsymmetric t1 t2 => t1 -> t2 -> MulType t1 t2
* SubType Box Box
Box
difference 
    newRange :: AddType (CN MPBall) (CN MPBall)
newRange       = CN MPBall
centreValue CN MPBall -> CN MPBall -> AddType (CN MPBall) (CN MPBall)
forall t1 t2. CanAddAsymmetric t1 t2 => t1 -> t2 -> AddType t1 t2
+ CN MPBall
MulType Box Box
dotProduct
    m' :: CN MPBall
m'             = CN MPBall -> CN MPBall -> CN MPBall
intersectCN CN MPBall
m CN MPBall
AddType (CN MPBall) (CN MPBall)
newRange

lipschitzRange :: BoxFun -> CN MPBall -> Box -> Box -> Box -> CN MPBall -> CN MPBall
lipschitzRange :: BoxFun -> CN MPBall -> Box -> Box -> Box -> CN MPBall -> CN MPBall
lipschitzRange BoxFun
_f CN MPBall
fc Box
c Box
g Box
box CN MPBall
m =
    CN MPBall
m'
    where
    difference :: SubType Box Box
difference     = Box
box Box -> Box -> SubType Box Box
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- Box
c
    normG :: CN MPBall
normG          = Box -> CN MPBall
Box.ellOneNorm Box
g
    normDiff :: CN MPBall
normDiff       = Box -> CN MPBall
Box.inftyNorm  SubType Box Box
Box
difference
    dotProduct :: MulType (CN MPBall) (CN MPBall)
dotProduct     = CN MPBall
normG CN MPBall -> CN MPBall -> MulType (CN MPBall) (CN MPBall)
forall t1 t2. CanMulAsymmetric t1 t2 => t1 -> t2 -> MulType t1 t2
* CN MPBall
normDiff
    newRange :: AddType (CN MPBall) (CN MPBall)
newRange       = CN MPBall
fc CN MPBall -> CN MPBall -> AddType (CN MPBall) (CN MPBall)
forall t1 t2. CanAddAsymmetric t1 t2 => t1 -> t2 -> AddType t1 t2
+ (CN MPBall -> CN MPBall -> CN MPBall
forall i.
(IsInterval i, CanMinMaxSameType (IntervalEndpoint i)) =>
i -> i -> i
fromEndpointsAsIntervals (-CN MPBall
MulType (CN MPBall) (CN MPBall)
dotProduct) CN MPBall
MulType (CN MPBall) (CN MPBall)
dotProduct :: CN MPBall)
    m' :: CN MPBall
m'             = CN MPBall -> CN MPBall -> CN MPBall
intersectCN CN MPBall
m CN MPBall
AddType (CN MPBall) (CN MPBall)
newRange

applyLipschitz :: BoxFun -> Box -> CN MPBall
applyLipschitz :: BoxFun -> Box -> CN MPBall
applyLipschitz BoxFun
f Box
box = 
    BoxFun -> CN MPBall -> Box -> Box -> Box -> CN MPBall -> CN MPBall
lipschitzRange BoxFun
f CN MPBall
fbc CentreType Box
Box
bc Box
dfb' Box
box CN MPBall
fb
    where
    (CN MPBall
fb, Box
dfb') = BoxFun -> Box -> (CN MPBall, Box)
valueGradient BoxFun
f Box
box
    bc :: CentreType Box
bc  = Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
box
    fbc :: CN MPBall
fbc  = BoxFun -> Box -> CN MPBall
apply BoxFun
f CentreType Box
Box
bc

increasePrecision :: Precision -> Precision
increasePrecision :: Precision -> Precision
increasePrecision Precision
p =
    Precision
p Precision -> Precision -> AddType Precision Precision
forall t1 t2. CanAddAsymmetric t1 t2 => t1 -> t2 -> AddType t1 t2
+ (Integer -> Precision
prec (Integer -> Precision) -> Integer -> Precision
forall a b. (a -> b) -> a -> b
$ (Precision -> Integer
forall t. CanBeInteger t => t -> Integer
integer Precision
p) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`Prelude.div` Integer
2)

newtonStep :: BoxFun -> Accuracy -> Vector (CN MPBall) -> Vector (CN MPBall) -> Matrix (CN MPBall) -> SearchBox -> Bool -> Maybe (Bool, SearchBox)
newtonStep :: BoxFun
-> Accuracy
-> Box
-> Box
-> Matrix (CN MPBall)
-> SearchBox
-> Bool
-> Maybe (Bool, SearchBox)
newtonStep BoxFun
f Accuracy
ac Box
c Box
dfc Matrix (CN MPBall)
hInv b :: SearchBox
b@(SearchBox Box
box CN MPBall
m) Bool
newtonSuccesful = 
    --Just $ SearchBox box' m'
    {-trace ("precision m "++(show $ (fmap getPrecision) m)) $
    trace ("precision m' "++(show $ (fmap getPrecision) m')) $
    trace ("precision box centre "++(show $ getPrecision c)) $
    trace ("precision box "++(show $ getPrecision box)) $
    trace ("precision newton box "++(show $ getPrecision newtonBox)) $
    trace ("precision box' "++(show $ getPrecision box')) $
    trace ("precision hInv "++(show $ getPrecision (entries hInv ! int 0))) $-}
    if CN MPBall -> Accuracy
forall a. HasAccuracy a => a -> Accuracy
getAccuracy CN MPBall
m Accuracy -> Accuracy -> OrderCompareType Accuracy Accuracy
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
>= Accuracy
ac then
        (Bool, SearchBox) -> Maybe (Bool, SearchBox)
forall a. a -> Maybe a
Just (Bool
newtonSuccesful, SearchBox
b)
    --else if not hInvDefined then
    --    Just (newtonSuccesful, b)
    else if Box -> Box -> Bool
Box.intersectionCertainlyEmpty Box
box SubType Box Box
Box
newtonBox then
        Maybe (Bool, SearchBox)
forall a. Maybe a
Nothing
    else if Box -> CN MPBall
Box.width Box
box' CN MPBall -> CN MPBall -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!<=! (Rational -> Dyadic
forall t. CanBeDyadic t => t -> Dyadic
dyadic (Rational -> Dyadic) -> Rational -> Dyadic
forall a b. (a -> b) -> a -> b
$ Rational
0.75) Dyadic -> CN MPBall -> MulType Dyadic (CN MPBall)
forall t1 t2. CanMulAsymmetric t1 t2 => t1 -> t2 -> MulType t1 t2
* Box -> CN MPBall
Box.width Box
box then
        if CN MPBall -> Accuracy
forall a. HasAccuracy a => a -> Accuracy
getAccuracy CN MPBall
m' Accuracy -> Accuracy -> OrderCompareType Accuracy Accuracy
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
> CN MPBall -> Accuracy
forall a. HasAccuracy a => a -> Accuracy
getAccuracy CN MPBall
m then
            BoxFun
-> Accuracy
-> Box
-> Box
-> Matrix (CN MPBall)
-> SearchBox
-> Bool
-> Maybe (Bool, SearchBox)
newtonStep BoxFun
f Accuracy
ac Box
c Box
dfc Matrix (CN MPBall)
hInv (Box -> CN MPBall -> SearchBox
SearchBox Box
box' CN MPBall
m') Bool
True
        else 
            (Bool, SearchBox) -> Maybe (Bool, SearchBox)
forall a. a -> Maybe a
Just (Bool
True, Box -> CN MPBall -> SearchBox
SearchBox (Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision (Precision -> Precision
increasePrecision (Precision -> Precision) -> Precision -> Precision
forall a b. (a -> b) -> a -> b
$ Box -> Precision
forall t. HasPrecision t => t -> Precision
getPrecision Box
box') Box
box') CN MPBall
m')
    else 
        (Bool, SearchBox) -> Maybe (Bool, SearchBox)
forall a. a -> Maybe a
Just (Bool
newtonSuccesful, Box -> CN MPBall -> SearchBox
SearchBox Box
box' CN MPBall
m')
    where
    {-c           = centre box
    dfc         = gradient f c-}
    -- hInvDefined = V.foldl' (&&) (True) $ V.map (isJust . fst . ensureNoCN) (entries hInv)
    newtonBox :: SubType Box Box
newtonBox   = Box
c Box -> Box -> SubType Box Box
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- Matrix (CN MPBall)
hInv Matrix (CN MPBall) -> Box -> MulType (Matrix (CN MPBall)) Box
forall t1 t2. CanMulAsymmetric t1 t2 => t1 -> t2 -> MulType t1 t2
* (Box
dfc)
    box' :: Box
box'        = Box -> Box -> Box
Box.nonEmptyIntersection Box
box SubType Box Box
Box
newtonBox
    m' :: CN MPBall
m'          = BoxFun -> Box -> CN MPBall
apply BoxFun
f Box
box'

processBox :: BoxFun -> Accuracy -> CN MPBall -> SearchBox -> (CN MPBall, [SearchBox])
processBox :: BoxFun
-> Accuracy -> CN MPBall -> SearchBox -> (CN MPBall, [SearchBox])
processBox BoxFun
f Accuracy
ac CN MPBall
cutoff SearchBox
box =
    if Box -> Accuracy
forall a. HasAccuracy a => a -> Accuracy
getAccuracy Box
ext Accuracy -> Accuracy -> OrderCompareType Accuracy Accuracy
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
< Integer -> Accuracy
forall t. ConvertibleExactly t Accuracy => t -> Accuracy
bits Integer
10 then 
        BoxFun -> Box -> CN MPBall -> Box -> (CN MPBall, [SearchBox])
split BoxFun
f (BoxFun -> Box -> Box
gradient BoxFun
f Box
ext) CN MPBall
cutoff Box
ext  
    else 
        (CN MPBall, [SearchBox])
result
    where
    ext :: Box
ext            = SearchBox -> Box
extents SearchBox
box
    (CN MPBall
_fb, Box
dfb, Matrix (CN MPBall)
hfb) = BoxFun -> Box -> (CN MPBall, Box, Matrix (CN MPBall))
valueGradientHessian BoxFun
f Box
ext
    c :: CentreType Box
c              = Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
ext
    dfc :: Box
dfc            = BoxFun -> Box -> Box
gradient BoxFun
f CentreType Box
Box
c
    maybeHinv :: Maybe (Matrix (CN MPBall))
maybeHinv      = Matrix (CN MPBall) -> Maybe (Matrix (CN MPBall))
inverse Matrix (CN MPBall)
hfb
    -- p              = getPrecision box
    box' :: Maybe (Bool, SearchBox)
box'           = --Just (False, box)
        case Maybe (Matrix (CN MPBall))
maybeHinv of 
            Maybe (Matrix (CN MPBall))
Nothing   -> (Bool, SearchBox) -> Maybe (Bool, SearchBox)
forall a. a -> Maybe a
Just (Bool
False, SearchBox
box)
            Just Matrix (CN MPBall)
hInv -> BoxFun
-> Accuracy
-> Box
-> Box
-> Matrix (CN MPBall)
-> SearchBox
-> Bool
-> Maybe (Bool, SearchBox)
newtonStep BoxFun
f Accuracy
ac CentreType Box
Box
c Box
dfc Matrix (CN MPBall)
hInv SearchBox
box Bool
False
    result :: (CN MPBall, [SearchBox])
result =
        case Maybe (Bool, SearchBox)
box' of 
            Maybe (Bool, SearchBox)
Nothing -> (CN MPBall
cutoff, [])
            Just (Bool
newtonSuccesful, bx :: SearchBox
bx@(SearchBox Box
bxe CN MPBall
m)) ->
                let
                    c' :: MinMaxType (CN MPBall) (CN MPBall)
c' = CN MPBall -> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min (CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
upperBound (CN MPBall -> CN MPBall) -> CN MPBall -> CN MPBall
forall a b. (a -> b) -> a -> b
$ BoxFun -> Box -> CN MPBall
apply BoxFun
f (Box -> CN MPBall) -> Box -> CN MPBall
forall a b. (a -> b) -> a -> b
$ Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
bxe :: CN MPBall) CN MPBall
cutoff    
                in
                if Bool
newtonSuccesful then
                    if CN MPBall -> Accuracy
forall a. HasAccuracy a => a -> Accuracy
getAccuracy CN MPBall
m Accuracy -> Accuracy -> OrderCompareType Accuracy Accuracy
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
>= Accuracy
ac then
                        (CN MPBall
MinMaxType (CN MPBall) (CN MPBall)
c', [SearchBox
bx])
                    else
                        BoxFun
-> Accuracy -> CN MPBall -> SearchBox -> (CN MPBall, [SearchBox])
processBox BoxFun
f Accuracy
ac CN MPBall
MinMaxType (CN MPBall) (CN MPBall)
c' SearchBox
bx
                else
                    BoxFun -> Box -> CN MPBall -> Box -> (CN MPBall, [SearchBox])
split BoxFun
f Box
dfb CN MPBall
MinMaxType (CN MPBall) (CN MPBall)
c' Box
bxe

split :: BoxFun -> Vector (CN MPBall) -> CN MPBall -> Box -> (CN MPBall, [SearchBox])
split :: BoxFun -> Box -> CN MPBall -> Box -> (CN MPBall, [SearchBox])
split BoxFun
f Box
dfb CN MPBall
cutoff Box
bxe = 
    let
    diff :: SubType Box Box
diff    = Box
bxe Box -> Box -> SubType Box Box
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
bxe
    dir :: Integer -> CN Dyadic
dir Integer
i   = ((ErrorBound -> Dyadic)
-> CollectErrors NumErrors ErrorBound -> CN Dyadic
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ErrorBound -> Dyadic
forall t. CanBeDyadic t => t -> Dyadic
dyadic) (CollectErrors NumErrors ErrorBound -> CN Dyadic)
-> CollectErrors NumErrors ErrorBound -> CN Dyadic
forall a b. (a -> b) -> a -> b
$ ((MPBall -> ErrorBound)
-> CN MPBall -> CollectErrors NumErrors ErrorBound
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap MPBall -> ErrorBound
forall t. IsBall t => t -> ErrorBound
radius) (CN MPBall -> CollectErrors NumErrors ErrorBound)
-> CN MPBall -> CollectErrors NumErrors ErrorBound
forall a b. (a -> b) -> a -> b
$ (Box
dfb Box -> Integer -> CN MPBall
forall a. Vector a -> Integer -> a
! Integer
i) CN MPBall -> CN MPBall -> MulType (CN MPBall) (CN MPBall)
forall t1 t2. CanMulAsymmetric t1 t2 => t1 -> t2 -> MulType t1 t2
* (SubType Box Box
Box
diff Box -> Integer -> CN MPBall
forall a. Vector a -> Integer -> a
! Integer
i) :: CN Dyadic
    dirs :: Vector (CN Dyadic)
dirs    = (Integer -> CN Dyadic) -> Vector Integer -> Vector (CN Dyadic)
forall a b. (a -> b) -> Vector a -> Vector b
V.map Integer -> CN Dyadic
dir (Vector Integer -> Vector (CN Dyadic))
-> Vector Integer -> Vector (CN Dyadic)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Vector Integer
forall a. Enum a => a -> a -> Vector a
V.enumFromTo Integer
0 (Box -> Integer
forall a. Vector a -> Integer
V.length Box
bxe Integer -> Integer -> SubType Integer Integer
forall t1 t2. CanSub t1 t2 => t1 -> t2 -> SubType t1 t2
- Integer
1)
    dirsDefined :: Bool
dirsDefined = (Bool -> Bool -> Bool) -> Bool -> Vector Bool -> Bool
forall b a. (b -> a -> b) -> b -> Vector a -> b
V.foldl' Bool -> Bool -> Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
(&&) Bool
True (Vector Bool -> Bool) -> Vector Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (CN Dyadic -> Bool) -> Vector (CN Dyadic) -> Vector Bool
forall a b. (a -> b) -> Vector a -> Vector b
V.map (Bool -> Bool
forall t. CanNeg t => t -> NegType t
not (Bool -> Bool) -> (CN Dyadic -> Bool) -> CN Dyadic -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CN Dyadic -> Bool
forall es. CanTestErrorsPresent es => es -> Bool
CN.hasError) Vector (CN Dyadic)
dirs
    aux :: Integer -> Integer -> Dyadic -> Integer
aux Integer
k Integer
j Dyadic
d = 
        if Integer
k Integer -> Integer -> EqCompareType Integer Integer
forall a b. HasEqAsymmetric a b => a -> b -> EqCompareType a b
== Box -> Integer
forall a. Vector a -> Integer
V.length Box
bxe then 
            Integer
j 
        else 
            let
                d' :: Dyadic
d' = CN Dyadic -> Dyadic
forall p. CN p -> p
unCN (CN Dyadic -> Dyadic) -> CN Dyadic -> Dyadic
forall a b. (a -> b) -> a -> b
$ Vector (CN Dyadic)
dirs Vector (CN Dyadic) -> Integer -> CN Dyadic
forall a. Vector a -> Integer -> a
! Integer
k
            in
            if Dyadic
d' Dyadic -> Dyadic -> OrderCompareType Dyadic Dyadic
forall a b.
HasOrderAsymmetric a b =>
a -> b -> OrderCompareType a b
> Dyadic
d then 
                Integer -> Integer -> Dyadic -> Integer
aux (Integer
k Integer -> Integer -> AddType Integer Integer
forall t1 t2. CanAddAsymmetric t1 t2 => t1 -> t2 -> AddType t1 t2
+ Integer
1) Integer
k Dyadic
d'
            else
                Integer -> Integer -> Dyadic -> Integer
aux (Integer
k Integer -> Integer -> AddType Integer Integer
forall t1 t2. CanAddAsymmetric t1 t2 => t1 -> t2 -> AddType t1 t2
+ Integer
1) Integer
j Dyadic
d
    splittingIndex :: IfThenElseType Bool Integer
splittingIndex = 
        if Bool
dirsDefined then (Integer -> Integer -> Dyadic -> Integer
aux Integer
1 Integer
0 (CN Dyadic -> Dyadic
forall p. CN p -> p
unCN (CN Dyadic -> Dyadic) -> CN Dyadic -> Dyadic
forall a b. (a -> b) -> a -> b
$ Vector (CN Dyadic)
dirs Vector (CN Dyadic) -> Integer -> CN Dyadic
forall a. Vector a -> Integer -> a
! Integer
0)) else Box -> Integer
Box.widestDirection Box
bxe
    (Box
a , Box
b)    = Integer -> Box -> (Box, Box)
Box.bisect Integer
IfThenElseType Bool Integer
splittingIndex Box
bxe
    (CN MPBall
fa, Box
dfa') = BoxFun -> Box -> (CN MPBall, Box)
valueGradient BoxFun
f Box
a
    (CN MPBall
fb, Box
dfb') = BoxFun -> Box -> (CN MPBall, Box)
valueGradient BoxFun
f Box
b
    ac :: CentreType Box
ac  = Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
a
    bc :: CentreType Box
bc  = Box -> CentreType Box
forall t. IsBall t => t -> CentreType t
centre Box
b
    fac :: CN MPBall
fac  = BoxFun -> Box -> CN MPBall
apply BoxFun
f CentreType Box
Box
ac
    fbc :: CN MPBall
fbc  = BoxFun -> Box -> CN MPBall
apply BoxFun
f CentreType Box
Box
bc
    fa' :: CN MPBall
fa'  = BoxFun -> CN MPBall -> Box -> Box -> Box -> CN MPBall -> CN MPBall
lipschitzRange BoxFun
f CN MPBall
fac CentreType Box
Box
ac Box
dfa' Box
a CN MPBall
fa
    fb' :: CN MPBall
fb'  = BoxFun -> CN MPBall -> Box -> Box -> Box -> CN MPBall -> CN MPBall
lipschitzRange BoxFun
f CN MPBall
fbc CentreType Box
Box
bc Box
dfb' Box
b CN MPBall
fb
    cutoff' :: MinMaxType (CN MPBall) (CN MPBall)
cutoff'       = CN MPBall -> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min (CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
upperBound CN MPBall
fac :: CN MPBall) (CN MPBall -> MinMaxType (CN MPBall) (CN MPBall))
-> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall a b. (a -> b) -> a -> b
$ CN MPBall -> CN MPBall -> MinMaxType (CN MPBall) (CN MPBall)
forall t1 t2.
CanMinMaxAsymmetric t1 t2 =>
t1 -> t2 -> MinMaxType t1 t2
min (CN MPBall -> CN MPBall
forall i. IsInterval i => i -> i
upperBound CN MPBall
fbc :: CN MPBall) CN MPBall
cutoff
    leftMonotone :: Bool
leftMonotone  = (Bool -> Bool -> Bool) -> Bool -> Vector Bool -> Bool
forall b a. (b -> a -> b) -> b -> Vector a -> b
V.foldl' Bool -> Bool -> Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
(||) Bool
False (Vector Bool -> Bool) -> Vector Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (CN MPBall -> Bool) -> Box -> Vector Bool
forall a b. (a -> b) -> Vector a -> Vector b
V.map (CN MPBall -> Integer -> Bool
forall a b. HasEqCertainlyAsymmetric a b => a -> b -> Bool
!/=! Integer
0) Box
dfa'
    rightMonotone :: Bool
rightMonotone = (Bool -> Bool -> Bool) -> Bool -> Vector Bool -> Bool
forall b a. (b -> a -> b) -> b -> Vector a -> b
V.foldl' Bool -> Bool -> Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
(||) Bool
False (Vector Bool -> Bool) -> Vector Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (CN MPBall -> Bool) -> Box -> Vector Bool
forall a b. (a -> b) -> Vector a -> Vector b
V.map (CN MPBall -> Integer -> Bool
forall a b. HasEqCertainlyAsymmetric a b => a -> b -> Bool
!/=! Integer
0) Box
dfb'
    boxes :: [SearchBox]
boxes = 
        case (Bool
leftMonotone Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
|| CN MPBall
fa' CN MPBall -> CN MPBall -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! CN MPBall
MinMaxType (CN MPBall) (CN MPBall)
cutoff', Bool
rightMonotone Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
|| CN MPBall
fb' CN MPBall -> CN MPBall -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! CN MPBall
MinMaxType (CN MPBall) (CN MPBall)
cutoff') of
            (Bool
True,  Bool
True)  -> []
            (Bool
True,  Bool
False) -> [Box -> CN MPBall -> SearchBox
SearchBox Box
b CN MPBall
fb']
            (Bool
False, Bool
True)  -> [Box -> CN MPBall -> SearchBox
SearchBox Box
a CN MPBall
fa']
            (Bool
False, Bool
False) -> [Box -> CN MPBall -> SearchBox
SearchBox Box
a CN MPBall
fa', Box -> CN MPBall -> SearchBox
SearchBox Box
b CN MPBall
fb']
    in
        (CN MPBall
MinMaxType (CN MPBall) (CN MPBall)
cutoff', [SearchBox]
boxes)

-- Precondition: f and g must have the same domain
maxBoxFunGreaterThanN :: BoxFun -> BoxFun -> CN Rational -> Precision -> Bool
maxBoxFunGreaterThanN :: BoxFun -> BoxFun -> CN Rational -> Precision -> Bool
maxBoxFunGreaterThanN BoxFun
f BoxFun
g CN Rational
n Precision
initialPrecision =
    case Box -> [(MPBall, MPBall)]
Box.getEndpoints Box
fbox [(MPBall, MPBall)]
-> [(MPBall, MPBall)]
-> EqCompareType [(MPBall, MPBall)] [(MPBall, MPBall)]
forall a b. HasEqAsymmetric a b => a -> b -> EqCompareType a b
== Box -> [(MPBall, MPBall)]
Box.getEndpoints Box
gbox of
        EqCompareType [(MPBall, MPBall)] [(MPBall, MPBall)]
CertainTrue ->
            BoxFun -> BoxFun -> AndOrType Bool Bool
checkMaxAboveN BoxFun
f BoxFun
g Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
||
                (Box -> CN MPBall
Box.width Box
fboxp CN MPBall -> Rational -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! Rational
cutoff Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
&& Box -> CN MPBall
Box.width Box
gboxp CN MPBall -> Rational -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! Rational
cutoff) Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
&&
                    let
                        newBoxes :: [Box]
newBoxes = Box -> [Box]
Box.fullBisect Box
fboxp

                        updateDomain :: BoxFun -> Box -> BoxFun
updateDomain BoxFun
z = Integer
-> (Vector (Differential (CN MPBall)) -> Differential (CN MPBall))
-> Box
-> BoxFun
BoxFun (BoxFun -> Integer
dimension BoxFun
z) (BoxFun
-> Vector (Differential (CN MPBall)) -> Differential (CN MPBall)
bf_eval BoxFun
z)

                        checkBoxes :: [Box] -> Bool
checkBoxes [] = Bool
True
                        checkBoxes (Box
box : [Box]
boxes) = 
                            if BoxFun -> BoxFun -> AndOrType Bool Bool
checkMaxAboveN (BoxFun -> Box -> BoxFun
updateDomain BoxFun
f Box
box) (BoxFun -> Box -> BoxFun
updateDomain BoxFun
g Box
box) 
                                then [Box] -> Bool
checkBoxes [Box]
boxes
                                else BoxFun -> BoxFun -> CN Rational -> Precision -> Bool
maxBoxFunGreaterThanN BoxFun
f' BoxFun
g' CN Rational
n Precision
initialPrecision Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
&& [Box] -> Bool
checkBoxes [Box]
boxes
                                where
                                    f' :: BoxFun
f' = BoxFun -> Box -> BoxFun
updateDomain BoxFun
f Box
box
                                    g' :: BoxFun
g' = BoxFun -> Box -> BoxFun
updateDomain BoxFun
g Box
box

                    in
                        [Box] -> Bool
checkBoxes [Box]
newBoxes

        EqCompareType [(MPBall, MPBall)] [(MPBall, MPBall)]
_ ->
            String -> Bool -> Bool
forall a. String -> a -> a
trace String
"Domain of f not equal to domain of g"
            Bool
False
    where
        cutoff :: DivType Integer Integer
cutoff = Integer
1Integer -> Integer -> DivType Integer Integer
forall t1 t2. CanDiv t1 t2 => t1 -> t2 -> DivType t1 t2
/Integer
2Integer -> Integer -> PowType Integer Integer
forall t1 t2. CanPow t1 t2 => t1 -> t2 -> PowType t1 t2
^Integer
10

        fbox :: Box
fbox                = BoxFun -> Box
domain BoxFun
f
        fboxp :: Box
fboxp               = Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision Precision
initialPrecision Box
fbox 

        gbox :: Box
gbox                = BoxFun -> Box
domain BoxFun
g
        gboxp :: Box
gboxp               = Precision -> Box -> Box
forall t. CanSetPrecision t => Precision -> t -> t
setPrecision Precision
initialPrecision Box
gbox

        checkMaxAboveN :: BoxFun -> BoxFun -> AndOrType Bool Bool
checkMaxAboveN BoxFun
h BoxFun
i = BoxFun -> CN MPBall
applyMinimum BoxFun
h CN MPBall -> CN Rational -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! CN Rational
n Bool -> Bool -> AndOrType Bool Bool
forall a b. CanAndOrAsymmetric a b => a -> b -> AndOrType a b
|| BoxFun -> CN MPBall
applyMinimum BoxFun
i CN MPBall -> CN Rational -> Bool
forall a b. HasOrderCertainlyAsymmetric a b => a -> b -> Bool
!>! CN Rational
n