StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let's take the rational numbers, in reduced form, and write them out in order first of denominator, then numerator.</p> <pre><code>1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, ... </code></pre> <p>Our first guess is going to be <code>1/2</code>. Then we'll go along the list until we have 3 in our range. Then we will take 2 guesses to search that list. Then we'll go along the list until we have 7 in our remaining range. Then we will take 3 guesses to search that list. And so on.</p> <p>In <code>n</code> steps we'll cover the first <code>2<sup>O(n)</sup></code> possibilities, which is in the order of magnitude of efficiency that you were looking for. </p> <p><strong>Update:</strong> People didn't get the reasoning behind this. The reasoning is simple. We know how to walk a binary tree efficiently. There are <code>O(n<sup>2</sup>)</code> fractions with maximum denominator <code>n</code>. We could therefore search up to any particular denominator size in <code>O(2*log(n)) = O(log(n))</code> steps. The problem is that we have an infinite number of possible rationals to search. So we can't just line them all up, order them, and start searching.</p> <p>Therefore my idea was to line up a few, search, line up more, search, and so on. Each time we line up more we line up about double what we did last time. So we need one more guess than we did last time. Therefore our first pass uses 1 guess to traverse 1 possible rational. Our second uses 2 guesses to traverse 3 possible rationals. Our third uses 3 guesses to traverse 7 possible rationals. And our <code>k</code>'th uses <code>k</code> guesses to traverse <code>2<sup>k</sup>-1</code> possible rationals. For any particular rational <code>m/n</code>, eventually it will wind up putting that rational on a fairly big list that it knows how to do a binary search on efficiently.</p> <p>If we did binary searches, then ignored everything we'd learned when we grab more rationals, then we'd put all of the rationals up to and including <code>m/n</code> in <code>O(log(n))</code> passes. (That's because by that point we'll get to a pass with enough rationals to include every rational up to and including <code>m/n</code>.) But each pass takes more guesses, so that would be <code>O(log(n)<sup>2</sup>)</code> guesses.</p> <p><em>However</em> we actually do a lot better than that. With our first guess, we eliminate half the rationals on our list as being too big or small. Our next two guesses don't quite cut the space into quarters, but they don't come too far from it. Our next 3 guesses again don't quite cut the space into eighths, but they don't come too far from it. And so on. When you put it together, I'm convinced that the result is that you find <code>m/n</code> in <code>O(log(n))</code> steps. Though I don't actually have a proof.</p> <p><strong>Try it out:</strong> Here is code to generate the guesses so that you can play and see how efficient it is.</p> <pre><code>#! /usr/bin/python from fractions import Fraction import heapq import readline import sys def generate_next_guesses (low, high, limit): upcoming = [(low.denominator + high.denominator, low.numerator + high.numerator, low.denominator, low.numerator, high.denominator, high.numerator)] guesses = [] while len(guesses) < limit: (mid_d, mid_n, low_d, low_n, high_d, high_n) = upcoming[0] guesses.append(Fraction(mid_n, mid_d)) heapq.heappushpop(upcoming, (low_d + mid_d, low_n + mid_n, low_d, low_n, mid_d, mid_n)) heapq.heappush(upcoming, (mid_d + high_d, mid_n + high_n, mid_d, mid_n, high_d, high_n)) guesses.sort() return guesses def ask (num): while True: print "Next guess: {0} ({1})".format(num, float(num)) if 1 < len(sys.argv): wanted = Fraction(sys.argv[1]) if wanted < num: print "too high" return 1 elif num < wanted: print "too low" return -1 else: print "correct" return 0 answer = raw_input("Is this (h)igh, (l)ow, or (c)orrect? ") if answer == "h": return 1 elif answer == "l": return -1 elif answer == "c": return 0 else: print "Not understood. Please say one of (l, c, h)" guess_size_bound = 2 low = Fraction(0) high = Fraction(1) guesses = [Fraction(1,2)] required_guesses = 0 answer = -1 while 0 != answer: if 0 == len(guesses): guess_size_bound *= 2 guesses = generate_next_guesses(low, high, guess_size_bound - 1) #print (low, high, guesses) guess = guesses[len(guesses)/2] answer = ask(guess) required_guesses += 1 if 0 == answer: print "Thanks for playing!" print "I needed %d guesses" % required_guesses elif 1 == answer: high = guess guesses[len(guesses)/2:] = [] else: low = guess guesses[0:len(guesses)/2 + 1] = [] </code></pre> <p>As an example to try it out I tried 101/1024 (0.0986328125) and found that it took 20 guesses to find the answer. I tried 0.98765 and it took 45 guesses. I tried 0.0123456789 and it needed 66 guesses and about a second to generate them. (Note, if you call the program with a rational number as an argument, it will fill in all of the guesses for you. This is a very helpful convenience.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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