Exp function

Monkey Forums/Monkey Programming/Exp function

gregbug

(Posted 2011) [#1]

Hi guys
i need to implement an optimized exp function...

now my exp function is like this:

const E:Float = 2.78281828

function exp:Float(power:Float)
   return Pow(E, power)
end function

some better (optimized) code ?

no need for extreme accurancy...

thanks.

Warpy

(Posted 2011) [#2]

for starters, e = 2.71828183...

It's very odd that there's no built-in exp function.

Import mojo

Function cfexp#(z#)
	Return 1+2*z/((2-z)+(z*z/6)/(z+(z*z/60)/(1+(z*z/140)/(1+(z*z/252)/(1+z*z/396)))))
End 

Function taylorexp#(z#)
	Return 1 + z/1 + z*z/2 + z*z*z/6 + z*z*z*z/24 + z*z*z*z*z/120 + z*z*z*z*z*z/720 + z*z*z*z*z*z*z/5040 + z*z*z*z*z*z*z*z/40320 + z*z*z*z*z*z*z*z*z/362880 + z*z*z*z*z*z*z*z*z*z/3628800
End

Const e#=2.71828183
Function powexp#(z#)
	Return Pow(e,z)
End 

Function Main()
	New App
	Local c,start,finish
	
	Print "Starting"
	start=Millisecs()
	err=0
	For c=1 To 10000000
		cfexp(Rnd(20))
	Next
	finish=Millisecs()
	Print (finish-start)+"ms: continued fraction"

	Print "Starting"
	start=Millisecs()
	err=0
	For c=1 To 10000000
		taylorexp(Rnd(20))
	Next
	finish=Millisecs()
	Print (finish-start)+"ms: taylor series approximation"

	Print "Starting"
	start=Millisecs()
	err=0
	For c=1 To 10000000
		powexp(Rnd(20))
	Next
	finish=Millisecs()
	Print (finish-start)+"ms: pow function"
End

So it looks like the function taylorexp, based on the Taylor approximation, is fastest.

FlameDuck

(Posted 2011) [#3]

Also, the Taylor series gives you a greater control of what kind of heuristic you want (in terms of speed versus accuracy).

gregbug

(Posted 2011) [#4]

thanks guys!

i hope that this optimizations will be effective also on Android,
ios and wp7 devices.

thanks again!

xlsior

(Posted 2011) [#5]

Interesting -- in HTML5, I get very different results with these depending on the browser I use.

Chrome 11:

Starting
1442ms: continued fraction
Starting
1432ms: taylor series approximation
Starting
1879ms: pow function

Internet Explorer 9:

Starting
5157ms: continued fraction
Starting
8891ms: taylor series approximation
Starting
3727ms: pow function

So... Taylor approximation is the fastest choice in Chrome for me, but in IE it takes much longer than the other two.

muddy_shoes

(Posted 2011) [#6]

Performance of this sort of thing will always vary widely across the platforms. The code above has a few problems though. The continued fraction implementation seems to have errors, but also the timing code includes the cost of the randomise function, which will vary across platforms.

It's not really possible to do micro-optimisation at the Monkey level that is applicable to all targets, but I've made a few tweaks that help on most targets to some extent. It's pretty academic as unless you're doing thousands of these operations in your game loop it's likely to be completely unnoticeable.

Import mojo

Function cfexp#(z#)
	Return 1+2*z/((2-z)+(z*z/6)/(z+(z*z/60)/(1+(z*z/140)/(1+(z*z/252)/(1+z*z/396)))))
End 

Function taylorexp#(z#)
	Return 1 + z/1 + z*z/2 + z*z*z/6 + z*z*z*z/24 + z*z*z*z*z/120 + z*z*z*z*z*z/720 + z*z*z*z*z*z*z/5040 + z*z*z*z*z*z*z*z/40320 + z*z*z*z*z*z*z*z*z/362880 + z*z*z*z*z*z*z*z*z*z/3628800
End

Const oneover6:Float = 1.0/6.0
Const oneover24:Float = 1.0/24.0
Const oneover60:Float = 1.0/60.0
Const oneover120:Float = 1.0/120.0
Const oneover140:Float = 1.0/140.0
Const oneover252:Float = 1.0/252.0
Const oneover396:Float = 1.0/396.0
Const oneover720:Float = 1.0/720.0
Const oneover5040:Float = 1.0/5040.0
Const oneover40320:Float = 1.0/40320
Const oneover362880:Float = 1.0/362880
Const oneover3628800:Float = 1.0/3628800

Function cfexp2#(z#)
    Local z2:Float = z*z
    Local ret:Float = ( 1+(z2*oneover252/(1+z2*oneover396)))
    ret = 1+(z2*oneover140/ret)
    ret = 1+(z2*oneover60/ret)
    ret = 2-z+(z2*oneover6/ret)
    ret = 1 + (2*z)/ret

	Return ret
End 

Function taylorexp2#(z#)
	Local z2:Float = z*z
	Local z4:Float = z2*z2
	Local z6:Float = z4*z2
	Local z8:Float = z4*z4
    Local z10:Float = z8*z2
    
	Return 1 + z + z2*0.5 + z2*z*oneover6 + z4*oneover24 + z4*z*oneover120 + z6*oneover720 + z6*z*oneover5040 + z8*oneover40320 + z8*z*oneover362880 + z10*oneover3628800
End

Const e#=2.71828183
Function powexp#(z#)
	Return Pow(e,z)
End 

Function Main()
	New App
	Local c,start,finish
    Local testCount:Int = 1000000
	Local testVals:Float[] = New Float[testCount]
    For c=0 Until testCount
		testVals[c] = Rnd()*10.0
	Next
	
#rem
    For c=0 Until testCount
        Print "Val: " + testVals[c]
		Print taylorexp(testVals[c])
        Print taylorexp2(testVals[c])
        Print cfexp(testVals[c])
        Print cfexp2(testVals[c])
		Print powexp(testVals[c])
	Next
#end
    
	Print "Starting"
	start=Millisecs()
	
    For c=0 Until testCount
        cfexp(testVals[c])
	Next
	finish=Millisecs()
	Print "continued fraction orig(ms): " + (finish-start)

    start=Millisecs()
	
    For c=0 Until testCount
        cfexp2(testVals[c])
	Next
	finish=Millisecs()
	Print "continued fraction opt(ms): " + (finish-start)

	start=Millisecs()
	
    For c=0 Until testCount
		taylorexp(testVals[c])
	Next
	finish=Millisecs()
	Print "taylor series orig(ms): " + (finish-start)

    start=Millisecs()
	
    For c=0 Until testCount
		taylorexp2(testVals[c])
	Next
	finish=Millisecs()
	Print "taylor series opt(ms): " + (finish-start)

    start=Millisecs()
	
    For c=0 Until testCount
		powexp(testVals[c])
	Next
	finish=Millisecs()
	Print "pow function(ms): " + (finish-start)
End

Example timings with 1,000,000 values

Chrome:

Starting
continued fraction orig(ms): 336
continued fraction opt(ms): 81
taylor series orig(ms): 103
taylor series opt(ms): 45
pow function(ms): 167

IE9:

Starting
continued fraction orig(ms): 440
continued fraction opt(ms): 230
taylor series orig(ms): 1013
taylor series opt(ms): 284
pow function(ms): 364

Android:

09-04 13:50:06.127: INFO/[Monkey](2761): Starting
09-04 13:50:07.947: INFO/[Monkey](2761): continued fraction orig(ms): 1818
09-04 13:50:09.157: INFO/[Monkey](2761): continued fraction opt(ms): 1207
09-04 13:50:12.487: INFO/[Monkey](2761): taylor series orig(ms): 3330
09-04 13:50:14.097: INFO/[Monkey](2761): taylor series opt(ms): 1609
09-04 13:50:32.327: INFO/[Monkey](2761): pow function(ms): 18231

Edit:

After playing around a bit, I've noticed that Chrome seems to have some pronounced start-up costs that handicap whichever function is timed first. The other targets I've tried don't show this to any great extent, but it's probably also worth looping over the entire test set two or three times if you want to avoid this problem. Example second loop timings for Chrome:

Starting
continued fraction orig(ms): 129
continued fraction opt(ms): 79
taylor series orig(ms): 101
taylor series opt(ms): 46
pow function(ms): 167

Floyd

(Posted 2011) [#7]

Avoid this unless numerical accuracy is utterly irrelevant.

The Taylor series up to z^10 is acceptable only for very small values of z. But it gets worse as z grows and is already down to one significant digit at z = 7:

1096.633   exp(7) "exact" float value
 988.592   Taylor up to z^10, note error is about 10%.

And it is completely ridiculous at z = -7, unless you take care to use 1/taylorexp(7). Then the error is back to being only 10%.

marksibly

(Posted 2011) [#8]

Hi,

Exp will be added to the next version.

Sorry for the oversight, it's just one of those things I never use myself so keeps slipping my mind...

gregbug

(Posted 2011) [#9]

oh thanks mark!