DGtal 1.3.0
Searching...
No Matches
convergents.cpp
Go to the documentation of this file.
1
36#include <iostream>
37#include "DGtal/arithmetic/LighterSternBrocot.h"
39
41
42using namespace DGtal;
43
45
46void usage( int, char** argv )
47{
48 std::cerr << "Usage: " << argv[ 0 ] << " <p> <q>" << std::endl;
49 std::cerr << "\t - computes the successive convergent of the fraction p / q." << std::endl;
50}
51
55int main( int argc, char** argv )
56{
57 if ( argc < 3 )
58 {
59 usage( argc, argv );
60 return 1;
61 }
62
64 typedef LighterSternBrocot<DGtal::int64_t, DGtal::int64_t, StdMapRebinder> SB; // the type of the Stern-Brocot tree
65 typedef SB::Fraction Fraction; // the type for fractions
66 typedef Fraction::ConstIterator ConstIterator; // the iterator type for visiting quotients
67 typedef Fraction::Value Value; // the value of the iterator, a pair (quotient,depth).
69
71 DGtal::int64_t p = atoll( argv[ 1 ] );
72 DGtal::int64_t q = atoll( argv[ 2 ] );
73 Fraction f( p, q ); // fraction p/q
75
77 // Visit quotients u_k as pair (u_k,k)
78 std::cout << "z = ";
79 ConstIterator itbegin = f.begin(), itend = f.end();
80 for ( ConstIterator it = itbegin; it != itend; ++it )
81 {
82 Value u = *it;
83 std::cout << ( ( it == itbegin ) ? "[" : "," )
84 << u.first;
85 }
86 std::cout << "]" << std::endl;
88
90 Fraction g; // fraction null, 0/0, invalid
91 for ( ConstIterator it = itbegin; it != itend; ++it )
92 {
93 Value u = *it;
94 std::cout << "z_" << u.second << " = ";
95 g.push_back( u ); // add (u_i,i) to existing fractions
96 std::cout << g.p() << " / " << g.q() << std::endl;
97 }
99 return 0;
100}
101
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
MyDigitalSurface::ConstIterator ConstIterator
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74
int main()
Definition: testBits.cpp:56