FLASH: improved square root

[Damian Morton]

Heres a way to speed up your square root calculations:


The algorithm given in the MM support site is an iterative refinement

algorithm. What this means is that it starts with an estimate of the square

root and refines it over a number of steps. This is the algorithm given on

the MM Site:


Label "SQRT"

	Set Variable: "i" = "0"

	Set Variable: "x" = "1"    	<----- this is the estimated square root that

we start with

	Loop While (i < 20) 		<----- note the fixed number of refinement steps

taken

		Set Variable: "x" = x-((x*x-value)/(2*x))

		Set Variable: "i" = i+1

	End Loop

	Set Variable: "sqrt" = x


In most cases, if you are using a square root, you will be doing it

repeatedly. That is, you will probably be measuring distances between

objects on every frame, or somesuch. Because of this, you can exploit what

is called frame-to-frame coherence to speed up your square roots. What this

means is that by storing the square root calculated at one place in one

frame, you have a pretty good estimate of what the square root will be at

that place in the next frame. Having a good estimate reduces the number of

times you have to refine your estimate, thus speeding things up. In the MM

example, the estimate is fixed at 1, but we can do better than that. Heres

the revised algorithm:


Label "SQRT"

	Comment: SQRT (value, estimate) -> (sqrt)

	Set Variable: "sqrt" = estimate

	Set Variable: "err" = (sqrt*sqrt - value)/(2*sqrt)

	Loop While (err*err > 0.01)

		Set Variable: "sqrt" = sqrt - err

		Set Variable: "err" = (sqrt*sqrt - value)/(2*sqrt)

	End Loop

	Set Variable: "sqrt" = sqrt - err


Ive found that for many applications involving simple physics, you can

reduce the number of iterations from 10 or 20 down to 2 or 3 by using this

technique.


Even if you cant supply a good estimate, this algorithm should be faster and

possibly more accurate than the MM supplied one becasue it stops when the

error term gets low enough, rather than continuing on blindly for N

iterations.


Its a shame that MM didnt expose a decent maths library in Flash 4, and

instead forces us to use prehistoric optimisation technques to get our code

to function right. Im also curious how they made actionscript so damned

slow. I can only hope that Flash 5 will speed things up and expose a

plethora of fairly standard math and string functions, not to mention access

to all of the properties of an object.



flasher is generously supported by...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 Get the last 100 messages from the flasher list NOW

    http://www.chinwag.com/flasher/last100.shtml


 Flash books http://www.chinwag.com/flasher/books.shtml

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

To unsubscribe or change your list settings go to

http://www.chinwag.com/flasher or email

helpchinwag [dot] com