(*
check out http://www.smlnj.org/doc/basis/pages/sml-std-basis.html
for sml built-in functions.  e.g. for Math.ln, click REALS then "The MATH signature";
Real.fromInt is in "The REAL signature".
*)

val real = Real.fromInt;
fun natrangeSlow a b = if b < a then [] else ((natrangeSlow a (b - 1)) @ [b]);

val natrange = 
    let 
        fun nr l a b = if b < a then l else nr (b :: l) a (b-1) 
    in 
        nr [] 
    end;

fun log2 x = (Math.ln x) / (Math.ln (real 2));

fun T n = if n > 0 andalso n < 4 then 1 else (T (n div 4)) + (T ((3 * n) div 4)) + n;

fun T' x = let val alpha = 2.0
               val beta = 1.0 in
               alpha * x * (log2 x) + beta
           end;

fun checkGT0 f a b = List.all (fn x => x >= 0.0) (map f (natrange a b));

val checkBound = checkGT0 (fn n => (T' (real n)) - (real (T n)));

val checkBase = checkBound 1 3;
val checkInduct = 
    let fun checkInductfn n = (T' (real n)) - ((T' (real (n div 4))) + (T' (real ((3 * n) div 4))) + (real n)) 
    in
        checkGT0 checkInductfn 4 1000
    end;
val checkBound1000 = checkBound 1 1000;

fun intersperse x (x1::x2::l) = x1::x::(intersperse x (x2::l))
  | intersperse _ l = l;

fun outputTable fileName sep table = 
    let val fd = TextIO.openOut fileName in
        TextIO.output (fd, concat (intersperse "\n" (map (fn l => concat (intersperse sep l)) table)));
        TextIO.flushOut fd
    end

fun graph fileName sep fl a b = 
    outputTable fileName sep (map (fn n => (Int.toString n) :: (map (fn f => f n) fl)) (natrange a b));

fun graphT fileName sep a b = 
    graph fileName sep [Int.toString o T, Real.toString o T' o real] a b;
        
(*
- graphT "t" "\t" 1 10000;
will produce a tab seperated file called "t" then in GNUPlot type
> plot "t" using 1:2 with lines title "T", "t" using 1:3 with lines title "T'"
will produce a graph of the data
*)