부동 소수점 계산

Question

모호한 제목의 사과. 내 문제는 다음과 같습니다. w이 1보다 작은 항목을 가진 벡터 인 경우 두 번째 벡터의 두 배가 v이고 양수 항목의 수가 1보다 작 으면 (아래 재귀를 사용하여 계산 됨) 두 배인 u은 양수보다 작습니다. 하나 sum(v)>1-u까지 재귀

w(i) = RandomNumber(); //A random number from (0,1) - not necessarily uniform 
v(i) = v(i-1)*w(i)*(1-w(i-1))/w(i-1); 

를 사용 v 연장. 문제는 u이 매우 작을 수 있고, v(i)이 (확률 적으로) 감소하기 때문에 너무 작아 질 수 있다는 것입니다. 그리고 우리는 w(i)을 가까이에 둘 수도 있습니다.

이것을 구현하는 가장 안전한 방법은 무엇입니까? 정확성을위한 포인트 :

Answer 1

너무 많은 실수없이 부동 소수점을 합하는 일반적인 방법 중 하나는 가장 작은 것에서 가장 큰 것까지 합산하는 것입니다. v(i)의 계산은 v(i-1)에만 의존하기 때문에 이전 노드의 숫자를 각 노드에 보관하고 이전 값은 별도의 변수에 저장하여 정렬 된 트리에 보관할 수 있습니다. 새로운 값을 삽입하거나 노드를 재정렬하면, 그 지점에서 트리를 따라 가면서 합계를 다시 계산해야합니다. 각 노드의 합계는 곧장 추가 될 수도 있고, 카한 합계와 같은 비트를 더 보존 할 수도 있습니다.

Answer 2

v (i)를 누적하고 1-u와 비교하는 대신 1-u로 시작하고 음수가 될 때까지 각 v (i)를 줄이십니까? 정확도는 0에 가까울수록 좋아집니다.