DGtal  0.9.2
extended-euclid.cpp
1 
14 #include <cstdlib>
17 #include <cmath>
18 #include <iostream>
19 #include <iomanip>
20 #include <string>
21 #include "DGtal/arithmetic/IntegerComputer.h"
23 
25 
26 using namespace DGtal;
27 
29 
30 void usage( int, char** argv )
31 {
32  std::cerr << "Usage: " << argv[ 0 ] << " <a> <b> <c>" << std::endl;
33  std::cerr << "\t - solves the diophantine equation ax+by=c by the extended Euclid algorithm." << std::endl;
34  std::cerr << "\t - note: c should be a multiple of gcd(a,b)." << std::endl;
35 }
36 
40 int main( int argc, char** argv )
41 {
42  if ( argc < 4 )
43  {
44  usage( argc, argv );
45  return 0;
46  }
47 
49  typedef BigInteger Integer;
50  typedef IntegerComputer<Integer> IC;
52 
54  Integer a( argv[ 1 ] );
55  Integer b( argv[ 2 ] );
56  Integer c( argv[ 3 ] );
57  IC ic;
58  Integer g = ic.gcd( a, b );
59  if ( ic.isZero( a ) || ic.isZero( b ) )
60  {
61  std::cerr << "[Error] parameters a and b should be non-null." << std::endl;
62  return 1;
63  }
64  if ( ic.isNotZero( c % g ) )
65  {
66  std::cerr << "[Error] parameter c should be a multiple of gcd(a,b)." << std::endl;
67  return 2;
68  }
70 
72  IC::Vector2I X = ic.extendedEuclid( a, b, c );
73  std::cout << "x=" << X[ 0 ] << " y=" << X[ 1 ] << std::endl;
74  Integer d = a*X[ 0 ] + b*X[ 1 ];
75  if ( c != d )
76  {
77  std::cerr << "[Internal Error] Output of extended Euclid algorithm is incorrect: " << d << " != " << c
78  << ". This should not happen." << std::endl;
79  return 3;
80  }
82  return 0;
83 }
84 
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.