DGtal 1.4.2
Loading...
Searching...
No Matches
Functions
testIntegerComputer.cpp File Reference
DGtal Test Files
#include <cstdlib>
#include <iostream>
#include "DGtal/base/Common.h"
#include "DGtal/arithmetic/IntegerComputer.h"
Include dependency graph for testIntegerComputer.cpp:

Go to the source code of this file.

Functions

template<typename Integer >
bool testGCD (const IntegerComputer< Integer > &ic)
 
template<typename Integer >
bool testCFrac (const IntegerComputer< Integer > &ic)
 
template<typename Integer >
bool testCeilFloorDiv (const IntegerComputer< Integer > &ic)
 
template<typename Integer >
bool testExtendedEuclid (const IntegerComputer< Integer > &ic)
 
template<typename Integer >
bool testCoefficientIntersection (const IntegerComputer< Integer > &ic)
 
template<typename Integer >
bool testValidBezout (const IntegerComputer< Integer > &ic)
 
bool testIntegerComputer ()
 
int main (int, char **)
 

Detailed Description

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Author
Jacques-Olivier Lachaud (jacqu.nosp@m.es-o.nosp@m.livie.nosp@m.r.la.nosp@m.chaud.nosp@m.@uni.nosp@m.v-sav.nosp@m.oie..nosp@m.fr ) Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
Date
2012/03/05

Functions for testing class IntegerComputer.

This file is part of the DGtal library.

Definition in file testIntegerComputer.cpp.

Function Documentation

◆ main()

int main ( int ,
char **  )

Definition at line 331 of file testIntegerComputer.cpp.

332{
333 trace.beginBlock ( "Testing class IntegerComputer" );
334 bool res = testIntegerComputer(); // && ... other tests
335 trace.emphase() << ( res ? "Passed." : "Error." ) << endl;
336 trace.endBlock();
337 return res ? 0 : 1;
338}
DGtal::Trace::beginBlock
void beginBlock(const std::string &keyword="")
DGtal::Trace::emphase
std::ostream & emphase()
DGtal::Trace::endBlock
double endBlock()
DGtal::trace
Trace trace
Definition Common.h:153
testIntegerComputer
bool testIntegerComputer()
Definition testIntegerComputer.cpp:264

References DGtal::Trace::beginBlock(), DGtal::Trace::emphase(), DGtal::Trace::endBlock(), testIntegerComputer(), and DGtal::trace.

◆ testCeilFloorDiv()

template<typename Integer >
bool testCeilFloorDiv ( const IntegerComputer< Integer > & ic)

Definition at line 122 of file testIntegerComputer.cpp.

123{
124 unsigned int nbok = 0;
125 unsigned int nb = 0;
126 Integer a = rand();
127 a -= rand();
128 Integer b = rand();
129 b -= rand();
130 if ( ic.isZero( b ) ) ++b;
131 trace.info() << "- a / b = " << a << " / " << b << std::endl;
132 Integer fl = ic.floorDiv( a, b );
133 Integer ce = ic.ceilDiv( a, b );
134 Integer fl2, ce2;
135 ic.getFloorCeilDiv( fl2, ce2, a, b );
136 nbok += fl == fl2 ? 1 : 0;
137 nb++;
138 trace.info() << "(" << nbok << "/" << nb << ") "
139 << "fl == fl2 " << fl2 << std::endl;
140 nbok += ce == ce2 ? 1 : 0;
141 nb++;
142 trace.info() << "(" << nbok << "/" << nb << ") "
143 << "ce == ce2 " << ce2 << std::endl;
144 Integer m = a % b;
145 nbok += ( ( m == 0 ) && ( fl == ce ) ) || ( fl + 1 == ce ) ? 1 : 0;
146 nb++;
147 trace.info() << "(" << nbok << "/" << nb << ") "
148 << "( ( m == 0 ) && ( fl == ce ) ) || ( fl+1 == ce )"
149 << std::endl;
150 return nbok == nb;
151}
DGtal::IntegerComputer::isZero
static bool isZero(IntegerParamType a)
DGtal::IntegerComputer::ceilDiv
Integer ceilDiv(IntegerParamType na, IntegerParamType nb) const
DGtal::IntegerComputer::getFloorCeilDiv
void getFloorCeilDiv(Integer &fl, Integer &ce, IntegerParamType na, IntegerParamType nb) const
DGtal::IntegerComputer::floorDiv
Integer floorDiv(IntegerParamType na, IntegerParamType nb) const
DGtal::Trace::info
std::ostream & info()

References DGtal::IntegerComputer< TInteger >::ceilDiv(), DGtal::IntegerComputer< TInteger >::floorDiv(), DGtal::IntegerComputer< TInteger >::getFloorCeilDiv(), DGtal::Trace::info(), DGtal::IntegerComputer< TInteger >::isZero(), and DGtal::trace.

Referenced by testIntegerComputer().

◆ testCFrac()

template<typename Integer >
bool testCFrac ( const IntegerComputer< Integer > & ic)

Definition at line 82 of file testIntegerComputer.cpp.

83{
84 unsigned int nbok = 0;
85 unsigned int nb = 0;
86 Integer a = rand();
87 Integer b = rand();
88 Integer g = ic.gcd( a, b );
89 trace.info() << "a / b = " << a << " / " << b << std::endl;
90 std::vector<Integer> quotients;
91 Integer g2 = ic.getCFrac( quotients, a, b );
92 nbok += g == g2 ? 1 : 0;
93 nb++;
94 trace.info() << "(" << nbok << "/" << nb << ") "
95 << g << " == " << g2 << std::endl;
96 trace.info() << a << " / " << b << " = ";
97 for ( typename std::vector<Integer>::const_iterator it = quotients.begin(),
98 it_end = quotients.end(); it != it_end; ++it )
99 trace.info() << *it;
100 trace.info() << std::endl;
101 double da = NumberTraits<Integer>::castToDouble( a );
102 double db = NumberTraits<Integer>::castToDouble( b );
103 double q = floor( da / db );
104 nbok += Integer( (int) q ) == quotients[ 0 ] ? 1 : 0;
105 nb++;
106 trace.info() << "(" << nbok << "/" << nb << ") "
107 << q << " == " << quotients[ 0 ] << std::endl;
108 typedef typename IntegerComputer<Integer>::Point2I Point2I;
109 Point2I p = ic.convergent( quotients, quotients.size() );
110 nbok += p[ 0 ] == ( a / g ) ? 1 : 0;
111 nb++;
112 trace.info() << "(" << nbok << "/" << nb << ") "
113 << "convergent p[ 0 ] " << p[ 0 ] << " == a / g " << std::endl;
114 nbok += p[ 1 ] == ( b / g ) ? 1 : 0;
115 nb++;
116 trace.info() << "(" << nbok << "/" << nb << ") "
117 << "convergent p[ 1 ] " << p[ 1 ] << " == b / g " << std::endl;
118 return nbok == nb;
119}
DGtal::IntegerComputer::getCFrac
Integer getCFrac(std::vector< Integer > &quotients, IntegerParamType a, IntegerParamType b) const
DGtal::IntegerComputer::convergent
Point2I convergent(const std::vector< Integer > &quotients, unsigned int k) const
DGtal::IntegerComputer::gcd
Integer gcd(IntegerParamType a, IntegerParamType b) const
DGtal::NumberTraits
Aim: The traits class for all models of Cinteger.
Definition NumberTraits.h:564

References DGtal::IntegerComputer< TInteger >::convergent(), DGtal::IntegerComputer< TInteger >::gcd(), DGtal::IntegerComputer< TInteger >::getCFrac(), DGtal::Trace::info(), and DGtal::trace.

Referenced by testIntegerComputer().

◆ testCoefficientIntersection()

template<typename Integer >
bool testCoefficientIntersection ( const IntegerComputer< Integer > & ic)

Definition at line 176 of file testIntegerComputer.cpp.

177{
178 typedef typename IntegerComputer<Integer>::Point2I Point2I;
179 unsigned int nbok = 0;
180 unsigned int nb = 0;
181 Point2I p, N;
182 Integer c;
183 p = Point2I( rand(), rand() );
184 N = Point2I( rand() , rand() );
185 c = rand() * rand();
186 Point2I u( rand() / 100, rand() / 100);
187 trace.info() << "p = " << p << std::endl;
188 trace.info() << "u = " << u << std::endl;
189 trace.info() << "N = " << N << std::endl;
190 trace.info() << "c = " << c << std::endl;
191 Integer fl, ce;
192 ic.getCoefficientIntersection( fl, ce, p, u, N, c );
193 trace.info() << "fl = " << fl << ", ce = " << ce << std::endl;
194 Point2I p1 = p + (u * fl);
195 Point2I p2 = p + (u * ce);
196 Integer c1 = ic.dotProduct( p1, N );
197 Integer c2 = ic.dotProduct( p2, N );
198 trace.info() << "c1 = " << c1
199 << " <= c = " << c
200 << " <= c2 = " << c2 << std::endl;
201 nbok += ( ( c1 == c2 ) && ( c == c1 ) )
202 || ( ( c1 <= c ) && ( c < c2 ) ) ? 1 : 0;
203 nb++;
204 trace.info() << "(" << nbok << "/" << nb << ") "
205 << "( ( c1 == c2 ) && ( c == c1 ) ) || ( ( c1 <= c ) && ( c < c2 ) )" << std::endl;
206 return nbok == nb;
207}
DGtal::IntegerComputer::dotProduct
Integer dotProduct(const Vector2I &u, const Vector2I &v) const
DGtal::IntegerComputer::getCoefficientIntersection
void getCoefficientIntersection(Integer &fl, Integer &ce, const Vector2I &p, const Vector2I &u, const Vector2I &N, IntegerParamType c) const

References DGtal::IntegerComputer< TInteger >::dotProduct(), DGtal::IntegerComputer< TInteger >::getCoefficientIntersection(), DGtal::Trace::info(), and DGtal::trace.

Referenced by testIntegerComputer().

◆ testExtendedEuclid()

template<typename Integer >
bool testExtendedEuclid ( const IntegerComputer< Integer > & ic)

Definition at line 154 of file testIntegerComputer.cpp.

155{
156 typedef typename IntegerComputer<Integer>::Point2I Point2I;
157 unsigned int nbok = 0;
158 unsigned int nb = 0;
159 Integer a = rand();
160 Integer b = rand();
161 Integer g = ic.gcd( a, b );
162 trace.info() << "a / b = " << a << " / " << b
163 << " gcd=" << g << std::endl;
164 Point2I v = ic.extendedEuclid( a, b, g );
165 trace.info() << "Bezout = " << v[ 0 ] << "," << v[ 1 ] << std::endl;
166 Integer rem = a * v[ 0 ] + b * v[ 1 ];
167 nbok += rem == g ? 1 : 0;
168 nb++;
169 trace.info() << "(" << nbok << "/" << nb << ") "
170 << "a * v[ 0 ] + b * v[ 1 ] == g "
171 << "(" << rem << " == " << g << ")" << std::endl;
172 return nbok == nb;
173}
DGtal::IntegerComputer::extendedEuclid
Vector2I extendedEuclid(IntegerParamType a, IntegerParamType b, IntegerParamType c) const

References DGtal::IntegerComputer< TInteger >::extendedEuclid(), DGtal::IntegerComputer< TInteger >::gcd(), DGtal::Trace::info(), and DGtal::trace.

Referenced by testIntegerComputer().

◆ testGCD()

template<typename Integer >
bool testGCD ( const IntegerComputer< Integer > & ic)

Definition at line 45 of file testIntegerComputer.cpp.

46{
47 unsigned int nbok = 0;
48 unsigned int nb = 0;
49 Integer a = rand();
50 Integer b = rand();
51 Integer g = ic.gcd( a, b );
52 trace.info() << "GCD(" << a << "," << b << ")"
53 << " = " << g << std::endl;
54 Integer ra = a % g;
55 Integer rb = b % g;
56 nbok += ic.isZero( ra ) ? 1 : 0;
57 nb++;
58 trace.info() << "(" << nbok << "/" << nb << ") "
59 << a << " % " << g << " == 0" << std::endl;
60 nbok += ic.isZero( rb ) ? 1 : 0;
61 nb++;
62 trace.info() << "(" << nbok << "/" << nb << ") "
63 << b << " % " << g << " == 0" << std::endl;
64 a /= g; b /= g;
65 g = ic.gcd( a, b );
66 nbok += g == Integer( 1 ) ? 1 : 0;
67 nb++;
68 trace.info() << "(" << nbok << "/" << nb << ") "
69 << "GCD(" << a << "," << b << ") == 1" << std::endl;
70 Integer c = rand();
71 ++c; // avoids zero.
72 a *= c; b *= c;
73 ic.getGcd( g, a, b );
74 nbok += g == c ? 1 : 0;
75 nb++;
76 trace.info() << "(" << nbok << "/" << nb << ") "
77 << "GCD(" << a << "," << b << ") == " << c << std::endl;
78 return nbok == nb;
79}
DGtal::IntegerComputer::getGcd
void getGcd(Integer &g, IntegerParamType a, IntegerParamType b) const

References DGtal::IntegerComputer< TInteger >::gcd(), DGtal::IntegerComputer< TInteger >::getGcd(), DGtal::Trace::info(), DGtal::IntegerComputer< TInteger >::isZero(), and DGtal::trace.

Referenced by testIntegerComputer().

◆ testIntegerComputer()

bool testIntegerComputer ( )

Example of a test. To be completed.

Definition at line 264 of file testIntegerComputer.cpp.

265{
266 unsigned int nbtests = 50;
267 unsigned int nbok = 0;
268 unsigned int nb = 0;
269 typedef BigInteger Integer;
270 IntegerComputer<Integer> ic;
271 trace.beginBlock ( "Testing block: multiple random gcd." );
272 for ( unsigned int i = 0; i < nbtests; ++i )
273 {
274 nbok += testGCD<Integer>( ic ) ? 1 : 0;
275 nb++;
276 }
277 trace.info() << "(" << nbok << "/" << nb << ") gcd tests." << std::endl;
278 trace.endBlock();
279
280 trace.beginBlock ( "Testing block: multiple random cfrac." );
281 for ( unsigned int i = 0; i < nbtests; ++i )
282 {
283 nbok += testCFrac<Integer>( ic ) ? 1 : 0;
284 nb++;
285 }
286 trace.info() << "(" << nbok << "/" << nb << ") cfrac tests." << std::endl;
287 trace.endBlock();
288
289 trace.beginBlock ( "Testing block: multiple ceil floor division." );
290 for ( unsigned int i = 0; i < nbtests; ++i )
291 {
292 nbok += testCeilFloorDiv<Integer>( ic ) ? 1 : 0;
293 nb++;
294 }
295 trace.info() << "(" << nbok << "/" << nb << ") ceil floor division." << std::endl;
296 trace.endBlock();
297
298 trace.beginBlock ( "Testing block: multiple Bezout / extended euclid: ax+by= gcd(a,b)." );
299 for ( unsigned int i = 0; i < nbtests; ++i )
300 {
301 nbok += testExtendedEuclid<Integer>( ic ) ? 1 : 0;
302 nb++;
303 }
304 trace.info() << "(" << nbok << "/" << nb << ") Bezout / extended euclid." << std::endl;
305 trace.endBlock();
306
307 trace.beginBlock ( "Testing block: multiple coefficient intersection." );
308 for ( unsigned int i = 0; i < nbtests; ++i )
309 {
310 nbok += testCoefficientIntersection( ic ) ? 1 : 0;
311 nb++;
312 }
313 trace.info() << "(" << nbok << "/" << nb << ") coefficient intersection." << std::endl;
314 trace.endBlock();
315
316 trace.beginBlock ( "Testing block: multiple valid bezout." );
317 for ( unsigned int i = 0; i < nbtests; ++i )
318 {
319 nbok += testValidBezout( ic ) ? 1 : 0;
320 nb++;
321 }
322 trace.info() << "(" << nbok << "/" << nb << ") valid bezout." << std::endl;
323 trace.endBlock();
324
325 return nbok == nb;
326}
DGtal::IntegerComputer
Aim: This class gathers several types and methods to make computation with integers.
Definition IntegerComputer.h:83
DGtal::BigInteger
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition BasicTypes.h:79
testGCD
bool testGCD(const IntegerComputer< Integer > &ic)
Definition testIntegerComputer.cpp:45
testCeilFloorDiv
bool testCeilFloorDiv(const IntegerComputer< Integer > &ic)
Definition testIntegerComputer.cpp:122
testValidBezout
bool testValidBezout(const IntegerComputer< Integer > &ic)
Definition testIntegerComputer.cpp:210
testCoefficientIntersection
bool testCoefficientIntersection(const IntegerComputer< Integer > &ic)
Definition testIntegerComputer.cpp:176
testCFrac
bool testCFrac(const IntegerComputer< Integer > &ic)
Definition testIntegerComputer.cpp:82
testExtendedEuclid
bool testExtendedEuclid(const IntegerComputer< Integer > &ic)
Definition testIntegerComputer.cpp:154

References DGtal::Trace::beginBlock(), DGtal::Trace::endBlock(), DGtal::Trace::info(), testCeilFloorDiv(), testCFrac(), testCoefficientIntersection(), testExtendedEuclid(), testGCD(), testValidBezout(), and DGtal::trace.

Referenced by main().

◆ testValidBezout()

template<typename Integer >
bool testValidBezout ( const IntegerComputer< Integer > & ic)

Definition at line 210 of file testIntegerComputer.cpp.

211{
212 typedef typename IntegerComputer<Integer>::Point2I Point2I;
213 typedef typename IntegerComputer<Integer>::Vector2I Vector2I;
214 unsigned int nbok = 0;
215 unsigned int nb = 0;
216 Vector2I v;
217 Point2I A( rand(), rand() );
218 Vector2I u( rand() / 100, rand() / 100 );
219 ic.reduce( u );
220 Vector2I N( rand(), rand() );
221 Vector2I N2( rand(), rand() );
222 Integer c = rand() * rand();
223 Integer c2 = rand() * rand();
224 trace.info() << "A = " << A << std::endl;
225 trace.info() << "u = " << u << std::endl;
226 trace.info() << "N = " << N << std::endl;
227 trace.info() << "c = " << c << std::endl;
228 trace.info() << "N2 = " << N2 << std::endl;
229 trace.info() << "c2 = " << c2 << std::endl;
230 ic.getValidBezout ( v,
231 A, u, N, c, N2, c2, true );
232 trace.info() << "-> v = " << v << std::endl;
233 Integer a0 = ic.crossProduct(u,v);
234 nbok += ( ic.abs( a0 ) == 1 ) ? 1 : 0;
235 ++nb;
236 trace.info() << "(" << nbok << "/" << nb << ") "
237 << " v^u = " << a0 << " == +/- 1 " << std::endl;
238 // (A+v).N <= c , (A+v).N2 <= c2, (A+v+u).N2 > c2.
239 // Integer a1 = ic.dotProduct( A+v, N );
240 Integer a2 = ic.dotProduct( A+v, N2 );
241 Integer a3 = ic.dotProduct( A+v+u, N2 );
242 // nbok += a1 <= c ? 1 : 0;
243 // ++nb;
244 // trace.info() << "(" << nbok << "/" << nb << ") "
245 // << "(A+v).N = " << a1
246 // << " <= c = " << c << std::endl;
247 nbok += a2 <= c2 ? 1 : 0;
248 ++nb;
249 trace.info() << "(" << nbok << "/" << nb << ") "
250 << "(A+v).N2 = " << a2
251 << " <= c = " << c2 << std::endl;
252 nbok += a3 > c2 ? 1 : 0;
253 ++nb;
254 trace.info() << "(" << nbok << "/" << nb << ") "
255 << "(A+v+u).N2 = " << a2
256 << " > c2 = " << c2 << std::endl;
257 return nbok == nb;
258}
DGtal::IntegerComputer::crossProduct
Integer crossProduct(const Vector2I &u, const Vector2I &v) const
DGtal::IntegerComputer::abs
static Integer abs(IntegerParamType a)
DGtal::IntegerComputer::reduce
void reduce(Vector2I &p) const
DGtal::IntegerComputer::getValidBezout
void getValidBezout(Vector2I &v, const Point2I &A, const Vector2I &u, const Vector2I &N, IntegerParamType c, const Vector2I &N2, IntegerParamType c2, bool compute_v=true) const

References DGtal::IntegerComputer< TInteger >::abs(), DGtal::IntegerComputer< TInteger >::crossProduct(), DGtal::IntegerComputer< TInteger >::dotProduct(), DGtal::IntegerComputer< TInteger >::getValidBezout(), DGtal::Trace::info(), DGtal::IntegerComputer< TInteger >::reduce(), and DGtal::trace.

Referenced by testIntegerComputer().