## interpolation with ints

Expand Messages
• Hi, Usually interpolations for mutlimedia programming are done with floats, but I m trying to make it with ints in order to make it deterministic and also it s
Message 1 of 4 , Jun 3, 2013
Hi,

Usually interpolations for mutlimedia programming are done with
floats, but I'm trying to make it with ints in order to make it
deterministic and also it's maybe faster for the RPi.

So I'm trying to see how I could avoid the calculus that are done several times.
Either with partial application, creating a closure, or even keeping
the intermediate calculus (v_diff, t_diff) the stress test shows that
the simplest (naive?) one is the fastest.

Is there a way to optimise this?

\$ cat interpolint.mli
(** Interpolation with ints *)

val inter :
t1:int -> t2:int ->
v1:int -> v2:int -> int -> int
(** simple interpolation *)

type inter_func = int -> int

val interp :
t1:int -> t2:int ->
v1:int -> v2:int -> inter_func
(** interpolation with partial application *)

type inter_value

val interv :
t1:int -> t2:int ->
v1:int -> v2:int -> inter_value

val intervf : inter_value -> int -> int
(** interpolation with intermediate calculus done *)

\$ cat interpolint.ml

let inter ~t1 ~t2 ~v1 ~v2 t =
((v2 - v1) * (t - t1)) / (t2 - t1) + v1

type inter_func = int -> int

let interp ~t1 ~t2 ~v1 ~v2 =
let v_diff = (v2 - v1)
and t_diff = (t2 - t1) in
function t ->
(v_diff * (t - t1)) / t_diff + v1

type inter_value = int * int * int * int

let interv ~t1 ~t2 ~v1 ~v2 =
let v_diff = (v2 - v1)
and t_diff = (t2 - t1) in
(t1, v1, v_diff, t_diff)

let intervf (t1, v1, v_diff, t_diff) t =
(v_diff * (t - t1)) / t_diff + v1

\$ cat stress.ml
open Interpolint

let timeit n f s =
let t0 = Unix.gettimeofday () in
for i = 1 to n do f () done;
let t1 = Unix.gettimeofday () in
Printf.printf "time(%s): %f\n%!" s (t1 -. t0)

let stress0 () =
for t = 1000 to 1200 do
let _ = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 t in
()
done

let stress1 () =
let f = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
for t = 1000 to 1200 do
let _ = f t in
()
done

let stress2 () =
let fi = interp ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
for t = 1000 to 1200 do
let _ = fi t in
()
done

let stress3 () =
let v = interv ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
for t = 1000 to 1200 do
let _ = intervf v t in
()
done

let () =
timeit 100_000 stress0 "stress0";
timeit 100_000 stress1 "stress1";
timeit 100_000 stress2 "stress2";
timeit 100_000 stress3 "stress3";
;;

\$ ./stress.opt
time(stress0): 0.267789
time(stress1): 0.320826
time(stress2): 0.287542
time(stress3): 0.287472

--
• You could take as parameters ~t1 ~tdiff ~v1 ~vdiff but I don t think this will make a big difference (this purely-integer calculus is very fast already). Does
Message 2 of 4 , Jun 3, 2013
You could take as parameters
~t1 ~tdiff ~v1 ~vdiff
but I don't think this will make a big difference (this purely-integer

On Mon, Jun 3, 2013 at 9:57 PM, Florent Monnier
<fmonnier@...> wrote:
> Hi,
>
> Usually interpolations for mutlimedia programming are done with
> floats, but I'm trying to make it with ints in order to make it
> deterministic and also it's maybe faster for the RPi.
>
> So I'm trying to see how I could avoid the calculus that are done several times.
> Either with partial application, creating a closure, or even keeping
> the intermediate calculus (v_diff, t_diff) the stress test shows that
> the simplest (naive?) one is the fastest.
>
> Is there a way to optimise this?
>
> \$ cat interpolint.mli
> (** Interpolation with ints *)
>
> val inter :
> t1:int -> t2:int ->
> v1:int -> v2:int -> int -> int
> (** simple interpolation *)
>
> type inter_func = int -> int
>
> val interp :
> t1:int -> t2:int ->
> v1:int -> v2:int -> inter_func
> (** interpolation with partial application *)
>
> type inter_value
>
> val interv :
> t1:int -> t2:int ->
> v1:int -> v2:int -> inter_value
>
> val intervf : inter_value -> int -> int
> (** interpolation with intermediate calculus done *)
>
> \$ cat interpolint.ml
>
> let inter ~t1 ~t2 ~v1 ~v2 t =
> ((v2 - v1) * (t - t1)) / (t2 - t1) + v1
>
> type inter_func = int -> int
>
> let interp ~t1 ~t2 ~v1 ~v2 =
> let v_diff = (v2 - v1)
> and t_diff = (t2 - t1) in
> function t ->
> (v_diff * (t - t1)) / t_diff + v1
>
> type inter_value = int * int * int * int
>
> let interv ~t1 ~t2 ~v1 ~v2 =
> let v_diff = (v2 - v1)
> and t_diff = (t2 - t1) in
> (t1, v1, v_diff, t_diff)
>
> let intervf (t1, v1, v_diff, t_diff) t =
> (v_diff * (t - t1)) / t_diff + v1
>
> \$ cat stress.ml
> open Interpolint
>
> let timeit n f s =
> let t0 = Unix.gettimeofday () in
> for i = 1 to n do f () done;
> let t1 = Unix.gettimeofday () in
> Printf.printf "time(%s): %f\n%!" s (t1 -. t0)
>
> let stress0 () =
> for t = 1000 to 1200 do
> let _ = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 t in
> ()
> done
>
> let stress1 () =
> let f = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
> for t = 1000 to 1200 do
> let _ = f t in
> ()
> done
>
> let stress2 () =
> let fi = interp ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
> for t = 1000 to 1200 do
> let _ = fi t in
> ()
> done
>
> let stress3 () =
> let v = interv ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
> for t = 1000 to 1200 do
> let _ = intervf v t in
> ()
> done
>
> let () =
> timeit 100_000 stress0 "stress0";
> timeit 100_000 stress1 "stress1";
> timeit 100_000 stress2 "stress2";
> timeit 100_000 stress3 "stress3";
> ;;
>
> \$ ./stress.opt
> time(stress0): 0.267789
> time(stress1): 0.320826
> time(stress2): 0.287542
> time(stress3): 0.287472
>
> --
>
>
> ------------------------------------
>
> Archives up to December 31, 2011 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links
>
>
>
• ... Not really. with (((v2 - v1) * (t - t1)) / (t2 - t1) + v1) there are 6 operations, but 4 would be enough ((v_diff * (t - t1)) / t_diff + v1) so I thought I
Message 3 of 4 , Jun 4, 2013
2013/06/04, Gabriel Scherer wrote:
> You could take as parameters
> ~t1 ~tdiff ~v1 ~vdiff
> but I don't think this will make a big difference (this purely-integer
> calculus is very fast already).
>

Not really.
with (((v2 - v1) * (t - t1)) / (t2 - t1) + v1) there are 6 operations,
but 4 would be enough ((v_diff * (t - t1)) / t_diff + v1)
so I thought I could easily save a little there without making the
code too much complex.

Also I noticed that replacing /. 2.0 by *. 0.5 saves by twice. This
simple trick makes save a lot on my desktop computer, but there's not
that much difference there on the RPi.

\$ cat >> interpolint.ml

let interg ~t1 ~t2 ~v1 ~v2 =
let v_diff = (v2 - v1)
and t_diff = (t2 - t1) in
(v_diff, t_diff)

let intervg ~t1 ~t_diff ~v1 ~v_diff t =
(v_diff * (t - t1)) / t_diff + v1

\$ cat >> interpolint.mli

val interg :
t1:int -> t2:int ->
v1:int -> v2:int -> int * int

val intervg :
t1:int -> t_diff:int ->
v1:int -> v_diff:int -> int -> int
(** interpolation with intermediate calculus done,
not given as tuple *)

\$ cat >> stress.ml

let stress4 () =
let t1, t2, v1, v2 = (1000, 1200, 2, 8) in
let v_diff, t_diff = interg ~t1 ~t2 ~v1 ~v2 in
for t = 1000 to 1200 do
let _ = intervg
~t1 ~t_diff
~v1 ~v_diff t
in
()
done

\$ ./stress.opt
time(stress0): 0.267789
time(stress1): 0.320826
time(stress2): 0.287542
time(stress3): 0.287472
time(stress4): 0.293996

--
• I wrote the following program: let stress6 () = let t1 = 1000 and t2 = 1200 and v1 = 2 and v2 = 8 in let tdiff = t2 - t1 and vdiff = v2 - v1 in let acc = ref
Message 4 of 4 , Jun 5, 2013
I wrote the following program:

let stress6 () =
let t1 = 1000 and t2 = 1200 and v1 = 2 and v2 = 8 in
let tdiff = t2 - t1 and vdiff = v2 - v1 in
let acc = ref (v1 * tdiff) in
for t = t1 to t2 do
let _ = !acc / tdiff in
acc := !acc + vdiff;
done

The time is the same as with stress0, because the compiler is too
clever here: it inlines everything, then does constant propagation,
and eg. the (/ tdiff) division becomes (/ 200) (for all the
implementations except f1 that was probably judged too complex to be
inlining, and that therefore pays a Division_by_zero check that the
other avoid).

You should try to measure the results with non-constant values (eg.
(int_of_string Sys.argv.(k)).

On Tue, Jun 4, 2013 at 11:25 PM, Florent Monnier
<fmonnier@...> wrote:
> 2013/06/04, Gabriel Scherer wrote:
>> You could take as parameters
>> ~t1 ~tdiff ~v1 ~vdiff
>> but I don't think this will make a big difference (this purely-integer
>> calculus is very fast already).
>>
>
> Not really.
> with (((v2 - v1) * (t - t1)) / (t2 - t1) + v1) there are 6 operations,
> but 4 would be enough ((v_diff * (t - t1)) / t_diff + v1)
> so I thought I could easily save a little there without making the
> code too much complex.
>
> Also I noticed that replacing /. 2.0 by *. 0.5 saves by twice. This
> simple trick makes save a lot on my desktop computer, but there's not
> that much difference there on the RPi.
>
>
> \$ cat >> interpolint.ml
>
> let interg ~t1 ~t2 ~v1 ~v2 =
> let v_diff = (v2 - v1)
> and t_diff = (t2 - t1) in
> (v_diff, t_diff)
>
> let intervg ~t1 ~t_diff ~v1 ~v_diff t =
> (v_diff * (t - t1)) / t_diff + v1
>
> \$ cat >> interpolint.mli
>
> val interg :
> t1:int -> t2:int ->
> v1:int -> v2:int -> int * int
>
> val intervg :
> t1:int -> t_diff:int ->
> v1:int -> v_diff:int -> int -> int
> (** interpolation with intermediate calculus done,
> not given as tuple *)
>
> \$ cat >> stress.ml
>
> let stress4 () =
> let t1, t2, v1, v2 = (1000, 1200, 2, 8) in
> let v_diff, t_diff = interg ~t1 ~t2 ~v1 ~v2 in
> for t = 1000 to 1200 do
> let _ = intervg
> ~t1 ~t_diff
> ~v1 ~v_diff t
> in
> ()
> done
>
> \$ ./stress.opt
> time(stress0): 0.267789
> time(stress1): 0.320826
> time(stress2): 0.287542
> time(stress3): 0.287472
> time(stress4): 0.293996
>
> --
>
>
> ------------------------------------
>
> Archives up to December 31, 2011 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links
>
>
>
Your message has been successfully submitted and would be delivered to recipients shortly.