DGtal  0.9.2
convergents-biginteger.cpp
1 
14 #include <iostream>
17 #include "DGtal/arithmetic/LighterSternBrocot.h"
19 
21 
22 using namespace DGtal;
23 
25 
26 void usage( int, char** argv )
27 {
28  std::cerr << "Usage: " << argv[ 0 ] << " <p> <q>" << std::endl;
29  std::cerr << "\t - computes the successive convergent of the fraction p / q." << std::endl;
30 }
31 
35 int main( int argc, char** argv )
36 {
37  if ( argc < 3 )
38  {
39  usage( argc, argv );
40  return 1;
41  }
42  std::string inputP = argv[ 1 ];
43  std::string inputQ = argv[ 2 ];
44 
46  typedef BigInteger Integer;
47  typedef DGtal::int64_t Quotient;
48  typedef LighterSternBrocot<Integer, Quotient, StdMapRebinder> SB; // the type of the Stern-Brocot tree
49  typedef SB::Fraction Fraction; // the type for fractions
50  typedef Fraction::ConstIterator ConstIterator; // the iterator type for visiting quotients
51  typedef Fraction::Value Value; // the value of the iterator, a pair (quotient,depth).
53 
55  Integer p( inputP );
56  Integer q( inputQ );
57  Fraction f( p, q ); // fraction p/q
59 
61  // Visit quotients u_k as pair (u_k,k)
62  std::cout << "z = ";
63  ConstIterator itbegin = f.begin(), itend = f.end();
64  for ( ConstIterator it = itbegin; it != itend; ++it )
65  {
66  Value u = *it;
67  std::cout << ( ( it == itbegin ) ? "[" : "," )
68  << u.first;
69  }
70  std::cout << "]" << std::endl;
72 
74  Fraction g; // fraction null, 0/0, invalid
75  for ( ConstIterator it = itbegin; it != itend; ++it )
76  {
77  Value u = *it;
78  std::cout << "z_" << u.second << " = ";
79  g.push_back( u ); // add (u_i,i) to existing fractions
80  std::cout << g.p() << " / " << g.q() << std::endl;
81  }
83  return 0;
84 }
85 
DGtal::int32_t Integer
Definition: StdDefs.h:74
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition: BasicTypes.h:79
DGtal is the top-level namespace which contains all DGtal functions and types.
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74