3 ms·
Useless trivia. You know the 20 questions game? You can actually find any rational through a binary higher/lower search of the Stern-Brocot tree. Finding n/m
by btilly 9y ago
Useless trivia. You know the 20 questions game? You can actually find any rational through a binary higher/lower search of the Stern-Brocot tree. Finding n/m this way takes O(log(max(|n|, |m|))).
The logic is slightly tricky. Some day I'll get bored enough to code it up...
- mathgenius 9y agoThe fractions in the Stern-Brocot tree approximate any real number. There's a statement about this that is equivalent to the Riemann hypothesis.