1 #include "paranoidnumber.h"
12 int64_t ParanoidNumber::g_count = 0;
15 ParanoidNumber::~ParanoidNumber()
18 for (int i = 0; i < NOP; ++i)
20 for (auto n : m_next[i])
25 ParanoidNumber::ParanoidNumber(const string & str) : m_value(0), m_cached_result(0), m_cache_valid(false), m_next()
30 while (str[dp] != '\0' && str[dp] != '.')
35 while (str[end] != '\0')
38 for (int i = dp-1; i >= 0; --i)
40 ParanoidNumber b(str[i]-'0');
46 for (int i = dp+1; i < end; ++i)
49 ParanoidNumber b(str[i]-'0');
55 ParanoidNumber & ParanoidNumber::operator=(const ParanoidNumber & a)
59 m_cached_result = a.m_cached_result;
60 for (int i = 0; i < NOP; ++i)
62 for (auto n : m_next[i])
65 for (auto n : a.m_next[i])
66 m_next[i].push_back(new ParanoidNumber(*n));
69 for (unsigned j = 0; j < m_next[i].size() && j < a.m_next[i].size(); ++j)
71 if (a.m_next[i][j] != NULL)
72 m_next[i][j]->operator=(*(a.m_next[i][j]));
75 for (unsigned j = a.m_next[i].size(); j < m_next[i].size(); ++j)
79 m_next[i].resize(a.m_next[i].size());
86 string ParanoidNumber::Str() const
94 for (auto mul : m_next[MULTIPLY])
98 result += "(" + mul->Str() + ")";
100 result += mul->Str();
102 for (auto div : m_next[DIVIDE])
105 if (!div->Floating())
106 result += "(" + div->Str() + ")";
108 result += div->Str();
111 for (auto add : m_next[ADD])
114 if (!add->Floating())
115 result += "(" + add->Str() + ")";
117 result += add->Str();
119 for (auto sub : m_next[SUBTRACT])
122 if (!sub->Floating())
123 result += "(" + sub->Str() + ")";
125 result += sub->Str();
133 bool TrustingOp<float>(float & a, const float & b, Optype op)
136 feclearexcept(FE_ALL_EXCEPT);
151 a = (a >= 0) ? INFINITY : -INFINITY;
160 return !fetestexcept(FE_ALL_EXCEPT);
164 bool TrustingOp<double>(double & a, const double & b, Optype op)
166 feclearexcept(FE_ALL_EXCEPT);
181 a = (a >= 0) ? INFINITY : -INFINITY;
189 return !fetestexcept(FE_ALL_EXCEPT);
193 bool TrustingOp<int8_t>(int8_t & a, const int8_t & b, Optype op)
201 exact = (abs(sa) <= 127);
205 exact = (abs(sa) <= 127);
209 exact = (abs(sa) <= 127);
212 exact = (b != 0 && sa > b && sa % b == 0);
223 ParanoidNumber & ParanoidNumber::operator+=(const ParanoidNumber & a)
226 assert(this != NULL);
227 delete Operation(SafeConstruct(a), ADD);
234 ParanoidNumber & ParanoidNumber::operator-=(const ParanoidNumber & a)
236 delete Operation(SafeConstruct(a), SUBTRACT);
242 ParanoidNumber & ParanoidNumber::operator*=(const ParanoidNumber & a)
244 delete Operation(SafeConstruct(a), MULTIPLY);
251 ParanoidNumber & ParanoidNumber::operator/=(const ParanoidNumber & a)
253 delete Operation(SafeConstruct(a), DIVIDE);
260 ParanoidNumber * ParanoidNumber::OperationTerm(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
266 assert(b->SanityCheck());
268 m_cached_result = nan("");
269 if (Floating() && m_value == 0) // 0 + b = b
271 m_value = b->m_value;
275 swap(b->m_next[ADD], b->m_next[SUBTRACT]);
278 for (int i = 0; i < NOP; ++i)
280 m_next[i] = b->m_next[i];
281 b->m_next[i].clear();
284 assert(SanityCheck());
287 if (b->Floating() && b->m_value == 0) // a + 0 = a
292 if ((NoFactors() && b->NoFactors())
293 || (GetFactors() == b->GetFactors()))
295 if (ParanoidOp<digit_t>(m_value, b->m_value, op))
297 Optype addop = (op == ADD) ? ADD : SUBTRACT;
298 for (auto add : b->m_next[ADD])
300 delete OperationTerm(add, addop);
302 Optype subop = (op == ADD) ? SUBTRACT : ADD;
303 for (auto sub : b->m_next[SUBTRACT])
304 delete OperationTerm(sub, subop);
306 b->m_next[ADD].clear();
307 b->m_next[SUBTRACT].clear();
308 assert(SanityCheck());
315 bool parent = (merge_point == NULL);
316 ParanoidNumber * merge = this;
318 assert(mop != NOP); // silence compiler warning
321 merge_point = &merge;
326 merge = *merge_point;
330 Optype invop = InverseOp(op); // inverse of p
339 for (auto prev : m_next[invop])
341 if (prev->OperationTerm(b, rev, merge_point, merge_op) == b)
343 assert(SanityCheck());
348 for (auto next : m_next[op])
350 if (next->OperationTerm(b, fwd, merge_point, merge_op) == b)
352 assert(SanityCheck());
362 //merge->m_next[*merge_op].push_back(b);
363 m_next[op].push_back(b);
367 if (m_next[op].size() == 0)
374 assert(SanityCheck());
378 ParanoidNumber * ParanoidNumber::OperationFactor(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
380 assert(SanityCheck());
381 assert(b->SanityCheck());
382 m_cached_result = nan("");
383 if (Floating() && m_value == 0)
388 if (Floating() && m_value == 1 && op == MULTIPLY)
390 m_value = b->m_value;
391 for (int i = 0; i < NOP; ++i)
393 for (auto n : m_next[i])
396 swap(m_next[i], b->m_next[i]);
398 assert(SanityCheck());
401 if (b->Floating() && b->m_value == 1)
406 if (NoTerms() && b->NoTerms())
408 if (ParanoidOp<digit_t>(m_value, b->m_value, op))
410 Optype mulop = (op == MULTIPLY) ? MULTIPLY : DIVIDE;
411 for (auto mul : b->m_next[MULTIPLY])
413 delete OperationFactor(mul, mulop);
415 Optype divop = (op == MULTIPLY) ? DIVIDE : MULTIPLY;
416 for (auto div : b->m_next[DIVIDE])
417 delete OperationFactor(div, divop);
419 b->m_next[DIVIDE].clear();
420 b->m_next[MULTIPLY].clear();
423 assert(SanityCheck());
429 bool parent = (merge_point == NULL);
430 ParanoidNumber * merge = this;
434 merge_point = &merge;
439 merge = *merge_point;
443 Optype invop = InverseOp(op); // inverse of p
452 ParanoidNumber * cpy_b = NULL;
454 if (m_next[ADD].size() > 0 || m_next[SUBTRACT].size() > 0)
456 cpy_b = SafeConstruct(*b);
459 for (auto prev : m_next[invop])
461 if (prev->OperationFactor(b, rev, merge_point, merge_op) == b)
463 for (auto add : m_next[ADD])
464 delete add->OperationFactor(SafeConstruct(*cpy_b), op);
465 for (auto sub : m_next[SUBTRACT])
466 delete sub->OperationFactor(SafeConstruct(*cpy_b), op);
469 assert(SanityCheck());
473 for (auto next : m_next[op])
475 if (next->OperationFactor(b, fwd, merge_point, merge_op) == b)
477 for (auto add : m_next[ADD])
479 delete add->OperationFactor(SafeConstruct(*cpy_b), op);
481 for (auto sub : m_next[SUBTRACT])
483 delete sub->OperationFactor(SafeConstruct(*cpy_b), op);
486 assert(SanityCheck());
494 m_next[op].push_back(b);
495 for (auto add : m_next[ADD])
496 delete add->OperationFactor(SafeConstruct(*cpy_b), op);
497 for (auto sub : m_next[SUBTRACT])
498 delete sub->OperationFactor(SafeConstruct(*cpy_b), op);
500 assert(SanityCheck());
507 * Performs the operation on a with argument b (a += b, a -= b, a *= b, a /= b)
508 * @returns b if b can safely be deleted
509 * @returns NULL if b has been merged with a
510 * append indicates that b should be merged
512 ParanoidNumber * ParanoidNumber::Operation(ParanoidNumber * b, Optype op, ParanoidNumber ** merge_point, Optype * merge_op)
519 if (op == SUBTRACT || op == ADD)
520 return OperationTerm(b, op, merge_point, merge_op);
521 if (op == MULTIPLY || op == DIVIDE)
522 return OperationFactor(b, op, merge_point, merge_op);
528 string ParanoidNumber::PStr() const
531 for (int i = 0; i < NOP; ++i)
533 Optype f = Optype(i);
535 for (auto n : m_next[f])
537 s << OpChar(f) << n->PStr();
543 bool ParanoidNumber::Simplify(Optype op)
548 assert(SanityCheck());
549 vector<ParanoidNumber*> next;
551 swap(m_next[op], next);
553 assert(m_next[op].size() == 0);
554 assert(SanityCheck());
558 else if (op == SUBTRACT)
562 for (vector<ParanoidNumber*>::iterator n = next.begin(); n != next.end(); ++n)
566 for (vector<ParanoidNumber*>::iterator m = n; m != next.end(); ++m)
573 ParanoidNumber * parent = this;
575 ParanoidNumber * result = (*n)->Operation(*m, fwd, &parent, &mop);
583 delete Operation(*n, op);
585 set<ParanoidNumber*> s;
588 Error("Simplify broke Sanity");
590 return (next.size() > m_next[op].size());
593 bool ParanoidNumber::FullSimplify()
596 result |= Simplify(MULTIPLY);
597 result |= Simplify(DIVIDE);
598 result |= Simplify(ADD);
599 result |= Simplify(SUBTRACT);
603 ParanoidNumber::digit_t ParanoidNumber::Digit() const
609 //if (!isnan(m_cached_result))
610 // return m_cached_result;
612 // Get around the absurd requirement that const correctness be observed.
613 digit_t result;// = ((ParanoidNumber*)(this))->m_cached_result;
615 for (auto mul : m_next[MULTIPLY])
617 result *= mul->Digit();
619 for (auto div : m_next[DIVIDE])
621 result /= div->Digit();
623 for (auto add : m_next[ADD])
624 result += add->Digit();
625 for (auto sub : m_next[SUBTRACT])
626 result -= sub->Digit();
631 ParanoidNumber::digit_t ParanoidNumber::GetFactors() const
634 for (auto mul : m_next[MULTIPLY])
635 value *= mul->Digit();
636 for (auto div : m_next[DIVIDE])
637 value /= div->Digit();
642 ParanoidNumber::digit_t ParanoidNumber::GetTerms() const
645 for (auto add : m_next[ADD])
646 value += add->Digit();
647 for (auto sub : m_next[SUBTRACT])
648 value -= sub->Digit();
652 bool ParanoidNumber::SanityCheck(set<ParanoidNumber*> & visited) const
656 Error("NULL pointer in tree");
660 if (visited.find((ParanoidNumber*)this) != visited.end())
662 Error("I think I've seen this tree before...");
666 visited.insert((ParanoidNumber*)this);
668 for (auto add : m_next[ADD])
670 if (!add->SanityCheck(visited))
673 for (auto sub : m_next[SUBTRACT])
675 if (!sub->SanityCheck(visited))
678 for (auto mul : m_next[MULTIPLY])
680 if (!mul->SanityCheck(visited))
684 for (auto div : m_next[DIVIDE])
686 if (!div->SanityCheck(visited))