몬테 - 카를로 (Monte-Carlo) 방법을 사용하여 n 볼의 볼륨을 계산합니다.

Question

R^n의 n 볼의 볼륨을 계산하는 MATLAB에서 함수를 생성하려고합니다. 이를 위해 저는 n 큐브에서 임의로 포인트를 생성 한 몬테카를로 방법을 사용하고 생성 된 모든 포인트에 대해 n 스피어 내부의 포인트 비율을 n 큐브의 볼륨으로 곱한 값을 사용합니다. 지금까지 작성한 코드는 다음과 같습니다.

function [ approximate_volume ] = MonteCarloHypersphereVolume(radius, dimension, number_of_generations) 
%MonteCarloHypersphereVolume Computes the volume of a 
%'dimension'-dimensional hypersphere by the Monte Carlo method 

number_within_sphere = 0; 
parfor i = 1 : number_of_generations 
    randoms = zeros(1, dimension); 
    for j = 1 : dimension 
     randoms(j) = randi(radius * 2) - radius; 
    end 

    if sum(randoms .^ 2) <= radius^2 
     number_within_sphere = number_within_sphere + 1; 
    end 
end 

approximate_volume = (number_within_sphere/number_of_generations) * (2*radius)^dimension; 

end 

그러나 이것은 매우 부정확 한 것으로 보입니다. Wikipedia에 따르면, 단위 10 구슬의 부피는 다음과 같아야합니다. V_10 = pi^5/5! = 2.5502, 그러나 1000000 반복으로 함수를 실행하면 11.0067을 반환하지만 실제로 여러 번 실행하면 항상 11보다 큰 값이 반환됩니다.

또한 GPGPU 프로그래밍을 사용하여이 기능의 성능을 향상시키는 방법이 있습니까? number_within_sphere의 데이터 종속성을 제외하고는 쉽게 병렬 처리가 가능합니까?

Answer 1

각 치수를 연속적으로 균일하게 분포 시키려면 randi이 아니라 rand을 사용해야합니다. 즉, N 차원 입방체의 체적 [-1 N-dimesional 부 공의 용적 비율 때문에, 조절되지 않는

randoms(j) = rand*radius*2 - radius; 

Answer 2

이 방식으로 광고

randoms(j) = randi(radius * 2) - radius; 

대체되고 1]^n은 기하 급수적으로 빠르게 0이됩니다 (따라서 단위 입방체의 거의 모든 무작위 지점은 단위 공 외부에있을 것입니다; 예를 들어, n = 30 인 경우 입방체의 체적은 약 5 * 10^13 배 더 큽니다 공의 부피보다 큼).

대신 한 번 그러나, 아래로 기록되는 형태

http://www.cs.berkeley.edu/~sinclair/cs294/n16.pdf

, 예를 들어 설명한 바와 같이 볼록 체의 체적을 찾는 여기 다항식 복잡성 몬테카를로 알고리즘을 사용해야 는 n 차원 공 의 수식을 이미 가정합니다 (텍스트에서 B_0의 볼륨을 알아야 함). 그러나 텍스트에서와 같이 동심 구가 증가하는 순서 대신에 유사한 특성을 갖는 증가하는 큐브의 순서 (첫 번째 정육면체는 단위 공에 새겨진 정육면체이고 마지막 부분은 [-1,1]^n이고, 연속적인 큐브의 측면 사이의 비율은 (최대로 1 + 1/n)이며, 볼록한 몸체 K는 단위 공이고, 다음 동일한 알고리즘이 단위 공의 부피를 찾는 데 사용될 수 있습니다.