src/paranoidnumber.cpp

   1 #include "paranoidnumber.h"
   2
   3 #include <sstream>
   4 #include <fenv.h>
   5 #include "log.h"
   6 #include <cassert>
   7 #include <iostream>
   8
   9 using namespace std;
  10 namespace IPDF
  11 {
  12
  13
  14 #ifdef PARANOID_USE_ARENA
  15 ParanoidNumber::Arena ParanoidNumber::g_arena;
  16 #endif //PARANOID_USE_ARENA
  17
  18 ParanoidNumber::~ParanoidNumber()
  19 {
  20         for (int i = 0; i < NOP; ++i)
  21         {
  22                 for (auto n : m_next[i])
  23                         delete n;
  24         }
  25 }
  26
  27 ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_next()
  28 {
  29         #ifdef PARANOID_SIZE_LIMIT
  30                 m_size = 0;
  31         #endif
  32         #ifdef PARANOID_CACHE_RESULTS
  33         m_cached_result = NAN;
  34         #endif
  35
  36         int dp = 0;
  37         int end = 0;
  38         while (str[dp] != '\0' && str[dp] != '.')
  39         {
  40                 ++dp;
  41                 ++end;
  42         }
  43         while (str[end] != '\0')
  44                 ++end;
  45         ParanoidNumber m(1);
  46         for (int i = dp-1; i >= 0; --i)
  47         {
  48                 ParanoidNumber b(str[i]-'0');
  49                 b*=m;
  50                 this->operator+=(b);
  51                 m*=10;
  52         }
  53         ParanoidNumber n(1);
  54         for (int i = dp+1; i < end; ++i)
  55         {
  56                 n/=10;
  57                 ParanoidNumber b(str[i]-'0');
  58                 b*=n;
  59                 this->operator+=(b);
  60         }
  61 }
  62
  63 ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
  64 {
  65         //assert(this != NULL);
  66
  67         #ifdef PARANOID_SIZE_LIMIT
  68                 m_size = a.m_size;
  69         #endif
  70
  71         m_value = a.m_value;
  72         #ifdef PARANOID_CACHE_RESULT
  73         m_cached_result = a.m_cached_result;
  74         #endif
  75         for (int i = 0; i < NOP; ++i)
  76         {
  77                 for (auto n : m_next[i])
  78                         delete n;
  79                 m_next[i].clear();
  80                 for (auto n : a.m_next[i])
  81                         m_next[i].push_back(new ParanoidNumber(*n));
  82         }
  83                 /*
  84                 for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j)
  85                 {
  86                         if (a.m_next[i][j] != NULL)
  87                                 m_next[i][j]->operator=(*(a.m_next[i][j]));
  88                 }
  89
  90                 for (unsigned j = a.m_next[i].size(); j < m_next[i].size(); ++j)
  91                 {
  92                         delete m_next[i][j];
  93                 }
  94                 m_next[i].resize(a.m_next[i].size());
  95                 */
  96         //}
  97         return *this;
  98 }
  99
 100
 101 string ParanoidNumber::Str() const
 102 {
 103
 104         //assert(this != NULL);
 105         string result("");
 106         stringstream s;
 107         s << (double)m_value;
 108         result += s.str();
 109         for (auto mul : m_next[MULTIPLY])
 110         {
 111                 result += "*";
 112                 if (!mul->Floating())
 113                         result += "(" + mul->Str() + ")";
 114                 else
 115                         result += mul->Str();
 116         }
 117         for (auto div : m_next[DIVIDE])
 118         {
 119                 result += "/";
 120                 if (!div->Floating())
 121                         result += "(" + div->Str() + ")";
 122                 else
 123                         result += div->Str();
 124         }
 125
 126         for (auto add : m_next[ADD])
 127         {
 128                 result += "+";
 129                 if (!add->Floating())
 130                         result += "(" + add->Str() + ")";
 131                 else
 132                         result += add->Str();
 133         }
 134         for (auto sub : m_next[SUBTRACT])
 135         {
 136                 result += "-";
 137                 if (!sub->Floating())
 138                         result += "(" + sub->Str() + ")";
 139                 else
 140                         result += sub->Str();
 141         }
 142
 143
 144         return result;
 145 }
 146
 147 template <>
 148 bool TrustingOp<float>(float & a, const float & b, Optype op)
 149 {
 150
 151
 152         feclearexcept(FE_ALL_EXCEPT);
 153         switch (op)
 154         {
 155                 case ADD:
 156                         a += b;
 157                         break;
 158                 case SUBTRACT:
 159                         a -= b;
 160                         break;
 161                 case MULTIPLY:
 162                         a *= b;
 163                         break;
 164                 case DIVIDE:
 165                         if (b == 0)
 166                         {
 167                                 a = (a >= 0) ? INFINITY : -INFINITY;
 168                                 return false;
 169                         }
 170
 171                         a /= b;
 172                         break;
 173                 case NOP:
 174                         break;
 175         }
 176         return !fetestexcept(FE_ALL_EXCEPT);
 177 }
 178
 179 template <>
 180 bool TrustingOp<double>(double & a, const double & b, Optype op)
 181 {
 182         feclearexcept(FE_ALL_EXCEPT);
 183         switch (op)
 184         {
 185                 case ADD:
 186                         a += b;
 187                         break;
 188                 case SUBTRACT:
 189                         a -= b;
 190                         break;
 191                 case MULTIPLY:
 192                         a *= b;
 193                         break;
 194                 case DIVIDE:
 195                         if (b == 0)
 196                         {
 197                                 a = (a >= 0) ? INFINITY : -INFINITY;
 198                                 return false;
 199                         }
 200                         a /= b;
 201                         break;
 202                 case NOP:
 203                         break;
 204         }
 205         return !fetestexcept(FE_ALL_EXCEPT);
 206 }
 207
 208
 209
 210 template <>
 211 bool TrustingOp<long double>(long double & a, const long double & b, Optype op)
 212 {
 213
 214
 215         feclearexcept(FE_ALL_EXCEPT);
 216         switch (op)
 217         {
 218                 case ADD:
 219                         a += b;
 220                         break;
 221                 case SUBTRACT:
 222                         a -= b;
 223                         break;
 224                 case MULTIPLY:
 225                         a *= b;
 226                         break;
 227                 case DIVIDE:
 228                         if (b == 0)
 229                         {
 230                                 a = (a >= 0) ? INFINITY : -INFINITY;
 231                                 return false;
 232                         }
 233
 234                         a /= b;
 235                         break;
 236                 case NOP:
 237                         break;
 238         }
 239         return !fetestexcept(FE_ALL_EXCEPT);
 240 }
 241
 242
 243 template <>
 244 bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
 245 {
 246         int16_t sa(a);
 247         bool exact = true;
 248         switch (op)
 249         {
 250                 case ADD:
 251                         sa += b;
 252                         exact = (abs(sa) <= 127);
 253                         break;
 254                 case SUBTRACT:
 255                         sa -= b;
 256                         exact = (abs(sa) <= 127);
 257                         break;
 258                 case MULTIPLY:
 259                         sa *= b;
 260                         exact = (abs(sa) <= 127);
 261                         break;
 262                 case DIVIDE:
 263                         exact = (b != 0 && sa > b && sa % b == 0);
 264                         sa /= b;
 265                         break;
 266                 case NOP:
 267                         break;
 268         }
 269         a = (int8_t)(sa);
 270         return exact;
 271 }
 272
 273
 274 ParanoidNumber & ParanoidNumber::operator+=(const digit_t & a)
 275 {
 276
 277         //assert(this != NULL);
 278         delete Operation(new ParanoidNumber(a), ADD);
 279         Simplify(ADD);
 280         Simplify(SUBTRACT);
 281         return *this;
 282 }
 283
 284
 285 ParanoidNumber & ParanoidNumber::operator-=(const digit_t & a)
 286 {
 287         delete Operation(new ParanoidNumber(a), SUBTRACT);
 288         Simplify(SUBTRACT);
 289         Simplify(ADD);
 290         return *this;
 291 }
 292
 293 ParanoidNumber & ParanoidNumber::operator*=(const digit_t & a)
 294 {
 295         delete Operation(new ParanoidNumber(a), MULTIPLY);
 296         Simplify(MULTIPLY);
 297         Simplify(DIVIDE);
 298         return *this;
 299 }
 300
 301
 302 ParanoidNumber & ParanoidNumber::operator/=(const digit_t & a)
 303 {
 304         delete Operation(new ParanoidNumber(a), DIVIDE);
 305         Simplify(MULTIPLY);
 306         Simplify(DIVIDE);
 307         return *this;
 308 }
 309
 310
 311 ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
 312 {
 313
 314         //assert(this != NULL);
 315         delete Operation(new ParanoidNumber(a), ADD);
 316         Simplify(ADD);
 317         Simplify(SUBTRACT);
 318         return *this;
 319 }
 320
 321
 322 ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
 323 {
 324         delete Operation(new ParanoidNumber(a), SUBTRACT);
 325         Simplify(SUBTRACT);
 326         Simplify(ADD);
 327         return *this;
 328 }
 329
 330 ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
 331 {
 332         delete Operation(new ParanoidNumber(a), MULTIPLY);
 333         Simplify(MULTIPLY);
 334         Simplify(DIVIDE);
 335         return *this;
 336 }
 337
 338
 339 ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
 340 {
 341         delete Operation(new ParanoidNumber(a), DIVIDE);
 342         Simplify(MULTIPLY);
 343         Simplify(DIVIDE);
 344         return *this;
 345 }
 346
 347 ParanoidNumber & ParanoidNumber::operator=(const digit_t & a)
 348 {
 349         for (int i = 0; i < NOP; ++i)
 350         {
 351                 for (auto n : m_next[i])
 352                         delete n;
 353         }
 354         m_value = a;
 355         #ifdef PARANOID_CACHE_RESULT
 356         m_cached_result = a;
 357         #endif
 358         return *this;
 359 }
 360
 361 // a + b
 362 ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
 363 {
 364         ////assert(b->SanityCheck());
 365         #ifdef PARANOID_CACHE_RESULTS
 366         m_cached_result = NAN;
 367         #endif
 368         #ifdef PARANOID_SIZE_LIMIT
 369                 if (m_size > PARANOID_SIZE_LIMIT)
 370                 {
 371                         if (op == ADD)
 372                                 m_value += b->Digit();
 373                         else
 374                                 m_value -= b->Digit();
 375                         return b;
 376                 }
 377                 //Debug("At size limit %d", m_size);
 378         #endif
 379
 380
 381         if (Floating() && m_value == 0) // 0 + b = b
 382         {
 383                 m_value = b->m_value;
 384                 if (op == SUBTRACT)
 385                 {
 386                         m_value = -m_value;
 387                         swap(b->m_next[ADD], b->m_next[SUBTRACT]);
 388                 }
 389
 390                 for (int i = 0; i < NOP; ++i)
 391                 {
 392                         m_next[i] = b->m_next[i];
 393                         b->m_next[i].clear();
 394                 }
 395
 396                 //assert(SanityCheck());
 397                 return b;
 398         }
 399         if (b->Floating() && b->m_value == 0) // a + 0 = a
 400                 return b;
 401
 402
 403
 404         if ((NoFactors() && b->NoFactors())
 405                 || (GetFactors() == b->GetFactors()))
 406         {
 407                 if (ParanoidOp<digit_t>(m_value, b->m_value, op))
 408                 {
 409                         Optype addop = (op == ADD) ? ADD : SUBTRACT;
 410                         for (auto add : b->m_next[ADD])
 411                         {
 412                                 delete (OperationTerm(add, addop));
 413                         }
 414                         Optype subop = (op == ADD) ? SUBTRACT : ADD;
 415                         for (auto sub : b->m_next[SUBTRACT])
 416                                 delete (OperationTerm(sub, subop));
 417
 418                         b->m_next[ADD].clear();
 419                         b->m_next[SUBTRACT].clear();
 420                         //assert(SanityCheck());
 421                         return b;
 422                 }
 423         }
 424
 425
 426
 427         bool parent = (merge_point == NULL);
 428         ParanoidNumber * merge = this;
 429         Optype mop = op;
 430         //assert(mop != NOP); // silence compiler warning
 431         if (parent)
 432         {
 433                 merge_point = &merge;
 434                 merge_op = &mop;
 435         }
 436         else
 437         {
 438                 merge = *merge_point;
 439                 mop = *merge_op;
 440         }
 441
 442         Optype invop = InverseOp(op); // inverse of p
 443         Optype fwd = op;
 444         Optype rev = invop;
 445         if (op == SUBTRACT)
 446         {
 447                 fwd = ADD;
 448                 rev = SUBTRACT;
 449         }
 450
 451         for (auto prev : m_next[invop])
 452         {
 453                 if (prev->OperationTerm(b, rev, merge_point, merge_op) == b)
 454                 {
 455                         //assert(SanityCheck());
 456                         return b;
 457                 }
 458
 459         }
 460         for (auto next : m_next[op])
 461         {
 462                 if (next->OperationTerm(b, fwd, merge_point, merge_op) == b)
 463                 {
 464                         //assert(SanityCheck());
 465                         return b;
 466                 }
 467         }
 468
 469
 470
 471
 472         if (parent)
 473         {
 474                 //merge->m_next[*merge_op].push_back(b);
 475                 m_next[op].push_back(b);
 476                 #ifdef PARANOID_SIZE_LIMIT
 477                         m_size += 1+b->m_size;
 478                 #endif
 479         }
 480         else
 481         {
 482                 if (m_next[op].size() == 0)
 483                 {
 484                         *merge_point = this;
 485                         *merge_op = op;
 486                 }
 487         }
 488
 489         //assert(SanityCheck());
 490
 491         return NULL;
 492 }
 493
 494 ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
 495 {
 496         //assert(SanityCheck());
 497         //assert(b->SanityCheck());
 498         #ifdef PARANOID_CACHE_RESULTS
 499         m_cached_result = NAN;
 500         #endif
 501         #ifdef PARANOID_SIZE_LIMIT
 502                 if (m_size > PARANOID_SIZE_LIMIT)
 503                 {
 504                         if (op == MULTIPLY)
 505                                 m_value *= b->Digit();
 506                         else
 507                                 m_value /= b->Digit();
 508                         //Debug("At size limit %d", m_size);
 509                         return b;
 510                 }
 511         #endif
 512
 513         if (Floating() && m_value == 0)
 514         {
 515                 return b;
 516         }
 517
 518         if (Floating() && m_value == 1 && op == MULTIPLY)
 519         {
 520                 m_value = b->m_value;
 521                 for (int i = 0; i < NOP; ++i)
 522                 {
 523                         for (auto n : m_next[i])
 524                                 delete (n);
 525                         m_next[i].clear();
 526                         swap(m_next[i], b->m_next[i]);
 527                 }
 528                 //assert(SanityCheck());
 529                 return b;
 530         }
 531         if (b->Floating() && b->m_value == 1)
 532                 return b;
 533
 534
 535
 536         if (NoTerms() && b->NoTerms())
 537         {
 538                 if (ParanoidOp<digit_t>(m_value, b->m_value, op))
 539                 {
 540                         Optype mulop = (op == MULTIPLY) ? MULTIPLY : DIVIDE;
 541                         for (auto mul : b->m_next[MULTIPLY])
 542                         {
 543                                 delete(OperationFactor(mul, mulop));
 544                         }
 545                         Optype divop = (op == MULTIPLY) ? DIVIDE : MULTIPLY;
 546                         for (auto div : b->m_next[DIVIDE])
 547                                 delete(OperationFactor(div, divop));
 548
 549                         b->m_next[DIVIDE].clear();
 550                         b->m_next[MULTIPLY].clear();
 551                         return b;
 552                 }
 553         }
 554
 555
 556         bool parent = (merge_point == NULL);
 557         ParanoidNumber * merge = this;
 558         Optype mop = op;
 559         if (parent)
 560         {
 561                 merge_point = &merge;
 562                 merge_op = &mop;
 563         }
 564         else
 565         {
 566                 merge = *merge_point;
 567                 mop = *merge_op;
 568         }
 569
 570         Optype invop = InverseOp(op); // inverse of p
 571         Optype fwd = op;
 572         Optype rev = invop;
 573         if (op == DIVIDE)
 574         {
 575                 fwd = MULTIPLY;
 576                 rev = DIVIDE;
 577         }
 578
 579         ParanoidNumber * cpy_b = new ParanoidNumber(*b);
 580         for (auto prev : m_next[invop])
 581         {
 582                 if (prev->OperationFactor(b, rev, merge_point, merge_op) == b)
 583                 {
 584                         for (auto add : m_next[ADD])
 585                                 delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op));
 586                         for (auto sub : m_next[SUBTRACT])
 587                                 delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op));
 588
 589                         delete(cpy_b);
 590                         return b;
 591                 }
 592         }
 593         for (auto next : m_next[op])
 594         {
 595                 if (next->OperationFactor(b, fwd, merge_point, merge_op) == b)
 596                 {
 597                         for (auto add : m_next[ADD])
 598                         {
 599                                 delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op));
 600                         }
 601                         for (auto sub : m_next[SUBTRACT])
 602                         {
 603                                 delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op));
 604                         }
 605                         delete(cpy_b);
 606                         return b;
 607                 }
 608         }
 609
 610         if (parent)
 611         {
 612                 //assert(b != NULL);
 613                 m_next[op].push_back(b);
 614                 for (auto add : m_next[ADD])
 615                         delete(add->OperationFactor(new ParanoidNumber(*cpy_b), op));
 616                 for (auto sub : m_next[SUBTRACT])
 617                         delete(sub->OperationFactor(new ParanoidNumber(*cpy_b), op));
 618
 619                 #ifdef PARANOID_SIZE_LIMIT
 620                         m_size += 1+b->m_size;
 621                 #endif
 622         }
 623         //assert(SanityCheck());
 624
 625
 626
 627         return NULL;
 628 }
 629
 630
 631
 632 /**
 633  * Performs the operation on a with argument b (a += b, a -= b, a *= b, a /= b)
 634  * @returns b if b can safely be deleted
 635  * @returns NULL if b has been merged with a
 636  * append indicates that b should be merged
 637  */
 638 ParanoidNumber * ParanoidNumber::Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
 639 {
 640
 641         if (b == NULL)
 642                 return NULL;
 643
 644
 645         if (op == SUBTRACT || op == ADD)
 646                 return OperationTerm(b, op, merge_point, merge_op);
 647         if (op == MULTIPLY || op == DIVIDE)
 648                 return OperationFactor(b, op, merge_point, merge_op);
 649         return b;
 650 }
 651
 652
 653
 654 string ParanoidNumber::PStr() const
 655 {
 656         stringstream s;
 657         for (int i = 0; i < NOP; ++i)
 658         {
 659                 Optype f = Optype(i);
 660                 s << this;
 661                 for (auto n : m_next[f])
 662                 {
 663                         s << OpChar(f) << n->PStr();
 664                 }
 665         }
 666         return s.str();
 667 }
 668
 669 bool ParanoidNumber::Simplify(Optype op)
 670 {
 671
 672         if (Floating())
 673                 return false;
 674
 675         //assert(SanityCheck());
 676         vector<ParanoidNumber*> next;
 677         next.clear();
 678         swap(m_next[op], next);
 679         m_next[op].clear();
 680         //assert(m_next[op].size() == 0);
 681         //assert(SanityCheck());
 682         Optype fwd = op;
 683         if (op == DIVIDE)
 684                 fwd = MULTIPLY;
 685         else if (op == SUBTRACT)
 686                 fwd = ADD;
 687
 688
 689         vector<ParanoidNumber*> hold[2];
 690         if (op == MULTIPLY || op == DIVIDE)
 691         {
 692                 swap(m_next[ADD], hold[0]);
 693                 swap(m_next[SUBTRACT], hold[1]);
 694         }
 695
 696         for (vector<ParanoidNumber*>::iterator n = next.begin(); n != next.end(); ++n)
 697         {
 698                 if (*n == NULL)
 699                         continue;
 700                 for (vector<ParanoidNumber*>::iterator m = n; m != next.end(); ++m)
 701                 {
 702                         if ((*m) == (*n))
 703                                 continue;
 704                         if (*m == NULL)
 705                                 continue;
 706
 707                         ParanoidNumber * parent = this;
 708                         Optype mop = op;
 709                         ParanoidNumber * result = (*n)->Operation(*m, fwd, &parent, &mop);
 710                         if (result != NULL)
 711                         {
 712                                 #ifdef PARANOID_SIZE_LIMIT
 713                                         m_size -= (1+result->m_size);
 714                                 #endif
 715                                 *m = NULL;
 716                                 delete(result);
 717                         }
 718                 }
 719         }
 720
 721
 722
 723         for (auto n : next)
 724         {
 725                 if (n != NULL)
 726                 {
 727                         #ifdef PARANOID_SIZE_LIMIT
 728                                 if (Operation(n, op) == n)
 729                                 {
 730                                         m_size -= (1+n->m_size);
 731                                         delete n;
 732                                 }
 733                         #else
 734                                 delete(Operation(n, op));
 735                         #endif
 736                 }
 737         }
 738
 739         if (op == MULTIPLY || op == DIVIDE)
 740         {
 741                 swap(m_next[ADD], hold[0]);
 742                 swap(m_next[SUBTRACT], hold[1]);
 743         }
 744
 745         set<ParanoidNumber*> s;
 746         //if (!SanityCheck(s))
 747         //{
 748         //      Error("Simplify broke Sanity");
 749         //}
 750         return (next.size() > m_next[op].size());
 751 }
 752
 753 bool ParanoidNumber::FullSimplify()
 754 {
 755         bool result = false;
 756         result |= Simplify(MULTIPLY);
 757         result |= Simplify(DIVIDE);
 758         result |= Simplify(ADD);
 759         result |= Simplify(SUBTRACT);
 760         return result;
 761 }
 762
 763 ParanoidNumber::digit_t ParanoidNumber::Digit() const
 764 {
 765
 766         // Get around the absurd requirement that const correctness be observed.
 767         #ifdef PARANOID_CACHE_RESULTS
 768         digit_t & result = ((ParanoidNumber*)(this))->m_cached_result;
 769
 770         if (!isnan(float(result))) // le sigh ambiguous function compiler warnings
 771                 return result;
 772         #else
 773                 digit_t result;
 774         #endif
 775         result = m_value;
 776         for (auto mul : m_next[MULTIPLY])
 777         {
 778                 result *= mul->Digit();
 779         }
 780         for (auto div : m_next[DIVIDE])
 781         {
 782                 result /= div->Digit();
 783         }
 784         for (auto add : m_next[ADD])
 785                 result += add->Digit();
 786         for (auto sub : m_next[SUBTRACT])
 787                 result -= sub->Digit();
 788         return result;
 789
 790 }
 791
 792 ParanoidNumber::digit_t ParanoidNumber::GetFactors() const
 793 {
 794         digit_t value = 1;
 795         for (auto mul : m_next[MULTIPLY])
 796                 value *= mul->Digit();
 797         for (auto div : m_next[DIVIDE])
 798                 value /= div->Digit();
 799         return value;
 800 }
 801
 802
 803 ParanoidNumber::digit_t ParanoidNumber::GetTerms() const
 804 {
 805         digit_t value = 0;
 806         for (auto add : m_next[ADD])
 807                 value += add->Digit();
 808         for (auto sub : m_next[SUBTRACT])
 809                 value -= sub->Digit();
 810         return value;
 811 }
 812
 813 bool ParanoidNumber::SanityCheck(set<ParanoidNumber*> & visited) const
 814 {
 815         if (this == NULL)
 816         {
 817                 Error("NULL pointer in tree");
 818                 return false;
 819         }
 820
 821         if (visited.find((ParanoidNumber*)this) != visited.end())
 822         {
 823                 Error("I think I've seen this tree before...");
 824                 return false;
 825         }
 826
 827         visited.insert((ParanoidNumber*)this);
 828
 829         for (auto add : m_next[ADD])
 830         {
 831                 if (!add->SanityCheck(visited))
 832                         return false;
 833         }
 834         for (auto sub : m_next[SUBTRACT])
 835         {
 836                 if (!sub->SanityCheck(visited))
 837                         return false;
 838         }
 839         for (auto mul : m_next[MULTIPLY])
 840         {
 841                 if (!mul->SanityCheck(visited))
 842                         return false;
 843         }
 844
 845         for (auto div : m_next[DIVIDE])
 846         {
 847                 if (!div->SanityCheck(visited))
 848                         return false;
 849         }
 850         return true;
 851 }
 852
 853 #ifdef PARANOID_USE_ARENA
 854
 855 void * ParanoidNumber::operator new(size_t s)
 856 {
 857         return g_arena.allocate(s);
 858 }
 859
 860 void ParanoidNumber::operator delete(void * p)
 861 {
 862         g_arena.deallocate(p);
 863 }
 864
 865 ParanoidNumber::Arena::Arena(int64_t block_size) : m_block_size(block_size), m_spare(NULL)
 866 {
 867         m_blocks.push_back({malloc(block_size*sizeof(ParanoidNumber)),0});
 868 }
 869
 870 ParanoidNumber::Arena::~Arena()
 871 {
 872         for (auto block : m_blocks)
 873         {
 874                 free(block.memory);
 875         }
 876         m_blocks.clear();
 877 }
 878
 879 void * ParanoidNumber::Arena::allocate(size_t s)
 880 {
 881         if (m_spare != NULL)
 882         {
 883                 void * result = m_spare;
 884                 m_spare = NULL;
 885                 return result;
 886         }
 887
 888         Block & b = m_blocks.back();
 889         void * result = (ParanoidNumber*)(b.memory) + (b.used++);
 890         if (b.used >= m_block_size)
 891         {
 892                 m_block_size *= 2;
 893                 Debug("Add block of size %d", m_block_size);
 894                 m_blocks.push_back({malloc(m_block_size*sizeof(ParanoidNumber)), 0});
 895         }
 896         return result;
 897 }
 898
 899 void ParanoidNumber::Arena::deallocate(void * p)
 900 {
 901         m_spare = p;
 902 }
 903 #endif //PARANOID_USE_ARENA
 904
 905 }