Ermitteln der Anzahl der ganzzahligen Punkte in einer Kugel mit Radius R und Dimension D zentriert am Ursprung

Question

Ich schreibe ein Computerprogramm/einen Algorithmus, um die Anzahl der ganzzahligen Punkte innerhalb einer Kugel mit Radius R und D am Ursprung zu zählen . Im Wesentlichen, wenn wir eine Sphäre der Dimension 2 (Kreis) und Radius 5 haben, ermittle ich alle ganzzahligen Lösungen für die Ungleichung X^2 + Y^2 ≤ 25. Gibt es einen effizienten Weg, statt jeden möglichen ganzzahligen Punkt zu zählen die Punkte zählen? Symmetrie verwenden?

Answer 1

Angenommen, die Dimension ist 3 und R ist der Radius. Für z = 0 sind die möglichen x, y Koordinaten die Punkte innerhalb eines Kreises mit dem Radius R, und für jedes z sind die x, y die Punkte innerhalb eines Kreises mit dem Radius sqrt (R * R - z * z); die möglichen Werte von z sind -r, .. 0, 1, .. r wobei r die kleinste ganze Zahl kleiner als R ist. Beachten Sie, dass die Anzahl für z und -z gleich ist.

Wenn wir zu Dimension 1 kommen, fragen wir, wie viele ganze Zahlen ich | i | < R, und dies ist 1 + 2 * r

So:

int ncip(int dim, double R) 
{ 
    int i; 
    int r = (int)floor(R); 
    if (dim == 1) 
    { return 1 + 2*r; 
    } 
    int n = ncip(dim-1, R); // last coord 0 
    for(i=1; i<=r; ++i) 
    { n += 2*ncip(dim-1, sqrt(R*R - i*i)); // last coord +- i 
    } 
    return n; 
} 

Answer 2

Nun, mit Symmetrie können Sie immer nur alle Ganzzahllösungen auf der positiven Seite zählen und dann die Komponenten invertieren. Also, im Falle Ihres Kreises (D = 2, R = 5), müssen Sie nur
{X, Y ∈ N: X² + Y² ≤ R} finden. Dann erstellen Sie die Kombinationen (X, Y), (X, -Y), (-X, Y), (-X, -Y)
Dies lässt Sie mit nur (1/2) ^D Lösungen zu finden.

Sie können auch einen Kreis mit dem Radius R als Quadrat mit dem Radius R/√ 2 annähern, sodass alle Kombinationen von Ganzzahlen, die kleiner oder gleich sind, automatisch hinzugefügt werden können.