[Shootout-list] Organisation for numerical tests

[Sebastien Loisel]

On 5/4/05, Isaac Gouy <igouy2@yahoo.com> wrote:
> Are there problems not dominated by array access?

These super classical tests can, if well implemented, get very close
to the theoritical FLOP rate of your computer, so in principle they're
FPU bound, not memory bound.

However, a large dense matrix will be memory bound unless we use the
LAPACK/BLAS trick where we store the dense matrix by blocks.

> Are there problems not dominated by io?

Never. None of them do much I/O.

> Are there problems were a good approach doesn't require destructive updat=
e?

Most of them don't require a destructive update, but as is well known,
purely functional data structures are slower than imperative ones. The
trickiest one is the reverse mode of automatic differentiation. With
destructive updates, the running time is 3T. With non-destructive
updates, the naive approach takes time nT, which is no gain compared
to finite difference or symbolic differentiation. A smart
non-destructive approach would require a purely functional array data
structure, perhaps by using a purely functional balanced binary tree
to store it. You will of course pay a large overhead cost, as well as
a log(n) cost, but it's hopefully better than n. It may be possibly to
circumvent this entire problem with lazyness, but I'd have to think
about it.

Sebastien Loisel