Page 2 of 2
Re: Squirrel Virtual Libraries
Posted: 02 Apr 2009 18:08
by Bilbo
Well, that would be many times slower. Maybe 20 or more times. And the most important (for me) function exp(x) that you have posted work only for x being positive integer, which unfortunately useless for sigmoidal transfer function, as x gets there usually "somewhere between -1 and 1, occasionally higher or lower".
Well, if it won't be exported, I'll have to calculate exp(x) somehow else. Possibly using some precomputed tables, storing exp(x) for x from -10 to 10 in increments of 1.
Since e^(x+y)=e^x*e^y, you can lookup for nearest e^x in the table, then get remainder y, multiply it by 10, lookup again and divide the result by e^10. With reasonably large table (~200 entries) you can compute exp(x) with relatively good precision with just 4 or 5 lookups. But it will be still slower than just handing the task to the FPU :)
Re: Squirrel Virtual Libraries
Posted: 02 Apr 2009 21:12
by Xander
Surely it would make a lot more sense to write the "heavy" functions (like exp) in AI code - that way they only tie up the system for the standard AI time slot and never affect the user experience.
I do appreciate where you're coming from Bilbo - any mature intelligence is going to need to do a lot of sums but if your sums are so demanding they affect the users play experience the first thing they're going to do is make a stupid topic on the forums bitching and then they're going to turn your AI off when they're told that's the problem.
Re: Squirrel Virtual Libraries
Posted: 02 Apr 2009 21:15
by Yexo
Xander wrote:Surely it would make a lot more sense to write the "heavy" functions (like exp) in AI code - that way they only tie up the system for the standard AI time slot and never affect the user experience.
No, that doesn't make sense, since AI code is a lot slower than c++ code.
I do appreciate where you're coming from Bilbo - any mature intelligence is going to need to do a lot of sums but if your sums are so demanding they affect the users play experience the first thing they're going to do is make a stupid topic on the forums bitching and then they're going to turn your AI off when they're told that's the problem.
I have no idea what point you're trying to make here.
Re: Squirrel Virtual Libraries
Posted: 02 Apr 2009 22:02
by cirdan
Bilbo wrote:Well, if it won't be exported, I'll have to calculate exp(x) somehow else. Possibly using some precomputed tables, storing exp(x) for x from -10 to 10 in increments of 1.
If you want an efficient formula to compute exp(x), you should use its power series expansion, which is
Code: Select all
exp(x) = 1 + x + x^2/2 + x^3/6 + x^4/24 + ... + x^n/n! + ...
It converges extremely fast, particularly for values of x close to 0 (due to the mean value theorem and the fact that n! grows even faster than exp(n)). If you are interested in values of x for which |x| < 1, then the Taylor polynomial of order 4
Code: Select all
exp(x) ~ 1 + x + x^2/2 + x^3/6 + x^4/24
gives you an error of less than e/120; using order 5, the error is less than e/720, and so on (order n has error bound by e/(n+1)!). If your values were |x| < 1/2, errors would be considerably smaller. On the other hand, convergence when |x| > 1 can be slower at first; from what you say, this may not be a problem for you, but otherwise you can use e^{2x} = (e^x)^2. I'd suggest halving x until it is less than, say, 1/4, then using an appropriate polynomial, then squaring the result as many times as you halved it in the first place.
Of course, you should not use those polynomials directly, but instead use Ruffini's rule for efficient polynomial evaluation:
Code: Select all
1 + x + x^2/2 + x^3/6 + x^4/24 = 1 + x ( 1 + x ( 1/2 + x ( 1/6 + 1/24 x ) ) )
This gives you the result with n additions and n multiplications--no powers involved. This is true for any polynomial of degree n, and it is provably the most efficient way to evaluate any polynomial.
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 10:02
by AndersI
Instead of using the mathematically correct infinite series expansion, you should decide your input range and acceptable error and compute 'optimized polynomials' for only that domain. For example, an acceptable sine() can be achieved with only three terms in the expansion (4 multiplications, 3 additions).
There's a bit (theory) about that (and other things) here:
http://www.research.scea.com/research/p ... _GDC02.pdf - and in many other places too.
Then there's the old, proven, CORDIC concept but that's maybe not so well suited for OTTD-AI Sqirrel as it results in a larger number of simple operations (is the AI allotted actual time, a number of program lines, or a number of 'Squirrel primitive operations' in each 'time slice'?)
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 11:05
by cirdan
AndersI wrote:Instead of using the mathematically correct infinite series expansion, you should decide your input range and acceptable error and compute 'optimized polynomials' for only that domain. For example, an acceptable sine() can be achieved with only three terms in the expansion (4 multiplications, 3 additions).
Err, that's exactly what I suggested, although perhaps I did not make it clear enough. In fact, I even gave some error estimations for the Taylor polynomials of orders 4 and 5. I mentioned the power series just because the previous suggestion had been to compute exp(x) as pow(e,x), and because all those 'optimised polynomials' are simply truncated versions of the infinite series.
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 11:28
by AndersI
No, as far as I can see, you are talking about truncated Taylor series. By calculating optimal coefficients for the terms you include, you can get a better approximation with fewer terms, especially if you know you will be using a limited input range. Those coefficients will not be integers, as in your examples.
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 11:36
by cirdan
Perhaps I'm just being thick, but 1/2, 1/6, 1/24... are not integers in my book...
And the Taylor polynomial method can't be that wrong if
the MPFR library uses
it.
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 12:06
by AndersI
Sorry, I don't have any good links. The best I could find quickly is this discussion on Stackoverflow,
http://stackoverflow.com/questions/3450 ... tions-work, I'm mostly thinking of Chebyshev polynomials, as Jason S (about at the middle of that page) is talking about. Some of his examples:
Code: Select all
[...sin and cos ...]
Range = -pi/2 to +pi/2, degree 5 (3 terms)
* Taylor: max error around 4.5e-3, f(x) = x-x3/6+x5/120
* Chebyshev: max error around 7e-5, f(x) = 0.9996949x-0.1656700x3+0.0075134x5
Range = -pi/2 to +pi/2, degree 7 (4 terms)
* Taylor: max error around 1.5e-4, f(x) = x-x3/6+x5/120-x7/5040
* Chebyshev: max error around 6e-7, f(x) = 0.99999660x-0.16664824x3+0.00830629x5-0.00018363x7
Range = -pi/4 to +pi/4, degree 3 (2 terms)
* Taylor: max error around 2.5e-3, f(x) = x-x3/6
* Chebyshev: max error around 1.5e-4, f(x) = 0.999x-0.1603x3
where you can see that by using Chebyshev (Minimax) polynomials, you can drop one term (or even two!) in the expansion and still have better accuracy than the Taylor expansion. I don't know if the same goes for the Exp() function, though - the most important thing for simplifying that is to reduce the range, I think.
[...some more searching...]
Ah, here's a textbook link that actually works:
http://books.google.se/books?id=-rCodwZ ... t&resnum=2
It seems the Exp() function is well suited for Chebyshev approximation too.
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 12:17
by gaynorg
Maybe we could throw these into a library as a stopgap until they include the ones from squirrel. Any takers ?
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 17:45
by Bilbo
Perhaps it would be easier to create a patch that will add these functions instead of trying to create an approximative library...
Re: Squirrel Virtual Libraries
Posted: 03 Apr 2009 18:53
by Zutty
Bilbo wrote:Perhaps it would be easier to create a patch that will add these functions instead of trying to create an approximative library...
Since 0.7.0 has only just gone out you're unlikely to get a patch in a release any time soon EVEN IF the OpenTTD devs like it. An AI that requires a patch isn't going to have very many followers and kinda defeats the point of NoAI.
Re: Squirrel Virtual Libraries
Posted: 20 Jul 2009 10:13
by id10terror
Bilbo, i'd just use the 'heavy' library for the moment, then when you have your ai to a point where it starts outperforming others but drags the performance of ottd down you will be in a good position to 'ask' for the math lib to be included. Even if you don't succeed with you request, people like a good ai and will ask why its so slow and then you'd be able to tell them why and further your case for inclusion.
Re: Squirrel Virtual Libraries
Posted: 20 Jul 2009 16:20
by Dustin
Zutty wrote:Bilbo wrote:Perhaps it would be easier to create a patch that will add these functions instead of trying to create an approximative library...
Since 0.7.0 has only just gone out you're unlikely to get a patch in a release any time soon EVEN IF the OpenTTD devs like it.
An AI that requires a patch isn't going to have very many followers and kinda defeats the point of NoAI.
I don't know about that. Being able to write a really cool NN AI, even if you are working off a private binary might be enough by itself. I know all the AI writers would probably want to check it out. And if we all though it was cool then we would recommend people get the patch and so on. In other words, if you write a killer app on a private patch, then the chances of talking the devs into taking the patch into main goes up.
I have toyed with the idea of farming off my pathfinding stuff to some sort of cloud computing. That would required a totally custom version of the game. But my pathfinder would be able to solve all the paths at once! (mmmm.)
In other news, I can promise that anyone can write an AI that will slow the game down noticeably right now. I have written some buggy loops that did just that. So having your AI impact the game isn't a really good reason to forbid any library calls. If your AI makes the game sluggish, no one will play with it.
-D