多倍長乗算サンプル

テキストフィールド二つに数字を入れてenter押すと掛け算実行

forked:0
favorite:5
lines:190
license : MIT License
modified : 2009-07-28 10:13:34

Embed: Tweet

package {  
     import flash.display.Sprite;  
	 import flash.events.KeyboardEvent;
	 import flash.text.TextField;
	 import flash.ui.Keyboard;
	 import flash.utils.getTimer;
	 
	 // テキストフィールド二つに数字を入れてenter押すと掛け算実行
     public class Test extends Sprite {  
		 private var tf1:TextField = new TextField();
		 private var tf2:TextField = new TextField();
		 private var tf3:TextField = new TextField();
         public function Test() {
			tf1.autoSize = tf2.autoSize = tf3.autoSize = "left";
			tf1.border = tf2.border = true;
			tf1.text = tf2.text = "111111111";
			tf1.type = tf2.type = "input";
			tf1.restrict = tf2.restrict = "0-9";
			tf2.y = tf1.height + 5;
			
			tf3.y = tf2.y + tf2.height + 10;
			
			addChild( tf1 );
			addChild( tf2 );
			addChild( tf3 );
			 
			stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown, true);
		 }
		 private function onKeyDown(e:KeyboardEvent):void {
			e.preventDefault();
			if ( e.keyCode == Keyboard.ENTER && tf1.length && tf2.length ) {
				var time:Number = getTimer();
				var result:String = bigMultiply(tf1.text, tf2.text);
				tf3.text = "結果(" + tf1.length +"桁×" + tf2.length + "桁, " +(getTimer() - time) + " ミリ秒):" + result;
			}
		 }
		 private function bigMultiply(num1:String, num2:String):String {
			const KETA:int = 4;
			var divideNum:Number = Math.pow(10, KETA);
			var zeroString:String = "";
			for (var i:int = 0; i < KETA; i++ ) { zeroString += "0"; }
			var maxLength:int = (num1.length > num2.length)?num1.length:num2.length;
			var maxKeta:int = Math.ceil(maxLength / KETA);
			var N:int = 1 + Math.ceil(Math.LOG2E * Math.log(maxKeta));
			var num:int = 1 << N;
			var halfNum:int = num >> 1;
			var temp:Number = 9999;
			var fftUtil:FFTutil = new FFTutil(N);
			
			var zeroString2:String = zeroString;
			for ( i = 1; i < N; i++ ) {
				zeroString2 = zeroString2 + zeroString2;
			}
			num1 = (zeroString2 + num1).substr( -halfNum * KETA, halfNum * KETA);
			num2 = (zeroString2 + num2).substr( -halfNum * KETA, halfNum * KETA);
				
			var v1:Vector.<Number> = new Vector.<Number>(2 * num);
			for ( i = 0; i < halfNum; i++ ) {
				v1[2 * i] = Number(num1.substr(4 * i, 4));
				v1[2 * i + 1] = Number(num2.substr(4 * i, 4));
			}
			fftUtil.data = v1;
			v1 = fftUtil.FFT();
			 
			var m:Vector.<Number> = new Vector.<Number>();
			m.push( v1[0] * v1[1] );
			m.push( 0 );
			for ( i = 1; i <= halfNum; i++ ) {
				m.push( 0.5 * (v1[2 * i] * v1[2 * i + 1] + v1[ 2 * (num-i)] * v1[2 * (num-i) + 1]) );
				m.push( 0.25 * (-v1[2*i]*v1[2*i]+v1[2*i+1]*v1[2*i+1]+v1[2*(num-i)]*v1[2*(num-i)]-v1[2*(num-i)+1]*v1[2*(num-i)+1]) );
			}
			for ( ; i < num; i++ ) {
				m.push( m[2 * (num - i)] );
				m.push( -m[2 * (num - i) + 1] );
			}
			
			fftUtil.data = m;
			var v:Vector.<Number> = fftUtil.FFT(true, num);
			var result:String = "";
			var kuriagari:Number = 0;
			var zeroIndex:int = 0;
			for ( i = 0; i < num; i++ ) {
				if ( int(0.5 + v[2 * i]) ) break;
			}
			zeroIndex = i;
            for (i = num - 2; i >= zeroIndex; i--) {
				var number:Number = int(0.5 + v[2 * i]);
				number += kuriagari;
				kuriagari = int(number / divideNum);
				if ( i == zeroIndex && kuriagari == 0 ) {
					result = int((zeroString + number.toString()).substr( -KETA, KETA)) +  result;
				} else {
					result = (zeroString + number.toString()).substr( -KETA, KETA) +  result;
				}
            }
			if ( kuriagari > 0 ) {
				result = kuriagari.toString() + result;
			}
			return( result );
         }  
    }  
}
	// sparkにあげたことがある、微妙に遅いFFT計算Util
	class FFTutil 
	{
		private var cos:Vector.<Number>;
		private var sin:Vector.<Number>;
		private var _N:int = -1;
		private var _M:int;
		private var _rM:Number;
		private var _data:Vector.<Number>;
		public function FFTutil(N:int) 
		{
			this.N = N;
		}
		/**
		 * 2のN乗分のデータを処理する
		 * （任意の数字に対応してください）
		 */
		public function set N(value:int):void
		{
			_N = value;
			_M = 1 << _N;
			_init();
		}
		/**
		 * 計算につかう三角関数を先に計算しておく
		 * （現在はメモリとりすぎ。こんなにいらない）
		 */
		private function _init():void
		{
			cos = new Vector.<Number>(_M);
			sin = new Vector.<Number>(_M);
			for ( var i:int = 0; i < _M; i++ ) {
				cos[i] = Math.cos( 2 * Math.PI * i / _M );
				sin[i] = Math.sin( 2 * Math.PI * i / _M );
			}
		}
		/**
		 * 変換元の配列
		 * [データ1の実数部, データ1の虚数部, データ2の実数部, データ2の虚数部, ...]
		 */
		public function set data(value:Vector.<Number>):void {
			_data = value;
		}
		/**
		 * 離散フーリエ変換を高速に実行する
		 * @return 変換後の配列
		 */
		public function FFT(isReverse:Boolean = false, divNum:Number = 1.0):Vector.<Number> {
			var ret:Vector.<Number> = new Vector.<Number>(2 * _M);
			if( isReverse ){
				DFT_iter_r( 0, 0, _M, ret );
			} else {
				DFT_iter( 0, 0, _M, ret );
			}
			if ( divNum != 1.0 ) {
				divNum = 1 / divNum;
				var M2:int = 2 * _M;
				for ( var i:int = 0; i < M2; i++ ) {
					ret[i] *= divNum;
				}
			}
			return ret;
		}
		/**
		 * バタフライ計算(CooleyとTukeyのアルゴリズム)
		 * 
		 * @param	a	元のデータの頭のインデックス
		 * @param	top	結果データの頭のインデックス
		 * @param	length	小分けにしたベクトルの長さ
		 * @param	ret	結果データ
		 */
		private function DFT_iter( a:Number, top:Number, length:Number, ret:Vector.<Number> ):void {
			if ( length > 2 ) {
				var halfLength:int = 0.5 * length;
				var b:Number = 0.5 * _M / length;
				DFT_iter( a, top, halfLength, ret );
				DFT_iter( a + 4 * b, top+length, halfLength, ret );
				for ( var i:int = 0; i < length; i += 2 ) {
					var k:int = i * b;
					var cos:Number = cos[k];
					var sin:Number = sin[k];
					var rnum:Number = cos * ret[top + i + length] - sin * ret[top + i + length + 1];
					var inum:Number = sin * ret[top + i + length] + cos * ret[top + i + length + 1];
					ret[top + i + length] = ret[top + i] - rnum;
					ret[top + i + length + 1] = ret[top + i + 1] - inum;
					ret[top + i] += rnum;
					ret[top + i + 1] += inum;
				}
			} else {
				var aM:int = a + _M;
				ret[top] = _data[a] + _data[aM];
				ret[top + 1] = _data[a + 1] + _data[aM + 1];
				ret[top + 2] = _data[a] - _data[aM];
				ret[top + 3] = _data[a + 1] - _data[aM + 1];
			}
		}
		/**
		 * バタフライ計算(CooleyとTukeyのアルゴリズム)
		 * 逆変換バージョン。sinが-sinになっただけ。
		 * 
		 * @param	a	元のデータの頭のインデックス
		 * @param	top	結果データの頭のインデックス
		 * @param	length	小分けにしたベクトルの長さ
		 * @param	ret	結果データ
		 */
		private function DFT_iter_r( a:int, top:int, length:int, ret:Vector.<Number> ):void {
			if ( length > 2 ) {
				var halfLength:int = 0.5 * length;
				var b:Number = 0.5 * _M / length;
				DFT_iter_r( a, top, halfLength, ret );
				DFT_iter_r( a + 4 * b, top+length, halfLength, ret );
				for ( var i:int = 0; i < length; i += 2 ) {
					var k:int = i * b;
					var cos:Number = cos[k];
					var sin:Number = - sin[k];
					var rnum:Number = cos * ret[top + i + length] - sin * ret[top + i + length + 1];
					var inum:Number = sin * ret[top + i + length] + cos * ret[top + i + length + 1];
					ret[top + i + length] = ret[top + i] - rnum;
					ret[top + i + length + 1] = ret[top + i + 1] - inum;
					ret[top + i] += rnum;
					ret[top + i + 1] += inum;
				}
			} else {
				var aM:int = a + _M;
				ret[top] = _data[a] + _data[aM];
				ret[top + 1] = _data[a + 1] + _data[aM + 1];
				ret[top + 2] = _data[a] - _data[aM];
				ret[top + 3] = _data[a + 1] - _data[aM + 1];
			}
		}
	}

Code Fullscreen

Preview Fullscreen