Problem

[helios]

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:

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?

[lastchance]

Sorry, @Helios, I could only get O(N) - I guess that's not much help.

#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!

[jonnin]

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.

[helios]

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).

[jonnin]

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?

[helios]

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.

[jonnin]

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 ?}

[helios]

How do you mean? How large is the array? How is it populated and used? How does the variable's value "depend" on n?

[Ganado]

Hahaha, I'm pretty sure you replied to a spambot. Their machine-learning-context-generated sentences are getting pretty good, aren't they? (Well, the profile was casino spam... even if it wasn't AI.)

[helios]

Friggin' GPT-3, man.

[jonnin]

the phone call ones have gotten better (they respond within the context of their spam) but they have a 10 second no speak right away and can't answer basic questions ("what country do you live in" blows their minds usually).

Even 10+ years ago.. we were writing proposals for government contracts and you could enter a dozen phrases and PHD level into a paper generator and it would spew all sorts of great sounding nonsense by stripping sentences from online papers, wiki, and other search results. They actually made sense, but then you read it a couple of times and realize it also didn't say anything at all.

[helios]

Even 10+ years ago.. we were writing proposals for government contracts and you could enter a dozen phrases and PHD level into a paper generator and it would spew all sorts of great sounding nonsense by stripping sentences from online papers, wiki, and other search results. They actually made sense, but then you read it a couple of times and realize it also didn't say anything at all.

Those were Markov chain generators though, right? The same type of algorithm was used for the Sokal paper in 1996. Modern NLP algorithms are way better with semantics and overall tone, but (obviously) they still fail at constructing an overarching idea, so either you get things like contradictory statements, or the text is meaningless even if individual sentences are not.

[jonnin]

I honestly do not recall how they worked. Those blasted proposals had a due date and our boss was really bad about giving us too little time to do them so it inevitably became an all nighter the day before due. In that light, when about done with them or waiting on the proofreader to go over them, we would goof off by running the current version thru the snoop dog shizzle program or run the key terms thru a paper generator just to laugh at it.