AngouriMath
WorkBudget
Description
Summary
What a computation is allowed to spend before it declines. A value, not a counter:
two budgets with the same ceilings are the same budget, and one can be reused,
shared and cached freely.
two budgets with the same ceilings are the same budget, and one can be reused,
shared and cached freely.
Remarks
work the algorithm does and so gives the same answer on every machine;
Time reads a clock and so does not. Both are here because they catch
different runaways — a computation can be spending a colossal number of cheap steps
or a handful of ruinous ones — but only the first can appear in an answer that is
supposed to be reproducible, which is why
IsDeterministic exists and why exhaustion says which
ceiling fired rather than only that one did
(#373).
not defined further: an algorithm charges where it would otherwise be able to loop,
and comparing step counts between two algorithms means nothing. What a step does
guarantee is that the count is a function of the input, so the same input exhausts at
the same point twice.
held are both named as budget axes by
#746 and neither
is counted anywhere in the library, so neither is a property here. A ceiling nothing
enforces reads as a promise, and the caller finds out it was not one by waiting.
Algorithm-specific ceilings — how many S-polynomial pairs, how wide a coefficient may
get — stay with the algorithm that knows what they mean; they are reported through
the same BudgetOutcome by name.
Members
Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online