源碼： 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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
