의사 Diophantine 방정식을 최소화하는 빠른 알고리즘

Question

우리는 O (N)에서이 문제를 해결하는 알고리즘을 찾고 있습니다. | - B

:

주어진 두 실수의 a와 b 발현을 최소화 -N과 N 사이의 정수 n 찾기 (일반성을 잃지 않고 당신은 그들이 모두 0과 1 사이입니다 가정 할 수 있습니다) - 둥근 (an - b) |

유클리드 알고리즘이 잘 작동한다고 생각했지만 해결할 수 없습니다. 정수 n을 철저히 검색하는 것보다 훨씬 빠른 방법이 있어야합니다.

참고 : 우리의 상황에서 a와 b는 자주 변경 될 수 있으므로 룩업 테이블에 대해 a와 b를 고정하는 것이 가능합니다. 따라서 N도 달라질 수 있으므로 추한 것입니다. 룩업 테이블을 상세히 보지 않았다면, N의 함수로서 얻을 수있는 것이 얼마나 작은 지 알 수있다.

Answer 1

그것은

은 그들이 어떻게 관련되어 ... 소리? b를 유리수 b1/b2로 대체 할 수 있다고 가정하십시오. 이제 an-b1/b2가 대략 m 인 정수 n과 m을 찾고 있습니다. 그렇지 않으면 합리적인 숫자 인 (m + (b1/b2))/n = (mb2 + b1)/nb1이 대략 a와 같은 n과 m을 찾고 있습니다. a1 = mb2 + b1 및 a2 = nb1로 설정하십시오. 연속 분수 근사값으로부터 a1과 a2에 대한 값을 찾고 n과 m을 풀어 라.

또 다른 방법이 될 수하십시오 ~ A1/A2와 B ~ B1/B2 :

1. 는 a와 b에 대한 좋은 합리적인 근사치를 찾을 수 있습니다.
2. n과 m에 대해 n (a1/a2) - (b1/b2) = m을 구하십시오.

나는 그것이 잘 작동하는지 너무 확신하지 못합니다. a에 필요한 정확도는 n과 b에 따라 다릅니다.

Answer 2

aN - b을 가능한 한 정수에 가깝게 만드는 정수 N을 효율적으로 찾고있다. . a 및 b이 수정 되었습니까? 예 당신이 O를 ​​조회 테이블을 미리 계산하고있는 경우 (1)

:-) 모든 정수 I에 대한 I + b에 aN 가까이하게 N을 찾고 고려하지 않으면. 당신이 continued fractions 같은 뭔가를 찾고 될 수 있습니다처럼

Answer 3

먼저, b = 0이고 0 < < 1 인 간단한 경우를 생각해 봅시다. F (a, n) = | an-round (an) |

하자 step_size = 1

Step 1. Let v=a 
Step 2. Let period size p = upper_round(1/v). 
Step 3. Now, for n=1..p, there must be a number i such that F(v,i) < v. 
Step 4. v = F(v,i), step_size = stepsize * i 
Step 5. Go to step 2 

당신은 당신이 원하는 수준으로 F (V, *)를 줄일 수 있습니다 볼 수 있듯이. 최종 솔루션 n = step_size.

Answer 4

비율 a/b에 대한 연속 분수를 계산할 수 있습니다. 분모가 N보다 큰 경우 또는 근사값이 충분할 때 중지 할 수 있습니다.(이 N에 비해 여전히 작은 경우 또는 d1)

// Initialize: 
double ratio = a/b; 
int ak = (int)(ratio); 
double remainder = ratio - ak; 

int n0 = 1; 
int d0 = 0; 

int n1 = ak; 
int d1 = 1; 

do { 
    ratio = 1/remainder; 
    ak = (int)ratio; 
    int n2 = ak * n1 + n0; 
    int d2 = ak * d1 + d0; 
    n0 = n1; 
    d0 = d1; 
    n1 = n2; 
    d1 = d2; 
    remainder = ratio - ak; 
} while (d1 < N); 

당신이 찾고있는 n의 값은 d0입니다.

이것은 반드시 최소한의 해결책을 제시하지는 않지만 근사한 근사값입니다.