Solving polynomials, complex arithmetics and code inlining

Yeah, this is what I’ve been doing in my spare time these last days. Basically, I needed to find all roots of 4th power polynomial and, after quick search, I’ve found great wiki article on new Durand-Kerner method that makes Newton-Raphson look outdated: using only simple arithmetics it simultaneously finds all polynomial roots no matter how wrong your initial guess is. The only problem is that it needs complex numbers.

So, I had to implement complex numbers in some way. Obviously, since AS3 does not support operator overloading, we end up with a bunch of function calls. The problem here is that even these short formulas require quite a lot of them, and you need to keep evaluating that over and over before solution is found, which, as you might guess, is not so CPU-friendly. So I decided to inline them all. To this end, I downloaded and installed apparat by Joa Ebert. This actually went much easier than I expected, the only problem I ran into was that it does not work with current version of scala. Any way, getting your code inlined with this tool is as easy as extending special class. However, checking my resulting SWF with AS3 decompiler, I have found that apparat does not remove neither its own nor my custom classes which were inlined and so are no longer used anywhere. Since this is not something Joa would be willing to fix, I turned to GPP, a tool pre-processing macros in source rather than post-processing bytecode in SWF. As a result of these adventures, I have these two FlashDevelop projects for grabs in svn (view).

The other problem with complex numbers implementation in AS3 is readability. Endless lines of similar function calls separated by semicolons look pretty much like some old code in asm, if you ever seen one. In order to somewhat ease the pain, I decided to at least make it possible to chain function calls into formulas. This normally implies another performance penalty because you need to create new temporary variables in the process; however, it can be avoided by pooling those variables. This implementation can be found (and forked :) at wonderfl.

Well, that’s it for today, I’m off to enjoy my sunday.

1 Response to “Solving polynomials, complex arithmetics and code inlining”



  1. 1 Meet qtrack « ¿noʎ ǝɹɐ ʍoɥ 'ʎǝɥ Trackback on December 29, 2010 at 21:06

Ask a Question

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Old stuff

December 2010
M T W T F S S
« Nov   Mar »
 12345
6789101112
13141516171819
20212223242526
2728293031  

Oh, btw…


%d bloggers like this: