The problem I have is pretty simple, however I cannot find an answer.
I need an *efficient* algorithm to sample integral points within an m-dimensional ball of radius r around the origin (Euclidean norm) uniformly. I want to sample uniformly from the set
$$
S = \{x \in \mathbb{Z}^m | x \in \mathcal{B}^m(r)\}.
$$
The obvious approach is rejection sampling, i.e. uniformly sample integral points within the m-dimensional box with coordinates between $-r$ and $r$ and reject those samples with norm $\geq r$.
However this approach is not efficient, as for $m=40$ this already takes several minutes ($r=40$).
Can you help me with this?



Sample integral points in m-Ball
If $r$ is large compared to $\sqrt{m}$ you may proceed as follows.


You may sample a vector $(x\_1,\ldots,x\_m)$ of $m$ independent normal-distributed variables, and divide each coordinate $x\_i$ of that vector by the length $\sqrt{x\_1^2 + \ldots + x\_m^2}$ of the vector. This gives you a uniform-distributed vector on the surface of the unit ball. Then you sample a variable $0 \leq z \leq r+s$ with distribution function proportional to $z^m$ for $0 \leq z \leq r+s$,
for a constant $s$ to be discussed later.


Then you multiply the vector with $z$ and round the coordinates
of the result vector to the nearest integer. You accept the vector if it has length $\leq r$ and reject is otherwise.


In case $s =\sqrt{m}/2$ you get a uniform distribution of the integer points in the ball $\mathcal{B}^m(r)$. But then the rejection rate is high if $r$ is not much larger than $\sqrt{m}$. If you can live with a smaller probability for choosing a point close to the boundary you may also use a smaller value for $s$.


