  We consider the random field M(t)=\sup_{n\geq 1}\big\{-\log
A_{n}+X_{n}(t)\big\}\,,\qquad t\in T\, for a set $T\subset \mathbb{R}^{m}$,
where $(X_{n})$ is an iid sequence of centered Gaussian random fields on $T$
and $0<A_{1}<A_{2}<\cdots $ are the arrivals of a general renewal process on
$(0,\infty )$, independent of $(X_{n})$. In particular, a large class of
max-stable random fields with Gumbel marginals have such a representation.
Assume that one needs $c\left( d\right) =c(\{t_{1},\ldots,t_{d}\})$ function
evaluations to sample $X_{n}$ at $d$ locations $t_{1},\ldots ,t_{d}\in T$. We
provide an algorithm which, for any $\epsilon >0$, samples $M(t_{1}),\ldots
,M(t_{d})$ with complexity $o(c(d)\,d^{\epsilon })$. Moreover, if $X_{n}$ has
an a.s. converging series representation, then $M$ can be a.s. approximated
with error $\delta $ uniformly over $T$ and with complexity $O(1/(\delta \log
(1/\delta ))^{1/\alpha })$, where $\alpha $ relates to the H\"{o}lder
continuity exponent of the process $X_{n}$ (so, if $X_{n}$ is Brownian motion,
$\alpha =1/2$).
