check/exam_paranoia.cpp

   1 /** @file exam_paranoia.cpp
   2  *
   3  *  This set of tests checks for some of GiNaC's oopses which showed up during
   4  *  development.  Things were evaluated wrongly and so.  Such a sick behaviour
   5  *  shouldn't occur any more.  But we are paranoic and we want to exclude these
   6  *  these oopses for good, so we run those stupid tests... */
   7
   8 /*
   9  *  GiNaC Copyright (C) 1999-2005 Johannes Gutenberg University Mainz, Germany
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License
  22  *  along with this program; if not, write to the Free Software
  23  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  24  */
  25
  26 #include "exams.h"
  27
  28 // The very first pair of historic problems had its roots in power.cpp and was
  29 // finally resolved on April 27th 1999. (Fixing the first on April 23rd
  30 // actually introduced the second.)
  31 static unsigned exam_paranoia1()
  32 {
  33         unsigned result = 0;
  34         symbol x("x"), y("y"), z("z");
  35         ex e, f, g;
  36
  37         e = x * y * z;
  38         f = y * z;
  39         g = e / f;
  40
  41         // In the first one expand did not do any job at all:
  42         if (!g.expand().is_equal(x)) {
  43                 clog << "e = x*y*z; f = y*z; expand(e/f) erroneously returned "
  44                      << g.expand() << endl;
  45                 ++result;
  46         }
  47
  48         // This one somehow used to return 0:
  49         e = pow(x + 1, -1);
  50         if (!e.expand().is_equal(e)) {
  51                 clog << "expand(pow(x + 1, -1)) erroneously returned "
  52                      << e.expand() << endl;
  53                 ++result;
  54         }
  55
  56         return result;
  57 }
  58
  59 // And here the second oops which showed up until May 17th 1999.  It had to do
  60 // with lexicographic canonicalization and thus showed up only if the variables
  61 // had the names as given here:
  62 static unsigned exam_paranoia2()
  63 {
  64         unsigned result = 0;
  65         symbol x("x"), y("y"), z("z");
  66         ex e, f, g;
  67
  68         e = x + z*x;
  69         f = e*y;
  70         g = f - e*y;
  71
  72         // After .expand(), g should be zero:
  73         if (!g.expand().is_zero()) {
  74                 clog << "e = (x + z*x); f = e*y; expand(f - e*y) erroneously returned "
  75                      << g.expand() << endl;
  76                 ++result;
  77         }
  78         // After .eval(), g should be zero:
  79         if (!g.eval().is_zero()) {
  80                 clog << "e = (x + z*x); f = e*y; eval(f - e*y) erroneously returned "
  81                      << g.eval() << endl;
  82                 ++result;
  83         }
  84         // This actually worked already back in April 1999.
  85         // But we are *very* paranoic!
  86         if (!g.expand().eval().is_zero()) {
  87                 clog << "e = (x + z*x); f = e*y; eval(expand(f - e*y)) erroneously returned "
  88                      << g.expand().eval() << endl;
  89                 ++result;
  90         }
  91
  92         return result;
  93 }
  94
  95 // The third bug was introduced on May 18th 1999, discovered on May 19 and
  96 // fixed that same day.  It worked when x was substituted by 1 but not with
  97 // other numbers:
  98 static unsigned exam_paranoia3()
  99 {
 100         unsigned result = 0;
 101         symbol x("x"), y("y");
 102         ex e, f;
 103
 104         e = x*y - y;
 105         f = e.subs(x == 2);
 106
 107         if (!f.is_equal(y)) {
 108                 clog << "e = x*y - y; f = e.subs(x == 2) erroneously returned "
 109                      << f << endl;
 110                 ++result;
 111         }
 112         if (!f.eval().is_equal(y)) {
 113                 clog << "e = x*y - y; eval(e.subs(x == 2)) erroneously returned "
 114                      << f.eval() << endl;
 115                 ++result;
 116         }
 117         if (!f.expand().is_equal(y)) {
 118                 clog << "e = x*y - y; expand(e.subs(x == 2)) erroneously returned "
 119                      << f.expand() << endl;
 120                 ++result;
 121         }
 122
 123         return result;
 124 }
 125
 126 // The fourth bug was also discovered on May 19th 1999 and fixed immediately:
 127 static unsigned exam_paranoia4()
 128 {
 129         unsigned result = 0;
 130         symbol x("x");
 131         ex e, f, g;
 132
 133         e = pow(x, 2) + x + 1;
 134         f = pow(x, 2) + x + 1;
 135         g = e - f;
 136
 137         if (!g.is_zero()) {
 138                 clog << "e = pow(x,2) + x + 1; f = pow(x,2) + x + 1; g = e-f; g erroneously returned "
 139                      << g << endl;
 140                 ++result;
 141         }
 142         if (!g.is_zero()) {
 143                 clog << "e = pow(x,2) + x + 1; f = pow(x,2) + x + 1; g = e-f; g.eval() erroneously returned "
 144                      << g.eval() << endl;
 145                 ++result;
 146         }
 147
 148         return result;
 149 }
 150
 151 // The fifth oops was discovered on May 20th 1999 and fixed a day later:
 152 static unsigned exam_paranoia5()
 153 {
 154         unsigned result = 0;
 155         symbol x("x"), y("y");
 156
 157         ex e, f;
 158         e = pow(x*y + 1, 2);
 159         f = pow(x, 2) * pow(y, 2) + 2*x*y + 1;
 160
 161         if (!(e-f).expand().is_zero()) {
 162                 clog << "e = pow(x*y+1,2); f = pow(x,2)*pow(y,2) + 2*x*y + 1; (e-f).expand() erroneously returned "
 163                      << (e-f).expand() << endl;
 164                 ++result;
 165         }
 166
 167         return result;
 168 }
 169
 170 // This one was discovered on Jun 1st 1999 and fixed the same day:
 171 static unsigned exam_paranoia6()
 172 {
 173         unsigned result = 0;
 174         symbol x("x");
 175
 176         ex e, f;
 177         e = pow(x, -5);
 178         f = e.denom();
 179
 180         if (!f.is_equal(pow(x, 5))) {
 181                 clog << "e = pow(x, -5); f = e.denom(); f was " << f << " (should be x^5)" << endl;
 182                 ++result;
 183         }
 184         return result;
 185 }
 186
 187 // This one was introduced on June 1st 1999 by some aggressive manual
 188 // optimization. Discovered and fixed on June 2nd.
 189 static unsigned exam_paranoia7()
 190 {
 191         unsigned result = 0;
 192         symbol x("x"), y("y");
 193
 194         ex e = y + y*x + 2;
 195         ex f = expand(pow(e, 2) - (e*y*(x + 1)));
 196
 197         if (f.nops() > 3) {
 198                 clog << "e=y+y*x+2; f=expand(pow(e,2)-(e*y*(x+1))) has "
 199                      << f.nops() << " arguments instead of 3 ( f=="
 200                      << f << " )" << endl;
 201                 ++result;
 202         }
 203         return result;
 204 }
 205
 206 // This one was a result of the rewrite of mul::max_coefficient when we
 207 // introduced the overall_coefficient field in expairseq objects on Oct 1st
 208 // 1999. Fixed on Oct 4th.
 209 static unsigned exam_paranoia8()
 210 {
 211         unsigned result = 0;
 212         symbol x("x");
 213
 214         ex e = -x / (x+1);
 215         ex f;
 216
 217         try {
 218                 f = e.normal();
 219                 if (!f.is_equal(e)) {
 220                         clog << "normal(-x/(x+1)) returns " << f << " instead of -x/(x+1)\n";
 221                         ++result;
 222                 }
 223         } catch (const exception &err) {
 224                 clog << "normal(-x/(x+1) throws " << err.what() << endl;
 225                 ++result;
 226         }
 227         return result;
 228 }
 229
 230 // This one was a result of a modification to frac_cancel() & Co. to avoid
 231 // expanding the numerator and denominator when bringing them from Q[X] to
 232 // Z[X]. multiply_lcm() forgot to multiply the x-linear term with the LCM of
 233 // the coefficient's denominators (2 in this case).  Introduced on Jan 25th
 234 // 2000 and fixed on Jan 31th.
 235 static unsigned exam_paranoia9()
 236 {
 237         unsigned result = 0;
 238         symbol x("x");
 239
 240         ex e = (exp(-x)-2*x*exp(-x)+pow(x,2)/2*exp(-x))/exp(-x);
 241         ex f = e.normal();
 242
 243         if (!f.is_equal(1-2*x+pow(x,2)/2)) {
 244                 clog << "normal(" << e << ") returns " << f << " instead of 1-2*x+1/2*x^2\n";
 245                 ++result;
 246         }
 247         return result;
 248 }
 249
 250 // I have no idea when this broke.  It has been working long ago, before 0.4.0
 251 // and on Feb 13th 2000 I found out that things like 2^(3/2) throw an exception
 252 // "power::eval(): pow(0,0) is undefined" instead of simplifying to 2*2^(1/2).
 253 // It was fixed that same day.
 254 static unsigned exam_paranoia10()
 255 {
 256         unsigned result = 0;
 257
 258         ex b = numeric(2);
 259         ex e = numeric(3,2);
 260         ex r;
 261
 262         try {
 263                 r = pow(b,e).eval();
 264                 if (!(r-2*sqrt(ex(2))).is_zero()) {
 265                         clog << "2^(3/2) erroneously returned " << r << " instead of 2*sqrt(2)" << endl;
 266                         ++result;
 267                 }
 268         } catch (const exception &err) {
 269                 clog << "2^(3/2) throws " << err.what() << endl;
 270                 ++result;
 271         }
 272         return result;
 273 }
 274
 275 // After the rewriting of basic::normal() & Co. to return {num, den} lists,
 276 // add::normal() forgot to multiply the denominator of the overall_coeff of
 277 // its expanded and normalized children with the denominator of the expanded
 278 // child (did you get this? Well, never mind...). Fixed on Feb 21th 2000.
 279 static unsigned exam_paranoia11()
 280 {
 281         unsigned result = 0;
 282         symbol x("x");
 283
 284         ex e = ((-5-2*x)-((2-5*x)/(-2+x))*(3+2*x))/(5-4*x);
 285         ex f = e.normal();
 286         ex d = (4+10*x+8*pow(x,2))/(x-2)/(5-4*x);
 287
 288         if (!(f - d).expand().is_zero()) {
 289                 clog << "normal(" << e << ") returns " << f << " instead of " << d << endl;
 290                 ++result;
 291         }
 292         return result;
 293 }
 294
 295 // This one returned 0 because add::normal() incorrectly assumed that if the
 296 // common denominator is 1, all the denominators would be 1 (they can in fact
 297 // be +/-1). Fixed on Aug 2nd 2000.
 298 static unsigned exam_paranoia12()
 299 {
 300         unsigned result = 0;
 301         symbol x("x");
 302
 303         ex e = 2-2*(1+x)/(-1-x);
 304         ex f = e.normal();
 305         ex d = 4;
 306
 307         if (!(f - d).expand().is_zero()) {
 308                 clog << "normal(" << e << ") returns " << f
 309                      << " instead of " << d << endl;
 310                 ++result;
 311         }
 312         return result;
 313 }
 314
 315 // This one caused a division by 0 because heur_gcd() didn't check its
 316 // input polynomials against 0. Fixed on Aug 4th 2000.
 317 static unsigned exam_paranoia13()
 318 {
 319         unsigned result = 0;
 320         symbol a("a"), b("b"), c("c");
 321
 322         ex e = (b*a-c*a)/(4-a);
 323         ex d = (c*a-b*a)/(a-4);
 324
 325         try {
 326                 ex f = e.normal();
 327                 if (!(f - d).expand().is_zero()) {
 328                         clog << "normal(" << e << ") returns " << f
 329                              << " instead of " << d << endl;
 330                         ++result;
 331                 }
 332         } catch (const exception &err) {
 333                 clog << "normal(" << e << ") throws " << err.what() << endl;
 334                 ++result;
 335         }
 336         return result;
 337 }
 338
 339 // A bug introduced on July 19, 2001. quo() and rem() would sometimes call
 340 // vector::reserve() with a negative argument. Fixed on Dec 20, 2001.
 341 static unsigned exam_paranoia14()
 342 {
 343         unsigned result = 0;
 344         symbol x("x");
 345
 346         ex q = quo(1, pow(x, 3), x);
 347         if (!q.is_zero()) {
 348                 clog << "quo(1,x^3,x) erroneously returned " << q << " instead of 0\n";
 349                 ++result;
 350         }
 351
 352         return result;
 353 }
 354
 355 // Under certain conditions, power::expand_add_2() could produce non-canonical
 356 // numeric expairs. Fixed on Oct 24, 2002.
 357 static unsigned exam_paranoia15()
 358 {
 359         unsigned result = 0;
 360
 361         ex q = (pow(pow(2, numeric(1, 2))*2+1, 2)).expand();
 362         // this used to produce "1+4*sqrt(2)+4*2" which would never evaluate
 363         // to "9+4*sqrt(2)"
 364
 365         if (!(q-9-4*pow(2, numeric(1, 2))).is_zero()) {
 366                 clog << "expand((sqrt(2)*2+1)^2) erroneously returned " << q << " instead of 9-4*sqrt(2)\n";
 367                 ++result;
 368         }
 369
 370         return result;
 371 }
 372
 373 // Expanding products containing powers of sums could return results that
 374 // were not fully expanded. Fixed on Dec 10, 2003.
 375 static unsigned exam_paranoia16()
 376 {
 377         unsigned result = 0;
 378         symbol a("a"), b("b"), c("c"), d("d"), e("e");
 379         ex e1, e2, e3;
 380
 381         e1 = pow(1+a*sqrt(b+c), 2);
 382         e2 = e1.expand();
 383
 384         if (e2.has(pow(a, 2)*(b+c))) {
 385                 clog << "expand(" << e1 << ") didn't fully expand\n";
 386                 ++result;
 387         }
 388
 389         e1 = (d*sqrt(a+b)+a*sqrt(c+d))*(b*sqrt(a+b)+a*sqrt(c+d));
 390         e2 = e1.expand();
 391
 392         if (e2.has(pow(a, 2)*(c+d))) {
 393                 clog << "expand(" << e1 << ") didn't fully expand\n";
 394                 ++result;
 395         }
 396
 397         e1 = (a+sqrt(b+c))*sqrt(b+c)*(d+sqrt(b+c));
 398         e2 = e1.expand();
 399
 400         if (e2.has(a*(b+c))) {
 401                 clog << "expand(" << e1 << ") didn't fully expand\n";
 402                 ++result;
 403         }
 404
 405         e1 = pow(sqrt(a+b)+sqrt(c+d), 3);
 406         e2 = e1.expand();
 407
 408         if (e2.has(3*(a+b)*sqrt(c+d)) || e2.has(3*(c+d)*sqrt(a+b))) {
 409                 clog << "expand(" << e1 << ") didn't fully expand\n";
 410                 ++result;
 411         }
 412
 413         e1 = a*(b+c*(d+e));
 414         e2 = e1.expand();
 415
 416         if (e2.has(c*(d+e))) {
 417                 clog << "expand(" << e1 << ") didn't fully expand\n";
 418                 ++result;
 419         }
 420
 421         e1 = 2*pow(1+a, 2)/a;
 422         e2 = e1.expand();
 423
 424         if (e2.has(pow(a, 2))) {
 425                 clog << "expand(" << e1 << ") didn't fully expand\n";
 426                 ++result;
 427         }
 428
 429         e1 = a*(a+b);
 430         e2 = pow(pow(e1, -1), -1);
 431
 432         if (e2.has(a*b)) {
 433                 clog << "double reciprocal expanded where it should not\n";
 434                 ++result;
 435         }
 436
 437         return result;
 438 }
 439
 440 unsigned exam_paranoia()
 441 {
 442         unsigned result = 0;
 443
 444         cout << "examining several historic failures just out of paranoia" << flush;
 445         clog << "----------several historic failures:" << endl;
 446
 447         result += exam_paranoia1();  cout << '.' << flush;
 448         result += exam_paranoia2();  cout << '.' << flush;
 449         result += exam_paranoia3();  cout << '.' << flush;
 450         result += exam_paranoia4();  cout << '.' << flush;
 451         result += exam_paranoia5();  cout << '.' << flush;
 452         result += exam_paranoia6();  cout << '.' << flush;
 453         result += exam_paranoia7();  cout << '.' << flush;
 454         result += exam_paranoia8();  cout << '.' << flush;
 455         result += exam_paranoia9();  cout << '.' << flush;
 456         result += exam_paranoia10();  cout << '.' << flush;
 457         result += exam_paranoia11();  cout << '.' << flush;
 458         result += exam_paranoia12();  cout << '.' << flush;
 459         result += exam_paranoia13();  cout << '.' << flush;
 460         result += exam_paranoia14();  cout << '.' << flush;
 461         result += exam_paranoia15();  cout << '.' << flush;
 462         result += exam_paranoia16();  cout << '.' << flush;
 463
 464         if (!result) {
 465                 cout << " passed " << endl;
 466                 clog << "(no output)" << endl;
 467         } else {
 468                 cout << " failed " << endl;
 469         }
 470
 471         return result;
 472 }