多倍長乗算サンプル
テキストフィールド二つに数字を入れてenter押すと掛け算実行
/**
* Copyright keno42 ( http://wonderfl.net/user/keno42 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/rgfF
*/
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];
}
}
}