<dfn id="lvnb7"></dfn>

    <dfn id="lvnb7"></dfn> <address id="lvnb7"></address>

          <ruby id="lvnb7"></ruby>

            <delect id="lvnb7"><strike id="lvnb7"></strike></delect>

               
              Problem

              Let's define an "n-bounded rational" as a rational number whose numerator and denominator both have absolute values no greater than n. There exists a function next() that takes an n-bounded rational and is either undefined or returns the least n-bounded rational that's greater than the argument.

              Problem: How to compute next() efficiently, i.e. O(log n) or faster? Hell, I'll take O(sqrt(n)).

              The best I have:
              1
              2
              3
              4
              5
              6
              7
              8
              9
              10
              11
              12
              13
              14
              15
              16
              Q<n> next(Q<n> q){
                  Q<n> ret = (q.n + 1) / q.d;
                  for (i = 2 to n){
                      auto a = q.n * i + 1;
                      auto b = q.d * i;
                      auto g = gcd(a, b);
                      a /= g;
                      b /= g;
                      if (a > n || b > n)
                          continue;
                      Q<n> c = a / b;
                      if (q < c < ret)
                          ret = c;
                  }
                  return ret;
              }
              It's faster than brute-forcing both the numerator and the denominator, but that's it. I haven't made much headway into reducing the search space in general. There are easy cases such as 1/x and x/1 where x > n/2, but otherwise it's pretty tricky.

              Any ideas?
              Last edited on
              Sorry, @Helios, I could only get O(N) - I guess that's not much help.

              1
              2
              3
              4
              5
              6
              7
              8
              9
              10
              11
              12
              13
              14
              15
              16
              17
              18
              19
              20
              21
              22
              23
              24
              25
              26
              27
              28
              29
              30
              31
              32
              33
              34
              35
              36
              #include <iostream>
              #include <vector>
              #include <utility>
              using namespace std;
              
              struct Rational{ unsigned n, d; };
              bool operator <= ( Rational a, Rational b ){ return a.n * b.d <= a.d * b.n; }
              ostream & operator << ( ostream &out, Rational a ){ return out << a.n << '/' << a.d; }
              
              
              Rational next( Rational x, unsigned N )
              {
                 bool found = false;
                 Rational best{ 0, 0 };    // signifies undefined
                 for ( unsigned r = N; r; r-- )   // letting it go all the way to r=1 saves a gcd call later
                 {
                    Rational trial{ r * x.n / x.d + 1, r };
                    if ( trial.n > N ) continue;
                    if ( !found || trial <= best ) best = trial;
                    found = true;
                 }
                 return best;
              }
              
              
              int main()
              {
                 vector< pair<Rational,unsigned> > tests = { {{2,3},7}, {{5,8},12}, {{65,31},73}, {{7,1},7} };
                 for ( auto pr : tests )
                 {
                    Rational R = next( pr.first, pr.second );
                    cout << "Next " << pr.second << "-bounded rational after " << pr.first << " is ";
                    if ( R.d == 0 ) cout << " ... naah!\n";
                    else            cout << R << '\n';
                 }
              }


              Next 7-bounded rational after 2/3 is 5/7
              Next 12-bounded rational after 5/8 is 7/11
              Next 73-bounded rational after 65/31 is 21/10
              Next 7-bounded rational after 7/1 is  ... naah!

              Last edited on
              have you tried going backwards somehow?

              eg start at .625 (5/8) and hunt for decimals that resolve to fractions in range?
              may not be any better... not up on decimal to fraction approximation techniques and how fast they are or what constraints you can apply.

              the smallest increment you can add is 1/n?

              looking at something called the stern brocot tree... if you can find a way to pick the decimal you want, you can walk the tree in lg(n) to find the fraction that matches it? ... (and I am not sure what N is here... its not YOUR n).

              using that idea, I think you can start at the fraction provided and iterate its tree directly (without the tree, just doing the math) to produce the next one in range. Which is ... ? go right once (bigger than now) and go left until out of range (smallest one on the left that works?) I will take a crack at it later. May be tomorrow.
              Last edited on
              the smallest increment you can add is 1/n?
              Actually, since next(1/n) = 1/(n-1), the smallest increment is 1/(n^2 - n).

              looking at something called the stern brocot tree... if you can find a way to pick the decimal you want, you can walk the tree in lg(n) to find the fraction that matches it? ... (and I am not sure what N is here... its not YOUR n).

              using that idea, I think you can start at the fraction provided and iterate its tree directly (without the tree, just doing the math) to produce the next one in range.
              Interesting, but that's kinda what I did already. Necessarily the next n-bounded rational is (numerator * i + 1) / (denominator * i), where i is somewhere between 1 and n. In other words, the depth of the tree is still n (or some multiple).
              Last edited on
              ok. I was not sure about that one, I never really got deeply into playing with fractions. This is a neat problem (it sure feels like there should be a rapid convergence attack) but is this for fun or are you doing something practical with it?
              This is purely for fun. I've been thinking about this for a while because as you say it seems like there should be a fast solution. It's tantalizing.
              One more shotgun idea (darn it, its stuck in the back of my head, hard to focus on work for it) ...
              5/8
              * 1.5/1.5 = {7.5/12} start iteration here (try 8/12, 7/12, 7/11, 8/11, whatnot?)

              where 1.5 = 12/8

              {or basically, trying to hit that calculus idea of getting a CLOSE initial guess that can converge on it from there ?}
              Last edited on
              Registered users can post here. Sign in or register to post.
              最好看的2018中文字幕_亚洲欧美日韩一区_国产欧美亚洲综合第一区_欧美日韩视费观看视频