Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Okay, here's my answer using <a href="http://en.wikipedia.org/wiki/Continued_fraction">continued fractions</a> alone. </p> <p>First let's get some terminology here. </p> <p>Let X = p/q be the unknown fraction.</p> <p>Let Q(X,p/q) = sign(X - p/q) be the query function: if it is 0, we've guessed the number, and if it's +/- 1 that tells us the sign of our error.</p> <p>The <a href="http://en.wikipedia.org/wiki/Continued_fraction#Notations_for_continued_fractions">conventional notation for continued fractions</a> is A = [a<sub>0</sub>; a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ... a<sub>k</sub>] </p> <p>= a<sub>0</sub> + 1/(a<sub>1</sub> + 1/(a<sub>2</sub> + 1/(a<sub>3</sub> + 1/( ... + 1/a<sub>k</sub>) ... )))</p> <hr> <p>We'll follow the following algorithm for 0 &lt; p/q &lt; 1.</p> <ol> <li><p>Initialize Y = 0 = [ 0 ], Z = 1 = [ 1 ], k = 0.</p></li> <li><p><strong>Outer loop</strong>: The <em>preconditions</em> are that:</p> <ul> <li><p>Y and Z are continued fractions of k+1 terms which are identical except in the last element, where they differ by 1, so that Y = [y<sub>0</sub>; y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub>, ... y<sub>k</sub>] and Z = [y<sub>0</sub>; y<sub>1</sub>, y<sub>2</sub>, y<sub>3</sub>, ... y<sub>k</sub> + 1] </p></li> <li><p>(-1)<sup>k</sup>(Y-X) &lt; 0 &lt; (-1)<sup>k</sup>(Z-X), or in simpler terms, for k even, Y &lt; X &lt; Z and for k odd, Z &lt; X &lt; Y.</p></li> </ul></li> <li><p>Extend the degree of the continued fraction by 1 step without changing the values of the numbers. In general, if the last terms are y<sub>k</sub> and y<sub>k</sub> + 1, we change that to [... y<sub>k</sub>, y<sub>k+1</sub>=&#8734;] and [... y<sub>k</sub>, z<sub>k+1</sub>=1]. Now increase k by 1.</p></li> <li><p><strong>Inner loops</strong>: This is essentially the same as @templatetypedef's interview question about the integers. We do a two-phase binary search to get closer:</p></li> <li><p><strong>Inner loop 1</strong>: y<sub>k</sub> = &#8734;, z<sub>k</sub> = a, and X is between Y and Z.</p></li> <li><p>Double Z's last term: Compute M = Z but with m<sub>k</sub> = 2*a = 2*z<sub>k</sub>.</p></li> <li><p>Query the unknown number: q = Q(X,M).</p></li> <li><p>If q = 0, we have our answer and go to step 17 . </p></li> <li><p>If q and Q(X,Y) have opposite signs, it means X is between Y and M, so set Z = M and go to step 5. </p></li> <li><p>Otherwise set Y = M and go to the next step:</p></li> <li><p><strong>Inner loop 2.</strong> y<sub>k</sub> = b, z<sub>k</sub> = a, and X is between Y and Z.</p></li> <li><p>If a and b differ by 1, swap Y and Z, go to step 2.</p></li> <li><p>Perform a binary search: compute M where m<sub>k</sub> = floor((a+b)/2, and query q = Q(X,M).</p></li> <li><p>If q = 0, we're done and go to step 17.</p></li> <li><p>If q and Q(X,Y) have opposite signs, it means X is between Y and M, so set Z = M and go to step 11.</p></li> <li><p>Otherwise, q and Q(X,Z) have opposite signs, it means X is between Z and M, so set Y = M and go to step 11.</p></li> <li><p>Done: X = M. </p></li> </ol> <p>A concrete example for X = 16/113 = 0.14159292</p> <pre><code>Y = 0 = [0], Z = 1 = [1], k = 0 k = 1: Y = 0 = [0; &amp;#8734;] &lt; X, Z = 1 = [0; 1] &gt; X, M = [0; 2] = 1/2 &gt; X. Y = 0 = [0; &amp;#8734;], Z = 1/2 = [0; 2], M = [0; 4] = 1/4 &gt; X. Y = 0 = [0; &amp;#8734;], Z = 1/4 = [0; 4], M = [0; 8] = 1/8 &lt; X. Y = 1/8 = [0; 8], Z = 1/4 = [0; 4], M = [0; 6] = 1/6 &gt; X. Y = 1/8 = [0; 8], Z = 1/6 = [0; 6], M = [0; 7] = 1/7 &gt; X. Y = 1/8 = [0; 8], Z = 1/7 = [0; 7] --&gt; the two last terms differ by one, so swap and repeat outer loop. k = 2: Y = 1/7 = [0; 7, &amp;#8734;] &gt; X, Z = 1/8 = [0; 7, 1] &lt; X, M = [0; 7, 2] = 2/15 &lt; X Y = 1/7 = [0; 7, &amp;#8734;], Z = 2/15 = [0; 7, 2], M = [0; 7, 4] = 4/29 &lt; X Y = 1/7 = [0; 7, &amp;#8734;], Z = 4/29 = [0; 7, 4], M = [0; 7, 8] = 8/57 &lt; X Y = 1/7 = [0; 7, &amp;#8734;], Z = 8/57 = [0; 7, 8], M = [0; 7, 16] = 16/113 = X --&gt; done! </code></pre> <p>At each step of computing M, the range of the interval reduces. It is probably fairly easy to prove (though I won't do this) that the interval reduces by a factor of at least 1/sqrt(5) at each step, which would show that this algorithm is O(log q) steps.</p> <p>Note that this can be combined with templatetypedef's original interview question and apply towards <em>any</em> rational number p/q, not just between 0 and 1, by first computing Q(X,0), then for either positive/negative integers, bounding between two consecutive integers, and then using the above algorithm for the fractional part.</p> <p>When I have a chance next, I will post a python program that implements this algorithm.</p> <p><strong>edit</strong>: also, note that you don't have to compute the continued fraction each step (which would be O(k), there are partial approximants to continued fractions that can compute the next step from the previous step in O(1).)</p> <p><strong>edit 2</strong>: Recursive definition of partial approximants:</p> <p>If A<sub>k</sub> = [a<sub>0</sub>; a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ... a<sub>k</sub>] = p<sub>k</sub>/q<sub>k</sub>, then p<sub>k</sub> = a<sub>k</sub>p<sub>k-1</sub> + p<sub>k-2</sub>, and q<sub>k</sub> = a<sub>k</sub>q<sub>k-1</sub> + q<sub>k-2</sub>. (Source: Niven &amp; Zuckerman, 4th ed, Theorems 7.3-7.5. See also <a href="http://en.wikipedia.org/wiki/Fundamental_recurrence_formulas">Wikipedia</a>) </p> <p>Example: [0] = 0/1 = p<sub>0</sub>/q<sub>0</sub>, [0; 7] = 1/7 = p<sub>1</sub>/q<sub>1</sub>; so [0; 7, 16] = (16*1+0)/(16*7+1) = 16/113 = p<sub>2</sub>/q<sub>2</sub>.</p> <p>This means that if two continued fractions Y and Z have the same terms except the last one, and the continued fraction excluding the last term is p<sub>k-1</sub>/q<sub>k-1</sub>, then we can write Y = (y<sub>k</sub>p<sub>k-1</sub> + p<sub>k-2</sub>) / (y<sub>k</sub>q<sub>k-1</sub> + q<sub>k-2</sub>) and Z = (z<sub>k</sub>p<sub>k-1</sub> + p<sub>k-2</sub>) / (z<sub>k</sub>q<sub>k-1</sub> + q<sub>k-2</sub>). It should be possible to show from this that |Y-Z| decreases by at least a factor of 1/sqrt(5) at each smaller interval produced by this algorithm, but the algebra seems to be beyond me at the moment. :-(</p> <p>Here's my Python program:</p> <pre><code>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 &lt; p0/q0, then Q() = 1; if p/q &lt; 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 '&lt;' if s&lt;0 else '&gt;' if s&gt;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 &lt; 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] </code></pre> <p>and a sample output for <code>ratguess(makeQ(33102,113017), True, 20)</code>:</p> <pre><code>p/q=[0]=0/1 None:2:1 0/1 &lt; X &lt; 1/1, interval=1.0; M=1/2 &gt; X None:4:2 0/1 &lt; X &lt; 1/2, interval=0.5; M=1/4 &lt; X 4:3:2 1/4 &lt; X &lt; 1/2, interval=0.25; M=1/3 &gt; X p/q=[0, 3]=1/3 None:2:1 1/3 &gt; X &gt; 1/4, interval=0.0833333333333; M=2/7 &lt; X None:4:2 1/3 &gt; X &gt; 2/7, interval=0.047619047619; M=4/13 &gt; X 4:3:2 4/13 &gt; X &gt; 2/7, interval=0.021978021978; M=3/10 &gt; X p/q=[0, 3, 2]=2/7 None:2:1 2/7 &lt; X &lt; 3/10, interval=0.0142857142857; M=5/17 &gt; X None:4:2 2/7 &lt; X &lt; 5/17, interval=0.00840336134454; M=9/31 &lt; X 4:3:2 9/31 &lt; X &lt; 5/17, interval=0.00379506641366; M=7/24 &lt; X p/q=[0, 3, 2, 2]=5/17 None:2:1 5/17 &gt; X &gt; 7/24, interval=0.00245098039216; M=12/41 &lt; X None:4:2 5/17 &gt; X &gt; 12/41, interval=0.00143472022956; M=22/75 &gt; X 4:3:2 22/75 &gt; X &gt; 12/41, interval=0.000650406504065; M=17/58 &gt; X p/q=[0, 3, 2, 2, 2]=12/41 None:2:1 12/41 &lt; X &lt; 17/58, interval=0.000420521446594; M=29/99 &gt; X None:4:2 12/41 &lt; X &lt; 29/99, interval=0.000246366100025; M=53/181 &lt; X 4:3:2 53/181 &lt; X &lt; 29/99, interval=0.000111613371282; M=41/140 &lt; X p/q=[0, 3, 2, 2, 2, 2]=29/99 None:2:1 29/99 &gt; X &gt; 41/140, interval=7.21500721501e-05; M=70/239 &lt; X None:4:2 29/99 &gt; X &gt; 70/239, interval=4.226364059e-05; M=128/437 &gt; X 4:3:2 128/437 &gt; X &gt; 70/239, interval=1.91492009996e-05; M=99/338 &gt; X p/q=[0, 3, 2, 2, 2, 2, 2]=70/239 None:2:1 70/239 &lt; X &lt; 99/338, interval=1.23789953207e-05; M=169/577 &gt; X None:4:2 70/239 &lt; X &lt; 169/577, interval=7.2514738621e-06; M=309/1055 &lt; X 4:3:2 309/1055 &lt; X &lt; 169/577, interval=3.28550190148e-06; M=239/816 &lt; X p/q=[0, 3, 2, 2, 2, 2, 2, 2]=169/577 None:2:1 169/577 &gt; X &gt; 239/816, interval=2.12389981991e-06; M=408/1393 &lt; X None:4:2 169/577 &gt; X &gt; 408/1393, interval=1.24415093544e-06; M=746/2547 &lt; X None:8:4 169/577 &gt; X &gt; 746/2547, interval=6.80448470014e-07; M=1422/4855 &lt; X None:16:8 169/577 &gt; X &gt; 1422/4855, interval=3.56972657711e-07; M=2774/9471 &gt; X 16:12:8 2774/9471 &gt; X &gt; 1422/4855, interval=1.73982239227e-07; M=2098/7163 &gt; X 12:10:8 2098/7163 &gt; X &gt; 1422/4855, interval=1.15020646951e-07; M=1760/6009 &gt; X 10:9:8 1760/6009 &gt; X &gt; 1422/4855, interval=6.85549088053e-08; M=1591/5432 &lt; X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9]=1591/5432 None:2:1 1591/5432 &lt; X &lt; 1760/6009, interval=3.06364213998e-08; M=3351/11441 &lt; X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1]=1760/6009 None:2:1 1760/6009 &gt; X &gt; 3351/11441, interval=1.45456726663e-08; M=5111/17450 &lt; X None:4:2 1760/6009 &gt; X &gt; 5111/17450, interval=9.53679318849e-09; M=8631/29468 &lt; X None:8:4 1760/6009 &gt; X &gt; 8631/29468, interval=5.6473816179e-09; M=15671/53504 &lt; X None:16:8 1760/6009 &gt; X &gt; 15671/53504, interval=3.11036635336e-09; M=29751/101576 &gt; X 16:12:8 29751/101576 &gt; X &gt; 15671/53504, interval=1.47201634215e-09; M=22711/77540 &gt; X 12:10:8 22711/77540 &gt; X &gt; 15671/53504, interval=9.64157420569e-10; M=19191/65522 &gt; X 10:9:8 19191/65522 &gt; X &gt; 15671/53504, interval=5.70501257346e-10; M=17431/59513 &gt; X p/q=[0, 3, 2, 2, 2, 2, 2, 2, 9, 1, 8]=15671/53504 None:2:1 15671/53504 &lt; X &lt; 17431/59513, interval=3.14052228667e-10; M=33102/113017 == X </code></pre> <p>Since Python handles biginteger math from the start, and this program uses only integer math (except for the interval calculations), it should work for arbitrary rationals.</p> <hr> <p><strong>edit 3</strong>: Outline of proof that this is O(log q), not O(log^2 q):</p> <p>First note that until the rational number is found, the # of steps n<sub>k</sub> for each new continued fraction term is <em>exactly</em> 2b(a_k)-1 where b(a_k) is the # of bits needed to represent a_k = ceil(log2(a_k)): it's b(a_k) steps to widen the "net" of the binary search, and b(a_k)-1 steps to narrow it). See the example above, you'll note that the # of steps is always 1, 3, 7, 15, etc.</p> <p>Now we can use the recurrence relation q<sub>k</sub> = a<sub>k</sub>q<sub>k-1</sub> + q<sub>k-2</sub> and induction to prove the desired result.</p> <p>Let's state it in this way: that the value of q after the N<sub>k</sub> = sum(n<sub>k</sub>) steps required for reaching the kth term has a minimum: q >= A*2<sup>cN</sup> for some fixed constants A,c. (so to invert, we'd get that the # of steps N is &lt;= (1/c) * log<sub>2</sub> (q/A) = O(log q).)</p> <p>Base cases: </p> <ul> <li>k=0: q = 1, N = 0, so q >= 2<sup>N</sup></li> <li>k=1: for N = 2b-1 steps, q = a<sub>1</sub> >= 2<sup>b-1</sup> = 2<sup>(N-1)/2</sup> = 2<sup>N/2</sup>/sqrt(2). </li> </ul> <p>This implies A = 1, c = 1/2 could provide desired bounds. In reality, q may <em>not</em> double each term (counterexample: [0; 1, 1, 1, 1, 1] has a growth factor of phi = (1+sqrt(5))/2) so let's use c = 1/4. </p> <p>Induction:</p> <ul> <li><p>for term k, q<sub>k</sub> = a<sub>k</sub>q<sub>k-1</sub> + q<sub>k-2</sub>. Again, for the n<sub>k</sub> = 2b-1 steps needed for this term, a<sub>k</sub> >= 2<sup>b-1</sup> = 2<sup>(n<sub>k</sub>-1)/2</sup>.</p> <p>So a<sub>k</sub>q<sub>k-1</sub> >= 2<sup>(N<sub>k</sub>-1)/2</sup> * q<sub>k-1</sub> >= 2<sup>(n<sub>k</sub>-1)/2</sup> * A*2<sup>N<sub>k-1</sub>/4</sup> = A*2<sup>N<sub>k</sub>/4</sup>/sqrt(2)*2<sup>n<sub>k</sub>/4</sup>.</p></li> </ul> <p>Argh -- the tough part here is that if a<sub>k</sub> = 1, q may not increase much for that one term, and we need to use q<sub>k-2</sub> but that may be much smaller than q<sub>k-1</sub>.</p>
    singulars
    1. This table or related slice is empty.
    1. POThe "guess the number" game for arbitrary rational numbers?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJason S
    1. USJason S
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POThe "guess the number" game for arbitrary rational numbers?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COSo this looks really great, but I don't think it's O(lg q). Any individual iteration of the inner loop runs in O(lg q) steps as you use the modified binary search to recover the next number of the continued fraction, but remember that there are O(lg q) iterations of that loop since there are (in the worst case) O(lg q) numbers in the partial fraction. That makes me think that this is O(lg^2 q) time instead. However, this is still an excellent solution to the problem, and whether it's O(lg q) or O(lg^2 q) time it's still exponentially better than what I had before.
      singulars
      1. PO
      1. UStemplatetypedef
    2. COI know it looks like O(lg^2 q) because of the two loops, but that's probably conservative. I'll try to prove it.
      singulars
      1. PO
      1. USJason S
    3. CO+1: Didn't check the details, but I now believe the CF approach will work.
      singulars
      1. PO
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload