You have been abducted by a sadistic math wizard (don’t you hate it when that happens?). He ushers you into a plain but cozy-looking room, with a hardwood floor, a few exotic-looking rugs, and wood paneling on the walls.
He hands you a small polished metal cube. “Inside this cube”, he explains, “is a positive rational number. If you can correctly tell me its numerator and denominator in lowest terms, I will let you go free. If you guess wrong, though…” He pauses to indulge in an evil chuckle. “Let’s just say that my sharks are hoping you will fail.” He strides out and slams the door behind him.
Of course you try to open the cube, but you can’t find any way to do it: you don’t see any hinges, or a lid, or even any kind of seam at all, just smooth metal. You try throwing it on the floor to see if it will shatter, but you only succeed in denting the floor. You next try the door, but of course it is locked, and seems extremely solid.
You sigh and start to look around the room. There are no windows, but you quickly notice that a few of the wooden panels have various holes, knobs, and inscriptions on them. You go to examine them more closely.
On the west wall is a panel labelled “RECIPROCATOR”. To one side there is a square hole labelled with the letter 
On the north wall is a panel labelled “ARITHMETIZER”. There are three square holes: one labelled 
The east wall has no panels, but it does have a window with a stunning view of the forest you were hiking in just a few hours ago. You realize, belatedly, that the stories that crazy old man at the lodge told about the “haunted math forest” may have had some truth to them after all.
On the south wall is a panel labelled “COMPARATOR”, with two holes labelled 
In the middle of the room is a small table with a chair and a lamp. On the desk, it looks like the wizard has thoughtfully provided you with a quill, a pot of ink, and a stack of blank paper. You have the first few ticklings of some ideas, so you sit down at the desk, look thoughtfully at the ceiling for a few seconds, then begin to write.
Can you escape? Or will you be feeding the sharks? What’s your best strategy?
Steel cube photograph by Zai Divecha
The Math Less Traveled 
I’ll get the ball rolling with a bad solution. I can create 1 as x(1/x), so I can create any positive integer by adding successive 1’s. Therefore I can create any positive rational using the division function. So I’ll just enumerate the positive rationals and start trying them…after some finite (but potentially very large) number of tries, I’ll find the right one, which I’ll recognize because I get the giant “F” from the comparator for both x<y and y<x.
If I'm interested in not dying of old age or going insane, I'll probably think about continued fractions instead.
I agree that your first solution is not a good one (there is no guarantee that the process would terminate). My second idea is similarly problematic: use bisection to hone in on
(we can construct any dyadic rational, then compare away). Again, this won’t generally terminate.
On the other hand, my first thought was continued fractions (I went on to the second thought because I didn’t want to think about implementation, but it seem to be absolutely the right idea). This makes sense, as a number is rational if and only if it has a terminating continued fraction expansion, so we just have to work out what that expansion is.
Thinking in terms of subroutines required, we’ll need a way of getting integer and fractional parts—the rest is just(!) arithmetic. The integer part of a number
can be found by comparing 
to the natural numbers (which can be constructed recursively as you describe, starting with 1—some kind of bisection argument will make things go faster), and the fractional part is just 
minus the integer part. Iterate the usual algorithm for finding a continued fraction expansion until the fractional part is zero, then work out the arithmetic to recover the original number.
My bad method is guaranteed to terminate, unlike bisection. As soon as the target rational is chosen, and an enumeration of the rationals is fixed, we (the omniscient we) immediately know the target number’s position in the enumeration, and thus how many tries the prisoner will need to find it.
The downside is that it’s not guaranteed to terminate in any bounded time. (The prisoner knows N exists and is finite, but has no idea how big N may be.) However, my gut insists that’ll be a limitation of any method. I’m interested in hearing what we come up with for formally deciding that one method is better than another, and by how much. I suspect it’ll depend on how the wizard chooses the target rational, since there’s no uniform distribution.
That works! Of course you’re right that it’s not the fastest.
I’ll get the ball and propose two variants based on continued fractions, as I’d like to go out before the heat death of the universe.
As said previously, with x and 1/x, we can create 1, and from here every rational. I’m only interested by the integers.
Also, I can test equality between any x and y, as stated in the previous comment.
Last note: given x, either x = 1 (in that case I can test it, and exit the room), or one of x and 1/x is > 1, and *I know which one*.
Now we have x = p/q > 1.
The goal is to find the integer a > 1 such that a < x a. If so, we double a and try again. Eventually, we will find k such that 2^k < x <= 2^(k+1). If the equality holds, we are done, and we found x.
Otherwise, we then find by dichotomy of this interval the integer a such that a < x <= a+1 holds.
With both methods, we now have an integer a such that a < x 1, and we can start again recursively, until we find the exact rational value of x’, by recursion. Then we know the exact value of x = 1/x’ + a.
Now, for the analysis of the complexity.
With both variant proposed, the number of recursions steps needed is proportional to the “length” of the continued fraction expansion of x ; and the complexity of each individual step is the complexity of finding the good ‘a’ integer. This complexity depends only on the actual value of a itself, that is the value of the coefficient of the continued fraction expansion at this level.
Now, we know that, for a rational number, the “length” (or “depth”) of its CFE is always < log(q)/log(phi)+1 = O(log(q)), where phi is the golden ratio (cf. Wikipedia for example).
Now, for the complexity of the variants, where we are looking for the number a.
For the first variant, the analysis is simple: we need O(a) steps.
For the second variant, when we first widen the intervals, we do that O(log(a)) times, and after the dichotomy in an interval of length O(log(a)) costs O(log(log(a)). So the overal complexity is O(log(a)).
Now, we know that the value of a for each step is the coefficient in the CFE of a rational number, which is at any level is < q (expect maybe the very first one, which is < p).
All together, it means that the complexity of the first variant of the algorithm is O(q*log(q) + p).
And for the second variant O(log(q)^2 + log(p)).
I'm curious if that's the best we can do, though…. My guts tell me yes…
Very nice! Although it looks like maybe some of your comment got omitted? I’m guessing probably due to less than and greater than signs being interpreted as HTML tags and stripped out. If you write > in place of > and < in place of < they will stick around.
Indeed, it looks like whole paragraphs have disappeared 😦 …..
For a math blog, maybe you’d want to disable HTML yeas, but be sure to enable the and = symbols. Which are quite common in math :-). I’m quite sure the culprit here is either Akismet, or the WordPress comment parameters themselves, configured to strip HTML, as opposed to authorize text-only comments.
Also, maybe you could enable LaTeX syntax in the comments 🙂 : $$\int_\mathbb{R} e^{-x^2} \mathrm{d}x = \sqrt{\pi}$$
My 2 cents :-).
I’m not sure how much control I have over the HTML escaping in comments, since the blog is hosted on wordpress.com. But LaTeX syntax already is enabled in the comments! You just have to enclose things in
$ latex ...$, but without the space in between the dollar sign and the l. Like this:Let
be the searched number.
– If we want, we can make infinite copies of every number that we already have.
– We can test for equality (by comparing
with 
and 
with 
)
– We can construct
and 
(and also all the integers and rational numbers if we need to).
– We can negate a number and test if it is negative or positive. So the sadistic math wizard made it a bit easier then necessary for us by stating that the searched number is positive. That wouldn’t have been necessary.
– If we know a number to be an integer we can find it relatively fast by comparing it to
, 
, 
, 
and so on and then doing a binary search.
– We have all the operations needed for an Euclidean algorithm (note that we don’t need a modulo operation for it, we can just continue to subtract the smaller number from the bigger one until they switch places). We can even do the extended version if we keep track of how often we had to subtract.
– By doing the extended Euclidean algorithm on
and 
we can find two integers 
and 
so that 
. (The extended Euclidian algorithm does work on rational numbers.)
– Since we know that $n$ and $m$ are integers, we can find them relatively fast by comparing them to
, 
, 
, 
and so on and then doing a binary search (of course, check the signum first).
– The equation
is equivalent to 
. So all we have to do now is to calculate two integer square roots, which we can do with our marker on the floor, without using the cubes.
(We should probably make sure that $x$ is completly reduced at that point, though I am pretty sure it isn’t necessary since the extended Euclidean algorithm should give us coprime
and 
. But I wouldn’t risk it while facing the sharks.)
This was great fun. The best thing is that we didn’t have to write
as a fraction, so we don’t have to mind any p’s or q’s.
It would be nice to have a heatmap of all possible positive fractions which shows how many steps we needed.
Pingback: The wizard’s rational puzzle (solutions, part 1) | The Math Less Traveled
We can do it using the good old binary search:
.
.
.
1. First, get 0 using
2. Get 1 using
3. Get 0.5 using
4. Compare x with 1:
3.1 IF x 1: x’ = 1/x
(So that x’ lies between 0 and 1)
3.3 ELSE return p=1, q=1
5. Set high = 1 and low = 0
6. Set mid =
7. Compare mid and x:
7.1 IF x mid; low = mid, GOTO 6
7.3 ELSE return p = numerator of mid, q = denominator of mid (or vice versa if x’ = 1/x in STEP 4)
Binary search is a nice idea, and it would work great if we were searching for an *integer*, but I don’t think it will work here. For example, what if the number was 1/3 ? Do you see why this won’t work?
Oh yeah! In the case of 1/3, or for any other fraction where the denominator is not a power of two, the algorithm will not terminate. Great catch! Love your blog!
Right! And thanks!
Pingback: The wizard’s rational puzzle (solutions, part 2) | The Math Less Traveled