|
How do we define "closed form" ?
I was thinking about this the other day.
Suppose I want the 6th Fibonacci number.
Well, I could do it in the "non-closed" form where I say
1+1 is 2, 1+2 is 3, 2+3 is 5, 3+5 is 8, 5+8 is 13
So the essence of "non-closed" seems to be that we do some sort of iterative
process to get our answer.
But then some mathematician comes along and presents the "closed form" for
Fibonacci numbers as
(1+sqr(5))^n - (1-sqr(5))^n
f(n) = ---------------------------
sqr(5)* 2^n
However, it still seems like I have to do an iterative process to compute
Fibonacci numbers using this formula, since unless I use some sort of log tables
I'll end up computing the nth power by iteratively multiplying.
Why is the interative multiplying to compute nth power considered "closed form"
but the iterative adding of previous two terms considered "non-closed form" ?
/Eric
|
| "Closed form" is not defined in any consistent fashion. It depends
on context. A particular expression is considered of "closed form"
only relative to some set of predetermined functions and operators.
Generally it includes +, -, *, /, and "standard" transcendental
functions such as log, exp, sin, hsin, etc. (Once you have log and exp
you may as well have the power operator), plus some assorted others
like sgn, and abs. Depending on context, other functions may be
included, such as the error function.
What is always excluded is explicit use of indefinite numeric
"quantifiers", such as sigma (sum), pi (product), and various
integrals.
Topher
|
| Thanks, Jim. Jim also asked where this problem came up.
T(d) is the number of ways to decompose a polynomial of degree d
into an expression tree by recursively applying the form:
i
P (x) = P (x) + x R (x),
d i-1 d-i
where (as you'd expect)
d
P (x) = c + c x + ... + c x ,
d 0 1 d
i-1
Q (x) = c + c x + ... + c x , and
i-1 0 1 i-1
d-i
R (x) = c + c x + ... + c x .
d-i i i+1 d
|