We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For those who became interested in Stern-Borcot due to this problem, just a note that studying the repeated application of it's recursive formulae can lead to quick algorithms (including for this problem, no GCD or modular inverse required), and also useful approximations. For example, my computer cannot tell the difference between M_PIl (pi as an f64) and 8717442233 / 2774848045, but also 355/113 is probably "good enough" in many cases (too large by 0.0000085%).
A related tree is the Calkin-Wilf tree. I recommend the paper "Recounting the Rationals" for those intrigued by Stern-Brocot. It's a very short, accessible, and intersting paper.
Project Euler #71: Ordered fractions
You are viewing a single comment's thread. Return to all comments →
For those who became interested in Stern-Borcot due to this problem, just a note that studying the repeated application of it's recursive formulae can lead to quick algorithms (including for this problem, no GCD or modular inverse required), and also useful approximations. For example, my computer cannot tell the difference between M_PIl (pi as an f64) and 8717442233 / 2774848045, but also 355/113 is probably "good enough" in many cases (too large by 0.0000085%).
A related tree is the Calkin-Wilf tree. I recommend the paper "Recounting the Rationals" for those intrigued by Stern-Brocot. It's a very short, accessible, and intersting paper.
https://www.math.upenn.edu/~wilf/website/recounting.pdf