[moonchild]

feel free to ping on irc if interested in chatting more on the topic, though i'm not sure i have a ton more original thoughts atm

if you have an expression with n terms, then you will end up with O(n) terms each taking up O(n) space, so the overall space usage is quadratic. (that's the fair way to compare to polyhedra since they're always global)

[kragen]

what's the scenario where you'd materialize the values of all those terms at once? maybe cache-invalidation-based incremental evaluation, like acar's self-adjusting computation? affine arithmetic (or raa) seems like it could be a good fit for that kind of thing, because it can handle small input changes within the affine approximation (with just a multiply-accumulate) and sometimes would benefit from being able to recursively subdivide the input space into smaller intervals without recomputing unaffected parts of the expression

on the other hand, if i am merely evaluating a polynomial with n terms, such as 3x⁴ - 2x³ + 17x² + x - 4 for n = 5, i only have three aa objects at any one time during evaluation of the expression, regardless of n. in this case the program might look like this

    a ← x; a ← a⁴; b ← 3; a ← a · b
    b ← x; b ← b³; c ← -2; b ← b · c; a ← a + b
    b ← x; b ← b²; c ← 17; b ← b · c; a ← a + b
    b ← x; a ← a + b
    b ← -4; a ← a + b

this assumes we have three registers for aa objects, creatively called a, b, and c; that we can only do arithmetic on these registers; and that the power operations are unary (otherwise they require an additional register)

this is true of any polynomial

with horner's-rule evaluation we can cut this down to two registers

    a ← 3
    b ← x; a ← a · b; b ← -2; a ← a + b
    b ← x; a ← a · b; b ← 17; a ← a + b
    b ← x; a ← a · b; b ← 1;  a ← a + b
    b ← x; a ← a · b; b ← -4; a ← a + b

obviously there do exist expressions with deeper minimum evaluation stacks, but i think they're only worst-case logarithmic in expression size, aren't they?

[moonchild]

(dynamic) computation forms a dag, not a tree. i think a sum scan (n inputs -> n outputs) will trigger the worst case. it might be that computations tend to be tree-shaped, so you rarely hit the worst case, but that helps everybody out, not just affine arithmetic

[kragen]

that's a good point; i was thinking of single-output expressions, where i think always evaluating the deepest subtree first limits your space usage to worst-case logarithmic?

[moonchild]

even single-output is a dag; you can explode the dag into a tree, but then you pay in time. suppose some expensive term x is used to compute n other terms. after computing x, assuming we want to share it, we have to compute all n terms before killing x; hence x sticks around longer than it might. (this doesn't necessarily lead to explosion, but i'm pretty sure you can use this to construct a scenario that needs a large number of live terms to avoid compromising time complexity; at least n live terms if the dag has nlogn nodes)