DGtal  1.1.0
extended-euclid.cpp
Go to the documentation of this file.
1
31 #include <cstdlib>
34 #include <cmath>
35 #include <iostream>
36 #include <iomanip>
37 #include <string>
38 #include "DGtal/arithmetic/IntegerComputer.h"
40
42
43 using namespace DGtal;
44
46
47 void usage( int, char** argv )
48 {
49  std::cerr << "Usage: " << argv[ 0 ] << " <a> <b> <c>" << std::endl;
50  std::cerr << "\t - solves the diophantine equation ax+by=c by the extended Euclid algorithm." << std::endl;
51  std::cerr << "\t - note: c should be a multiple of gcd(a,b)." << std::endl;
52 }
53
57 int main( int argc, char** argv )
58 {
59  if ( argc < 4 )
60  {
61  usage( argc, argv );
62  return 0;
63  }
64
66  typedef BigInteger Integer;
67  typedef IntegerComputer<Integer> IC;
69
71  Integer a( argv[ 1 ] );
72  Integer b( argv[ 2 ] );
73  Integer c( argv[ 3 ] );
74  IC ic;
75  Integer g = ic.gcd( a, b );
76  if ( ic.isZero( a ) || ic.isZero( b ) )
77  {
78  std::cerr << "[Error] parameters a and b should be non-null." << std::endl;
79  return 1;
80  }
81  if ( ic.isNotZero( c % g ) )
82  {
83  std::cerr << "[Error] parameter c should be a multiple of gcd(a,b)." << std::endl;
84  return 2;
85  }
87
89  IC::Vector2I X = ic.extendedEuclid( a, b, c );
90  std::cout << "x=" << X[ 0 ] << " y=" << X[ 1 ] << std::endl;
91  Integer d = a*X[ 0 ] + b*X[ 1 ];
92  if ( c != d )
93  {
94  std::cerr << "[Internal Error] Output of extended Euclid algorithm is incorrect: " << d << " != " << c
95  << ". This should not happen." << std::endl;
96  return 3;
97  }
99  return 0;
100 }
101
DGtal::BigInteger
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition: BasicTypes.h:79
DGtal::IntegerComputer< Integer >
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition: ClosedIntegerHalfPlane.h:49
main
int main(int argc, char **argv)
Definition: extended-euclid.cpp:57
usage
void usage(int, char **argv)
Definition: extended-euclid.cpp:47