If all you have is a data encoding method....

[mangosteen]

Realization: Polynomials and indexed arrays of integers are, if not isomorphic, then *very* useful for understanding each other.

I'm kind of embarrassed that it took my brain this long to explicitly put that one together. Which is to say, I always knew it, but I didn't previously realize the cool stuff that falls out of it, like taking the derivative to move the index into the coefficient, etc.

This is (apparently) what I do on vacation. Happy New Year!

Comments

[miss-chance.livejournal.com]

I <3 geekery!


Happy New Year!

[sweh.livejournal.com]

It becomes even more obvious when you think of a polynomial as a sigma equation
f(x)=sum(i=0->inf) a{sub i}x^i
ie
a0 + a1x + a2x^2 + a3x^3 + ...
which leads to a natural a[] as the representation

For full representation you need an infinitely sized array, or a lazy evaluation language :-)

[vatine]

And if you have your arrays in the right (and by right, I actually mean "wrong") order, stored from highest to lowest index, computing the polynmomial for a given X turns into a simple reduce (or, if your language supports reducing from the tail-end, you can have the array in the right order).

To wit:
lambda(x, polynom): reduce lambda(sum, new-poly-factor): x*sum+new-poly-factor over polynom

[sweh.livejournal.com]

Trying to think how I'd do this in Orwell (language I last used in 1987). Hmm...

> f x a:as = f x a:as 0
> f x a:as i = a*x^i * f x as (i+1) if as <> []
>           = a*x^i otherwise

The "a:as" expression means "single element a followed by a (potentially empty) list of more a's"

[perspicuity.livejournal.com]

i've got a book in "computational algebra" some years ago. fascinating stuff. polynomial goodness.

then consider polynomials and bases and the fun you can do there.

and gah. i can reference a book if you want. i'll have to find it later.

one can write a lot of neat perl/python for such things.

#

[vatine]

There's always the joys of "iterated Newton-Raphson fractals". Essentially, take any polynomial, find its roots, then for a section of the complex plane, colour all points based on (a) what root is reached and (b) how long it takes to get there.

If you start from the roots, you can simply construct the polynomial and can skip the root-finding. It's also possible to do the root-finding mixed in with the point-colouring (find what root a given point tends to, see if that is a root previously found, if not add the root to the set of roots).

[jicama]

Ah yes, Linear Algebra.