DGtal  0.9.3beta
arithmetic/convergents.cpp

Computes the quotients and the convergents of a given fraction.

See also
Instantiating fractions
# Approximations of pi
$ ./examples/arithmetic/convergents 103993 33102
z = [3,7,15,1,292]
z_0 = 3 / 1
z_1 = 22 / 7
z_2 = 333 / 106
z_3 = 355 / 113
z_4 = 103993 / 33102
#include <iostream>
#include "DGtal/arithmetic/LighterSternBrocot.h"
using namespace DGtal;
void usage( int, char** argv )
{
std::cerr << "Usage: " << argv[ 0 ] << " <p> <q>" << std::endl;
std::cerr << "\t - computes the successive convergent of the fraction p / q." << std::endl;
}
int main( int argc, char** argv )
{
if ( argc < 3 )
{
usage( argc, argv );
return 1;
}
typedef LighterSternBrocot<DGtal::int64_t, DGtal::int64_t, StdMapRebinder> SB; // the type of the Stern-Brocot tree
typedef SB::Fraction Fraction; // the type for fractions
typedef Fraction::ConstIterator ConstIterator; // the iterator type for visiting quotients
typedef Fraction::Value Value; // the value of the iterator, a pair (quotient,depth).
DGtal::int64_t p = atoll( argv[ 1 ] );
DGtal::int64_t q = atoll( argv[ 2 ] );
Fraction f( p, q ); // fraction p/q
// Visit quotients u_k as pair (u_k,k)
std::cout << "z = ";
ConstIterator itbegin = f.begin(), itend = f.end();
for ( ConstIterator it = itbegin; it != itend; ++it )
{
Value u = *it;
std::cout << ( ( it == itbegin ) ? "[" : "," )
<< u.first;
}
std::cout << "]" << std::endl;
Fraction g; // fraction null, 0/0, invalid
for ( ConstIterator it = itbegin; it != itend; ++it )
{
Value u = *it;
std::cout << "z_" << u.second << " = ";
g.push_back( u ); // add (u_i,i) to existing fractions
std::cout << g.p() << " / " << g.q() << std::endl;
}
return 0;
}