DGtal 1.3.0
Searching...
No Matches
convergents-biginteger.cpp
Go to the documentation of this file.
1
42#include <iostream>
43#include "DGtal/arithmetic/LighterSternBrocot.h"
45
47
48using namespace DGtal;
49
51
52void usage( int, char** argv )
53{
54 std::cerr << "Usage: " << argv[ 0 ] << " <p> <q>" << std::endl;
55 std::cerr << "\t - computes the successive convergent of the fraction p / q." << std::endl;
56}
57
61int main( int argc, char** argv )
62{
63 if ( argc < 3 )
64 {
65 usage( argc, argv );
66 return 1;
67 }
68 std::string inputP = argv[ 1 ];
69 std::string inputQ = argv[ 2 ];
70
72 typedef BigInteger Integer;
73 typedef DGtal::int64_t Quotient;
74 typedef LighterSternBrocot<Integer, Quotient, StdMapRebinder> SB; // the type of the Stern-Brocot tree
75 typedef SB::Fraction Fraction; // the type for fractions
76 typedef Fraction::ConstIterator ConstIterator; // the iterator type for visiting quotients
77 typedef Fraction::Value Value; // the value of the iterator, a pair (quotient,depth).
79
81 Integer p( inputP );
82 Integer q( inputQ );
83 Fraction f( p, q ); // fraction p/q
85
87 // Visit quotients u_k as pair (u_k,k)
88 std::cout << "z = ";
89 ConstIterator itbegin = f.begin(), itend = f.end();
90 for ( ConstIterator it = itbegin; it != itend; ++it )
91 {
92 Value u = *it;
93 std::cout << ( ( it == itbegin ) ? "[" : "," )
94 << u.first;
95 }
96 std::cout << "]" << std::endl;
98
100 Fraction g; // fraction null, 0/0, invalid
101 for ( ConstIterator it = itbegin; it != itend; ++it )
102 {
103 Value u = *it;
104 std::cout << "z_" << u.second << " = ";
105 g.push_back( u ); // add (u_i,i) to existing fractions
106 std::cout << g.p() << " / " << g.q() << std::endl;
107 }
109 return 0;
110}
111
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Point::Coordinate Integer
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
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition: BasicTypes.h:79
int main()
Definition: testBits.cpp:56