源碼： http://files.cnblogs.com/flash3d/alc.rar
前幾天研究了Bresenham直線掃描算法。頗受其一些優化策略的啟發，故想將其推廣至二次三次已經n次曲線的批量計算。
進過一番假設推導證明，具體思路和過程就不和大家講了，估計我也講不清楚，大家也聽不明白。我給大家舉個例子就明白了。
假設我們要求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
恩，粗看確實毫無規律，然后，我們試著給他們的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
最后發現。。不斷求差結果竟都是6！
這個6就是y=x^3這個方程不斷對x求導的最后得到的常數。比如這里y=x^3，那么3*2*1就是6。如果x前面還有個數，比如y=2*x^3，那么最后的常數就是2*3*2*1。以此類推。
這個規律的發現，可以讓計算結果很大程度上被重用。
利用這個規律，如何計算呢？因為這個算法的計算依賴上一次的計算，所以，我們只能先算1的結果再算2的結果。。依次計算。那么我們來演繹下如果計算y=x^3。
x為1時，我們沒有任何數據可以利用，那么老老實實計算吧。。結果為1，這個結果先存著。
x為2時，我們雖然有x為1時結果為1這個數字可以依賴，貌似沒有起到任何作用。。那也老老實實計算，結果是8。這個結果存著。而且，我們也可以把前兩次結果的差算出來，8和1的差是7。這個7也存著。
x為3的時候，我們也試圖使用前兩次的數據，結果失敗。那么我們也老老實實計算，結果是27。這個結果存著，并且，我們也把他和前面的那個結果求差，27-8結果是19。這個19要存著。而且，我們還能把19和7求差，結果是12。存著。
x為4的時候，我們試圖使用前面的數據。這次我們得逞了！參照上面那張表，那個6我們是能計算出來的，12我們也有，那么通過這兩個數據，相加，可以得到18。然后的得出來的18和我們已經保存著的19相加，就能得到37。這37是何物？這37就是x為3和x為4兩個結果的差。我們可以直接把x為3的結果27加上37，得到x為4的結果64.
x為5的結果也類似，可以用以上的方法不斷累加得到。。
觀察發現，前面3個數需要老老實實算，除去前三個，就能通過累加獲得結果。數學證明，最高n次方程，前面n個需要老老實實算。
這里我們再整理下內存的開銷。觀察整個流程，可以發現，用過一次的數第二次都用不到了，其存貯位置可以被新產生的數據利用。
這里，除去那個6，總共就用到三個存儲器。3就是整個函數的最高次。通過證明得到，最高n次的方程，用到存儲器n個。
以下是as3上的算法。
var
res:Array=new Array();
//
存放表一行的數組
function
cul(n:int):void
{
var
thex:int;
//
x的值
var
a:int;
//
中間變量
var
b:int;
//
同上
var
k:int=1;
//
不斷求導最后的常數
//
前面n個數需要手動老老實實算
for
(thex=1;thex<=n;thex++)
{
res[thex-1]=Math.pow(thex,n)+Math.pow(thex,n-1);
trace(thex,",",res[thex-1]);
//
新存入的數產生的一系列新的值代替了老的一些用不到的值的位置
for
(a=thex-1;a>=1;a--)
{
res[a-1]=res[a]-res[a-1];
}
}
//
求出不斷求導后常數的值
for
(a=n;a>=2;a--)
{
k*=a;
}
//
計算100000次
for
(b=0;b<100000;b++)
{
//
每次計算，將k累加到最末位上，最末位是那張表除去k之外最外層的數，加上k之后，其值下移了一位
res[0]+=k;
//
不斷將值往里面累加，里面的值在表中都下移了一位，最后使表中最左邊的值下移一位，也就是我們要求的結果
for
(a=1;a<n;a++)
{
res[a]+=res[a-1];
}
trace(n+b+1,",",res[n-1]);
}
}
不過悲劇的是，經過測試發現，該算法比用pow函數老老實實算還要慢上一大截。
這結果讓我很不爽！
于是我將該算法寫成了alchemy進行調用，才勉強能趕上as3默認的pow函數。不知道pow函數是用什么樣的算法，很想知道呀！
?
http://bbs.blueidea.com/thread-2934831-1-1.html
這個是alchemy使用的方法。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
