flash on 2009-12-9

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/xhmH
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // エラトステネスの改良
    // doEratosthenesは各要素=奇数
    // doEratosthenes2は各bit=奇数
    // doEratosthenes3は各bit=30で割った余りが1,7,11,13,17,19,23,29のもの
    // 結論から言うと 2 > 1 > 3
    // 他の言語だと3が一番速くなりそうなんだけどなあ
    // 3が遅くなるのは配列要素呼び出し等がループのなかに入ってしまうからかなあ
    public class Test extends Sprite {
        private var _tf : TextField;
  
        public function Test() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            
//            tr(doEratosthenes(10000000).length);
            tr(doEratosthenes2(10000000).length);
//            tr(doEratosthenes3(10000000).length); 
//            tr(doEratosthenes3(100)); 
            
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // 8bitに30ぶん格納
        private function doEratosthenes3(n : int) : Array
        {
            var nn : uint = ((n / 30) >>> 2) + 1;
            var ar : Vector.<uint> = new Vector.<uint>(nn + 1);
            var i : uint, j : uint;
            for(i = 0;i <= nn;i++)ar[i] = 0xffffffff;
            ar[0] ^= 1;
            
            var a : Vector.<uint> = Vector.<uint>([1, 7, 11, 13, 17, 19, 23, 29]);
            
            var ia : Vector.<uint> = new Vector.<uint>(30);
            for(i = 0;i < 30;i++)ia[i] = 0;
            for(i = 0;i < a.length;i++)ia[a[i]] = i + 1;
            
            var mods : Array = [];
            // m*mを基準に2mずつ進めたときの、この格納方式に有効なインデックスを取り出す
            for(i = 0;i < a.length;i++){
                var mod : Array = [];
                var aa30 : uint = (a[i] * a[i]) % 30;
                for(j = 2;j < 32;j+=2){
                    var mmmmm : uint = a[i] * j + aa30;
                    if(ia[mmmmm % 30]){
                        mod.push([mmmmm, ia[mmmmm%30] - 1]);
                    }
                }
                tr(i, mod);
                mods.push(mod);
            }
            
            var sq : uint = uint(Math.sqrt(n) / 30 + 1) << 3;
            for(var p : uint = 0;p <= sq;p++){
                if(ar[p >>> 5] & (1 << (p & 31))){
                    var m : uint = uint((p >>> 3) * 30) + a[p & 7];
                    var m30 : uint = m * 30;
                    var mmm : Array = mods[ia[m%30]-1];
//                    tr(p, m, mmm);
                    for(var mm : uint = m*m;mm <= n;mm += m30){
                        for each(var mmmm : Array in mmm){
                            var ind : uint = uint((mm+mmmm[0])/30)<<3 | mmmm[1];
                            if(ind >>> 5 < nn){
                                ar[ind >>> 5] &= ~(1 << (ind & 31));
                            }
                        }
                    }
                }
            }
            
            var ret : Array = [2, 3, 5];
            // p = i << 5 | j
            for(i = 0;i < nn;i++){
                for(j = 0;j <= 31;j++){
                    if(ar[i] & (1 << j))ret.push((i << 2 | j >>> 3) * 30 + a[j & 7]);
                }
            }
            return ret;
        }
        
        private function doEratosthenes2(n : int) : Array
        {
            var nn : uint = ((n / 2 - 1) >>> 5) + 1;
            var ar : Vector.<uint> = new Vector.<uint>(nn);
            var i : uint, j : uint;
            for(i = 0;i < nn - 1;i++)ar[i] = 0xffffffff;
            ar[nn - 1] = (1 << ((n / 2 - 1) & 31)) - 1;
            
            var sq : uint = (Math.sqrt(n) - 3) >>> 1;
            for(var p : uint = 0;p <= sq;p++){
                if(ar[p >>> 5] & (1 << (p & 31))){
                    var m : uint = (p << 1) + 3;
                    var m2 : uint = m << 1;
                    for(var mm : uint = m * m;mm <= n;mm += m2){
                        var ind : uint = (mm - 3) >>> 1;
                        ar[ind >>> 5] &= ~(1 << (ind & 31));
                    }
                }
            }
            
            var ret : Array = [2];
            for(i = 0;i < nn;i++){
                for(j = 0;j <= 31;j++){
                    if(ar[i] & (1 << j))ret.push((((i << 5) | j) << 1) + 3);
                }
            }
            return ret;
        }
        
        private static function doEratosthenes(n : int) : Array
        {
            var ar : Vector.<uint> = new Vector.<uint>(n / 2 - 1);
            var i : int;
            for(i = 0;i < ar.length;i++)ar[i] = 1;
            
            var sq : int = (Math.sqrt(n) - 3) >> 1;
            for(var p : int = 0;p <= sq;p++){
                if(ar[p] == 1){
                    var m : int = (p << 1) + 3;
                    var m2 : int = m << 1;
                    for(var mm : int = m * m;mm <= n;mm += m2){
                        ar[(mm - 3) >> 1] = 0;
                    }
                }
            }
            var ret : Array = [2];
            for(i = 0;i < ar.length;i++){
                if(ar[i] == 1)ret.push((i << 1) + 3);
            }
            return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
        }
    }
}