纳金网

标题: [as3基础应用]Alchemy的使用和多项式批量计算的优化 [打印本页]

作者: . 时间: 2013-3-20 09:12
标题: [as3基础应用]Alchemy的使用和多项式批量计算的优化
http://boycy.webs.com/cul.swf 动画地址：http://boycy.webs.com/cul.swf
前几天研究了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使用的方法。
我自己的源文件：
http://boycy.webs.com/alc.rar 【来源：互联网】
更多精彩教程，尽在web3D纳金网http://www.narkii.com/college/ 动画地址：http://boycy.webs.com/cul.swf
前几天研究了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使用的方法。
我自己的源文件：
http://boycy.webs.com/alc.rar 【来源：互联网】
更多精彩教程，尽在web3D纳金网http://www.narkii.com/college/

欢迎光临纳金网 (http://c-www.narkii.com/club/)