Artifact bfa0be1fa6ea3c75c678e1a1b27ac92f68d0a561

• File _lib/numeric/sternBrocot.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/numeric/sternBrocot.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// Enumerate all positive reduced fractions in a 
// systematic manner.
//   [pl/ql, pr/qr] --> [pl/ql, pm/qm] + [pm/qm, pr/qr]
//                  --> ...
//
// Verified by
//   - CodeCraft 09 FRACTION
//-------------------------------------------------------------

void sternBrocot(LL pl = 0, LL ql = 1, LL pr = 1, LL qr = 0)
{
	LL pm = pl + pr, qm = ql + qr;
	sternBrocot(pl, ql, pm, qm);
	sternBrocot(pm, qm, pr, qr);
}

/*
bool fleq(LL p1, LL q1, LL p2, LL q2)
{
	return p1*q2 <= p2*q1;
}

void sternBrocot(LL pl = 0, LL ql = 1, LL pr = 1, LL qr = 0)
{
	for(;;) {
		LL pm = pl + pr, qm = ql + qr;

		if( fleq(c,d,pm,qm) ) {
//			pr = pm, qr = qm; // [pl/ql, pm/qm]
			LL X = c*ql - d*pl;
			LL Y = d*pr - c*qr;
			LL k = max(1LL, Y/X);
			pr += k*pl;
			qr += k*ql;
		}
		else if( fleq(pm,qm,a,b) ) {
//			pl = pm, ql = qm; // [pm/qm, pr/qr]
			LL X = b*pr - a*qr;
			LL Y = a*ql - b*pl;
			LL k = max(1LL, Y/X);
			pl += k*pr;
			ql += k*qr;
		}
		else {
			cout << pm+qm*base << "/" << qm << endl;
			break;
		}
	}
}
*/