整数多倍長演算クラスを作ってみる
いや、そんな立派なものではないです。
とある問題で200の階乗を計算しろというものがあり、Number型の精度を飛び出してしまうということで、作ってみたのが以下。
package { import flash.display.Sprite; public class apre extends Sprite { public function apre() { var a:int2 = new int2("1"); for(var i:int=2 ; i<=200 ; i++) a.mul(i); trace(a.getnum()); } } } class int2{ private var num:String; // 本当は s の中身が全部数字であることの確認が必要 public function int2(s:String="0"){ num = s; } public function getnum():String{ return num; } public function add(num2:String):void{ var n:int; var ans:String = ""; var tmp:int; var digup:Boolean = false; // num の方が長い if(num.length>num2.length){ n = num.length; for(var i:int=0 ; i=n-num2.length ; i++){ num2 = "0"+num2; } } // num2 の方が長い else{ n = num2.length; for(i=0 ; i=n-num.length ; i++){ num = "0" + num; } } for(i=n-1 ; i>=0 ; i--){ tmp = (int)(num.charAt(i)) + (int)(num2.charAt(i)); if(digup) tmp++; digup=false; // 10より大きい場合は繰り上げ if(tmp >= 10){ tmp -= 10; digup = true; } ans = tmp.toString()+ans; } if(digup) ans = "1"+ans; num = ans; } public function mul(t:int):void{ var tmpnum:String = num; for(var i:int=1 ; i<t ; i++) add(tmpnum); } }
クラスを作るのはほとんど初めてなのでいろいろ許してください・・・。
で、これをもうちょっとマシにしたのが以下。
package { import flash.display.Sprite; public class apre extends Sprite { public function apre() { var a:int2 = new int2("1"); for(var i:int=2 ; i<=200 ; i++) a.mul(i); trace(a.getnum()); } } } class int2{ private const DIG:int = 9; private var num:String; // コンストラクタ:本当は s の中身が全部数字であることの確認が必要 public function int2(s:String="0"){num = s;} public function getnum():String{return num;} public function addint(num2int:int):void{addstr(num2int.toString());} public function addstr(num2:String):void{ // 桁数保存用 var numlen:int = num.length; var num2len:int = num2.length; var n:int; // return用変数 (最後にnumに代入) var ans:String = ""; // 足し算用 var tmp:uint; var tmpstr:String; var tmpstrlen:int; // 繰り上げ用 var digup:Boolean = false; // num の方が長い -> num2が numと同じ桁数になるように0を加える if(numlen > num2len){ n = numlen; for(var i:int=0 ; i<numlen - num2len ; i++){ num2 = "0"+num2; } } // num2 の方が長い -> numが num2と同じ桁数になるように0を加える else{ n = num2len; for(i=0 ; i<num2len - numlen ; i++){ num = "0" + num; } } for(i=n-1 ; i>=0 ; i=i-DIG){ // DIG の桁ずつ足し算 if(i-DIG>=0) tmp = (uint)(num.slice(i-DIG+1,i+1)) + (uint)(num2.slice(i-DIG+1,i+1)); else tmp = (uint)(num.slice(0,i+1)) + (uint)(num2.slice(0,i+1)); if(digup) tmp += 1; digup = false; tmpstr = tmp.toString(); tmpstrlen = tmpstr.length; // 10^DIG より大きい場合は繰り上げ if(tmpstrlen == DIG+1 && tmpstr.charAt(0)=="1"){ digup = true; tmpstr = tmpstr.slice(1,tmpstrlen); } // 桁が足りない場合は0を埋める else if(tmpstr.length!=DIG){ for(var k:int=1 ; k<=DIG-tmpstrlen ; k++){ tmpstr = "0"+tmpstr; } } ans = tmpstr + ans; } if(digup) ans = "1"+ans; // 先頭に0があった場合消去する while(ans.charAt(0)=="0"){ ans = ans.slice(1,ans.length); } num = ans; } public function mul(t:int):void{ var tmpnum:String = num; for(var i:int=1 ; i<t ; i++) addstr(tmpnum); } }
1桁ずつの足し算を、intでとれる限界の桁まで増やしてみました(Numberで大きい整数を扱うといろいろと問題が発生したのでやめました)。
一応 DIG で桁数を変えられるようにはしてあります。
それに伴ってaddstrの中はいろいろ面倒な事になりました・・・
それから掛け算は超絶手抜きです。(String)×(String)まで本当はやりたいのですが、ほんと大変になってしまいそうなので。逃げ。
200の階乗は2秒以上2.5秒未満ぐらいの時間で計算できるようになりました。
「なぜActionScriptで?」っていう疑問はなしね!
あ、今気づいたけどコンストラクタの数字かどうかの判定してないや。isNaNでも書いとけばいいのかなー。