numerical integral vs counting roots I have a problem that can be viewed in two different ways:


Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.
Count (just count) the roots of an $n$-dimensional function (not a polynomial).


Solving just one of them is sufficient for solving the original problem.
I know that simple algorithms for numerical integration would take $O(L^n)$, taking linear time per dimension. But I am not sure if there an asymptotically faster algorithms for (1). 

For (2), I am aware of algorithms that can find roots (Newton and Bisection), but I am not sure about the best algorithms just for counting how many roots are in a non-polynomial $n$-dimensional function.

What are the best algorithms for (2)? Are they better than the fastest of (1)?
Consider using Monte Carlo method for computing quadrature. It is good choice when you need not so precise approximation and dimension of the domain is large.

You definitely should provide more details.