さて、これが連分数だけを使った私の答えです。
まず、ここでいくつかの用語を取得しましょう。
X = p/qを未知の分数とします。
Q（X、p / q）= sign（X --p / q）をクエリ関数とします。0の場合は数値を推測し、+/-1の場合はエラーの兆候を示します。 。
連分数の従来の表記法はA=[a 0 ; a 1、a 2、a 3、... a k ]
= a 0 + 1 /（a 1 + 1 /（a 2 + 1 /（a 3 + 1 /（... + 1 / a k）...）））
0 <p / q <1の場合は、次のアルゴリズムに従います。
Y = 0 = [0]、Z = 1 = [1]、k=0を初期化します。
外側のループ：前提条件は次のとおりです。
数値の値を変更せずに、連分数の次数を1ステップ拡張します。一般に、最後の項がykおよびyk + 1の場合、それを[... y k、y k +1 =∞]および[... yk、z k + 1 =1]に変更します。ここで、kを1増やします。
内部ループ：これは、整数に関する@templatetypedefのインタビューの質問と本質的に同じです。近づけるために、2段階の二分探索を行います。
内部ループ1：y k =∞、z k = a、XはYとZの間にあります。
Zの最後の項を2倍にします。M=Zを計算しますが、m k = 2 * a = 2 *zkを使用します。
未知数を照会します：q = Q（X、M）。
q = 0の場合、答えが得られ、ステップ17に進みます。
qとQ（X、Y）の符号が反対の場合は、XがYとMの間にあることを意味するため、Z = Mに設定して、手順5に進みます。
それ以外の場合は、Y = Mに設定し、次の手順に進みます。
内部ループ2。yk =b、z k = a、XはYとZの間にあります。
aとbの差が1の場合は、YとZを入れ替えて、手順2に進みます。
二分探索を実行します。Mを計算します。ここで、m k = floor（（a + b）/ 2、およびクエリq = Q（X、M）です。
q = 0の場合、これで完了です。手順17に進みます。
qとQ（X、Y）の符号が反対の場合は、XがYとMの間にあることを意味するため、Z = Mに設定して、手順11に進みます。
それ以外の場合、qとQ（X、Z）の符号は逆になります。つまり、XはZとMの間にあるため、Y = Mに設定して、手順11に進みます。
完了：X=M。
X = 16/113=0.14159292の具体例
Y = 0 = [0], Z = 1 = [1], k = 0
k = 1:
Y = 0 = [0; ∞] < X, Z = 1 = [0; 1] > X, M = [0; 2] = 1/2 > X.
Y = 0 = [0; ∞], Z = 1/2 = [0; 2], M = [0; 4] = 1/4 > X.
Y = 0 = [0; ∞], Z = 1/4 = [0; 4], M = [0; 8] = 1/8 < X.
Y = 1/8 = [0; 8], Z = 1/4 = [0; 4], M = [0; 6] = 1/6 > X.
Y = 1/8 = [0; 8], Z = 1/6 = [0; 6], M = [0; 7] = 1/7 > X.
Y = 1/8 = [0; 8], Z = 1/7 = [0; 7]
--> the two last terms differ by one, so swap and repeat outer loop.
k = 2:
Y = 1/7 = [0; 7, ∞] > X, Z = 1/8 = [0; 7, 1] < X,
M = [0; 7, 2] = 2/15 < X
Y = 1/7 = [0; 7, ∞], Z = 2/15 = [0; 7, 2],
M = [0; 7, 4] = 4/29 < X
Y = 1/7 = [0; 7, ∞], Z = 4/29 = [0; 7, 4],
M = [0; 7, 8] = 8/57 < X
Y = 1/7 = [0; 7, ∞], Z = 8/57 = [0; 7, 8],
M = [0; 7, 16] = 16/113 = X
--> done!
Mを計算する各ステップで、間隔の範囲が狭くなります。間隔が各ステップで少なくとも1/sqrt（5）の係数で減少することを証明するのはおそらくかなり簡単です（これは行いませんが）。これは、このアルゴリズムがO（log q）ステップであることを示します。
これはtemplatetypedefの元のインタビューの質問と組み合わせて、最初にQ（X、0）を計算し、次に正/負の整数のいずれかに対して、2つの連続する間に境界を置くことにより、0と1の間だけでなく、任意の有理数p/qに適用できることに注意してください。整数、そして小数部に上記のアルゴリズムを使用します。
次に機会があれば、このアルゴリズムを実装するPythonプログラムを投稿します。
編集：また、各ステップで連分数を計算する必要がないことに注意してください（O（k）になります。O（1）の前のステップから次のステップを計算できる連分数の部分的な近似があります。 ）。
編集2：部分近似の再帰的定義：
A k =[ a0 ;の場合 a 1、a 2、a 3、... a k ] = p k / q k、次にp k = a k p k-1 + p k-2、およびq k = a k q k-1 + q k-2。（出典：Niven＆Zuckerman、第4版、定理7.3-7.5。ウィキペディアも参照）
例：[0] = 0/1 = p 0 / q 0、[0; 7] = 1/7 = p 1 / q 1 ; だから[0; 7、16] =（16 * 1 + 0）/（16 * 7 + 1）= 16/113 = p 2 / q2 。
これは、2つの連分数YとZが最後の項を除いて同じ項を持ち、最後の項を除いた連分数がp k-1 / q k-1である場合、Y =（y k p k- 1 + p k-2）/（y k q k-1 + q k-2）およびZ =（z k p k-1 + p k-2）/（z k q k-1 + q k-2）。これから|YZ|を示すことができるはずです。このアルゴリズムによって生成される小さな間隔ごとに、少なくとも1 / sqrt（5）の係数で減少しますが、代数は現時点では私を超えているようです。:-(
これが私のPythonプログラムです：
import math
# Return a function that returns Q(p0/q0,p/q)
# = sign(p0/q0-p/q) = sign(p0q-q0p)*sign(q0*q)
# If p/q < p0/q0, then Q() = 1; if p/q < p0/q0, then Q() = -1; otherwise Q()=0.
def makeQ(p0,q0):
def Q(p,q):
return cmp(q0*p,p0*q)*cmp(q0*q,0)
return Q
def strsign(s):
return '<' if s<0 else '>' if s>0 else '=='
def cfnext(p1,q1,p2,q2,a):
return [a*p1+p2,a*q1+q2]
def ratguess(Q, doprint, kmax):
# p2/q2 = p[k-2]/q[k-2]
p2 = 1
q2 = 0
# p1/q1 = p[k-1]/q[k-1]
p1 = 0
q1 = 1
k = 0
cf = [0]
done = False
while not done and (not kmax or k < kmax):
if doprint:
print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1)
# extend continued fraction
k = k + 1
[py,qy] = [p1,q1]
[pz,qz] = cfnext(p1,q1,p2,q2,1)
ay = None
az = 1
sy = Q(py,qy)
sz = Q(pz,qz)
while not done:
if doprint:
out = str(py)+'/'+str(qy)+' '+strsign(sy)+' X '
out += strsign(-sz)+' '+str(pz)+'/'+str(qz)
out += ', interval='+str(abs(1.0*py/qy-1.0*pz/qz))
if ay:
if (ay - az == 1):
[p0,q0,a0] = [pz,qz,az]
break
am = (ay+az)/2
else:
am = az * 2
[pm,qm] = cfnext(p1,q1,p2,q2,am)
sm = Q(pm,qm)
if doprint:
out = str(ay)+':'+str(am)+':'+str(az) + ' ' + out + '; M='+str(pm)+'/'+str(qm)+' '+strsign(sm)+' X '
print out
if (sm == 0):
[p0,q0,a0] = [pm,qm,am]
done = True
break
elif (sm == sy):
[py,qy,ay,sy] = [pm,qm,am,sm]
else:
[pz,qz,az,sz] = [pm,qm,am,sm]
[p2,q2] = [p1,q1]
[p1,q1] = [p0,q0]
cf += [a0]
print 'p/q='+str(cf)+'='+str(p1)+'/'+str(q1)
return [p1,q1]
およびのサンプル出力ratguess(makeQ(33102,113017), True, 20)：
p/q=[0]=0/1
None:2:1 0/1 < X < 1/1, interval=1.0; M=1/2 > X
None:4:2 0/1 < X < 1/2, interval=0.5; M=1/4 < X
4:3:2 1/4 < X < 1/2, interval=0.25; M=1/3 > X
p/q=[0, 3]=1/3
None:2:1 1/3 > X > 1/4, interval=0.0833333333333; M=2/7 < X
None:4:2 1/3 > X > 2/7, interval=0.047619047619; M=4/13 > X
4:3:2 4/13 > X > 2/7, interval=0.021978021978; M=3/10 > X
p/q=[0, 3, 2]=2/7
None:2:1 2/7 < X < 3/10, interval=0.0142857142857; M=5/17 > X
None:4:2 2/7 < X < 5/17, interval=0.00840336134454; M=9/31 < X
4:3:2 9/31 < X < 5/17, interval=0.00379506641366; M=7/24 < X
p/q=[0, 3, 2, 2]=5/17
None:2:1 5/17 > X > 7/24, interval=0.00245098039216; M=12/41 < X
None:4:2 5/17 > X > 12/41, interval=0.00143472022956; M=22/75 > X
4:3:2 22/75 > X > 12/41, interval=0.000650406504065; M=17/58 > X
p/q=[0, 3, 2, 2, 2]=12/41
None:2:1 12/41 < X < 17/58, interval=0.000420521446594; M=29/99 > X
None:4:2 12/41 < X < 29/99, interval=0.000246366100025; M=53/181 < X
4:3:2 53/181 < X < 29/99, interval=0.000111613371282; M=41/140 < X
p/q=[0, 3, 2, 2, 2, 2]=29/99
None:2:1 29/99 > X > 41/140, interval=7.21500721501e-05; M=70/239 < X
None:4:2 29/99 > X > 70/239, interval=4.226364059e-05; M=128/437 > X
4:3:2 128/437 > X > 70/239, interval=1.91492009996e-05; M=99/338 > X
p/q=[0, 3, 2, 2, 2, 2, 2]=70/239
None:2:1 70/239 < X < 99/338, interval=1.23789953207e-05; M=169/577 > X
None:4:2 70/239 < X < 169/577, interval=7.2514738621e-06; M=309/1055 < X
4:3:2 309/1055 < X < 169/577, interval=3.28550190148e-06; M=239/816 < X
p/q=[0, 3, 2, 2, 2, 2, 2, 2]=169/577
None:2:1 169/577 > X > 239/816, interval=2.12389981991e-06; M=408/1393 < X
None:4:2 169/577 > X > 408/1393, interval=1.24415093544e-06; M=746/2547 < X
None:8:4 169/577 > X > 746/2547, interval=6.80448470014e-07; M=1422/4855 < X
None:16:8 169/577 > X > 1422/4855, interval=3.56972657711e-07; M=2774/9471 > X
16:12:8 2774/9471 > X > 1422/4855, interval=1.73982239227e-07; M=2098/7163 > X
12:10:8 2098/7163 > X > 1422/4855, interval=1.15020646951e-07; M=1760/6009 > X
10:9:8 1760/6009 > X > 1422/4855, interval=6.85549088053e-08; M=1591/5432 < X
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9]=1591/5432
None:2:1 1591/5432 < X < 1760/6009, interval=3.06364213998e-08; M=3351/11441 < X
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1]=1760/6009
None:2:1 1760/6009 > X > 3351/11441, interval=1.45456726663e-08; M=5111/17450 < X
None:4:2 1760/6009 > X > 5111/17450, interval=9.53679318849e-09; M=8631/29468 < X
None:8:4 1760/6009 > X > 8631/29468, interval=5.6473816179e-09; M=15671/53504 < X
None:16:8 1760/6009 > X > 15671/53504, interval=3.11036635336e-09; M=29751/101576 > X
16:12:8 29751/101576 > X > 15671/53504, interval=1.47201634215e-09; M=22711/77540 > X
12:10:8 22711/77540 > X > 15671/53504, interval=9.64157420569e-10; M=19191/65522 > X
10:9:8 19191/65522 > X > 15671/53504, interval=5.70501257346e-10; M=17431/59513 > X
p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1, 8]=15671/53504
None:2:1 15671/53504 < X < 17431/59513, interval=3.14052228667e-10; M=33102/113017 == X
Pythonは最初からbiginteger数学を処理し、このプログラムは整数数学（区間計算を除く）のみを使用するため、任意の有理数で機能するはずです。
編集3：これがO（log ^ 2 q）ではなくO（log q）であることの証明の概要：
最初に、有理数が見つかるまで、新しい連分数項ごとのステップ数n kは正確に2b（a_k）-1であることに注意してください。ここで、b（a_k）はa_k = ceil（log2（a_k）を表すために必要なビット数です。 ））：バイナリ検索の「ネット」を広げるにはb（a_k）ステップ、狭くするにはb（a_k）-1ステップです）。上記の例を参照してください。ステップ数は常に1、3、7、15などです。
これで、漸化式q k = a k q k-1 + q k-2と帰納法を使用して、目的の結果を証明できます。
このように述べましょう。k番目の項に到達するために必要なNk = sum（n k ）ステップ後のqの値は、最小値を持ちます。いくつかの固定定数A、cに対してq> = A * 2cN 。（逆にすると、ステップ数Nは<=（1 / c）* log 2（q / A）= O（log q）になります。）
基本ケース：
- k = 0：q = 1、N = 0、つまりq> = 2 N
- k = 1：N = 2b-1ステップの場合、q = a 1 > = 2 b-1 = 2 （N-1）/ 2 = 2 N / 2 / sqrt（2）。
これは、A = 1、c=1/2が望ましい境界を提供できることを意味します。実際には、qは各項を2倍にすることはできません（反例：[0; 1、1、1、1、1]の成長因子はphi =（1 + sqrt（5））/ 2）ので、c =1/を使用しましょう。 4.4。
誘導：
項kの場合、q k = a k q k-1 +qk -2。この場合も、この項に必要なn k = 2b-1ステップの場合、a k > = 2 b-1 = 2 （n k -1）/2です。
したがって、a k q k-1 > = 2 （N k -1）/ 2 * q k-1 > = 2 （n k -1）/ 2 * A * 2 N k-1 / 4 = A * 2 N k / 4 / sqrt（2）* 2 n k /4。
ああ-ここで難しいのは、a k = 1の場合、qはその1つの項であまり増加しない可能性があり、q k-2を使用する必要がありますが、それはqk -1よりもはるかに小さい可能性があります。