源碼: http://files.cnblogs.com/flash3d/alc.rar
前幾天研究了Bresenham直線掃描算法。頗受其一些優(yōu)化策略的啟發(fā),故想將其推廣至二次三次已經(jīng)n次曲線的批量計算。
進過一番假設(shè)推導(dǎo)證明,具體思路和過程就不和大家講了,估計我也講不清楚,大家也聽不明白。我給大家舉個例子就明白了。
假設(shè)我們要求y=x^3這個曲線,x為(1,2,3,4,5...)時候y的值,這個也是我們研究的目的。
那么,我們先手動算幾個值看看。
X???? Y
1???? 1
2???? 8
3???? 27
4???? 64
5???? 125
6???? 216
7???? 343
恩,粗看確實毫無規(guī)律,然后,我們試著給他們的y求相鄰的差,得出的差再求相鄰的差。。。
X???? Y
1???? 1
??????????? 7
2???? 8?????????? 12
??????????? 19?????????? 6
3???? 27???????? 18
??????????? 37?????????? 6
4???? 64???????? 24
??????????? 61?????????? 6
5???? 125?????? 30
??????????? 91?????????? 6
6???? 216?????? 36
??????????? 127
7???? 343
最后發(fā)現(xiàn)。。不斷求差結(jié)果竟都是6!
這個6就是y=x^3這個方程不斷對x求導(dǎo)的最后得到的常數(shù)。比如這里y=x^3,那么3*2*1就是6。如果x前面還有個數(shù),比如y=2*x^3,那么最后的常數(shù)就是2*3*2*1。以此類推。
這個規(guī)律的發(fā)現(xiàn),可以讓計算結(jié)果很大程度上被重用。
利用這個規(guī)律,如何計算呢?因為這個算法的計算依賴上一次的計算,所以,我們只能先算1的結(jié)果再算2的結(jié)果。。依次計算。那么我們來演繹下如果計算y=x^3。
x為1時,我們沒有任何數(shù)據(jù)可以利用,那么老老實實計算吧。。結(jié)果為1,這個結(jié)果先存著。
x為2時,我們雖然有x為1時結(jié)果為1這個數(shù)字可以依賴,貌似沒有起到任何作用。。那也老老實實計算,結(jié)果是8。這個結(jié)果存著。而且,我們也可以把前兩次結(jié)果的差算出來,8和1的差是7。這個7也存著。
x為3的時候,我們也試圖使用前兩次的數(shù)據(jù),結(jié)果失敗。那么我們也老老實實計算,結(jié)果是27。這個結(jié)果存著,并且,我們也把他和前面的那個結(jié)果求差,27-8結(jié)果是19。這個19要存著。而且,我們還能把19和7求差,結(jié)果是12。存著。
x為4的時候,我們試圖使用前面的數(shù)據(jù)。這次我們得逞了!參照上面那張表,那個6我們是能計算出來的,12我們也有,那么通過這兩個數(shù)據(jù),相加,可以得到18。然后的得出來的18和我們已經(jīng)保存著的19相加,就能得到37。這37是何物?這37就是x為3和x為4兩個結(jié)果的差。我們可以直接把x為3的結(jié)果27加上37,得到x為4的結(jié)果64.
x為5的結(jié)果也類似,可以用以上的方法不斷累加得到。。
觀察發(fā)現(xiàn),前面3個數(shù)需要老老實實算,除去前三個,就能通過累加獲得結(jié)果。數(shù)學(xué)證明,最高n次方程,前面n個需要老老實實算。
這里我們再整理下內(nèi)存的開銷。觀察整個流程,可以發(fā)現(xiàn),用過一次的數(shù)第二次都用不到了,其存貯位置可以被新產(chǎn)生的數(shù)據(jù)利用。
這里,除去那個6,總共就用到三個存儲器。3就是整個函數(shù)的最高次。通過證明得到,最高n次的方程,用到存儲器n個。
以下是as3上的算法。
var res:Array=new Array(); // 存放表一行的數(shù)組
function cul(n:int):void
{
var thex:int; // x的值
var a:int; // 中間變量
var b:int; // 同上
var k:int=1; // 不斷求導(dǎo)最后的常數(shù)
// 前面n個數(shù)需要手動老老實實算
for (thex=1;thex<=n;thex++)
{
res[thex-1]=Math.pow(thex,n)+Math.pow(thex,n-1);
trace(thex,",",res[thex-1]);
// 新存入的數(shù)產(chǎn)生的一系列新的值代替了老的一些用不到的值的位置
for (a=thex-1;a>=1;a--)
{
res[a-1]=res[a]-res[a-1];
}
}
// 求出不斷求導(dǎo)后常數(shù)的值
for (a=n;a>=2;a--)
{
k*=a;
}
// 計算100000次
for (b=0;b<100000;b++)
{
// 每次計算,將k累加到最末位上,最末位是那張表除去k之外最外層的數(shù),加上k之后,其值下移了一位
res[0]+=k;
// 不斷將值往里面累加,里面的值在表中都下移了一位,最后使表中最左邊的值下移一位,也就是我們要求的結(jié)果
for (a=1;a<n;a++)
{
res[a]+=res[a-1];
}
trace(n+b+1,",",res[n-1]);
}
}
不過悲劇的是,經(jīng)過測試發(fā)現(xiàn),該算法比用pow函數(shù)老老實實算還要慢上一大截。
這結(jié)果讓我很不爽!
于是我將該算法寫成了alchemy進行調(diào)用,才勉強能趕上as3默認的pow函數(shù)。不知道pow函數(shù)是用什么樣的算法,很想知道呀!
?
http://bbs.blueidea.com/thread-2934831-1-1.html
這個是alchemy使用的方法。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
