著作権フリーのC++高速汎用多倍長演算を作るｽﾚ
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2007/11/24(土) 09:53:51ネット上でここが詳しい
http://homepage1.nifty.com/~umetani/ims/Algebra.html
0002デフォルトの名無しさん
2007/11/24(土) 09:55:520003デフォルトの名無しさん
2007/11/24(土) 10:02:0300041
2007/11/24(土) 10:07:130005デフォルトの名無しさん
2007/11/24(土) 10:15:38単発依頼スレを自分だけ特別に立てて良いと思った理由を述べろ。
00061
2007/11/24(土) 11:03:2300071
2007/11/24(土) 11:27:300008デフォルトの名無しさん
2007/11/24(土) 12:02:03できんやつはスレ立てる．
若干反例があるが，これは普遍の真理．
00091
2007/11/24(土) 12:02:480010デフォルトの名無しさん
2007/11/24(土) 12:08:16その著作権は誰のものになるんだ？
0011デフォルトの名無しさん
2007/11/24(土) 12:08:32ちなみに、それはもう存在してて、ググれば見つかるよ。
商用利用もOK。GPLじゃない。
00121
2007/11/24(土) 12:15:50Ｒ［Ｘ］/（Ｘ＾ｎ-1） → R[G] （同型のフーリエ変換）
という写像を作って
多項式環の乗法が、 右側だと簡単で計算出来て、
それを同型で戻すという寸法だ
00131
2007/11/24(土) 12:28:08では、高速離散フーリエ変換のライブラリでフリーで高速にうごくやつを組み込んで作ろう
どこかにいいやつありますか?
0014デフォルトの名無しさん
2007/11/24(土) 12:34:1000151
2007/11/24(土) 12:49:28それより厳密な整数演算に使える高速フーリエ変換ってあるんですか?
誤差が出るやつでは駄目です 整数演算のみでやるやつです
0016デフォルトの名無しさん
2007/11/24(土) 16:00:2900171
2007/11/24(土) 17:43:360018デフォルトの名無しさん
2007/11/24(土) 18:30:37とりあえず
基幹部分はC
インターフェイスはPython
でいいんだよな
0019デフォルトの名無しさん
2007/11/24(土) 18:34:5200201
2007/11/24(土) 19:29:10数値を多項式と見立てて、多項式の乗算、即ち、離散系の畳み込みをフーリエ空間で行い、
それを実空間に戻して、数値の乗算をしたことにするのである。
今、4096個の一次元データに4096個データの一次元フィルタを掛けるとすれば、
実空間では、4096*4096 約1678万回の乗算が必要となるが、
DFTでは、畳み込みだけでは、0.4万回で済む。前後に3回のDFTが必要となるが、
この分は、FFTで行えば8万回程度なので、約8.4万回で済むことになる。約200倍のスピードとなる。
http://www.nextftp.com/swlabo/m0_pctech/hp_ultraprecision/up_815_1.htm
00211
2007/11/24(土) 19:34:583/4 Ｎ*Ｎにできるアルゴリズムがあるが断然違うよな
0022デフォルトの名無しさん
2007/11/24(土) 19:37:550023デフォルトの名無しさん
2007/11/24(土) 19:48:590024デフォルトの名無しさん
2007/11/24(土) 22:23:19多倍長整数の加減乗除を実装するスレなのかと思った。
0025デフォルトの名無しさん
2007/11/24(土) 22:32:200026デフォルトの名無しさん
2007/11/24(土) 23:11:52じゃあ低速でいいからとっとと作れよ、簡単なんだろ。
高速化するのはその後でいいよ。
最低限、自分の発言に責任を持て。
0027デフォルトの名無しさん
2007/11/25(日) 00:32:341がDQNあつかいされてるな。
フーリエ変換って、多倍長乗算やCTとか、
周波数とか関係のない、意外なとこで利用されてるから面白いよね。
0028デフォルトの名無しさん
2007/11/25(日) 02:31:310029デフォルトの名無しさん
2007/11/25(日) 14:53:532ちゃんねるに書き込んだものってひろゆきが権利持つんじゃないだろうか。
00301
2007/11/25(日) 14:54:26可換環Ｒに対して、次を満たす要素ｅが存在するとする
・ ｅは1の原始ｎ+1乗根 （すなわち、ｅのｎ+1乗は1かつ、ｎ乗以下では1ではない）
・ ｋがｎ以下ならば、 Σ( i, 0, n) E(k) ^ i =0 ただしE(k) ＝ｅ＾ｋ
このとき、Ｇ＝｛1，Ｅ（1），・・・，Ｅ（ｎ）｝は群をなす
ＧからＲへの写像全体をＣ（ｅ）と置くと、次のようにしてR上の有限次元ベクトル空間になる
内積を、(f,g)=Σ( i, 0, n) f( Ｅ（j）) g( Ｅ（-j）)で定義すると、｛λi｝が正規直交基底を与える （ただしλi( Ｅ（j） )＝Ｅ（jj））
さらにＣ（ｅ）は次で与える積でR代数になる (f*g)( Ｅ（k）) = Σ( i, 0, n) f( Ｅ（k-i）) g( Ｅ（i）)
R[X]の要素fに対して、C(e)の要素Ｆ（ｆ）を次のように定義する Ｆ（ｆ）( Ｅ（k）) = Σ( i, 0, n) f( Ｅ（i）) Ｅ（ki）
この対応はR代数として準同型写像を与える
これから導かれる 同型 R[X]/(X^(n+1) - 1) ≡ C(e) を離散フーリエ変換という
00311
2007/11/25(日) 15:00:24Ｒ［Ｘ］/（Ｘ^4-1） からC(2)への離散フーリエ変換が定義できる
0032デフォルトの名無しさん
2007/11/25(日) 18:34:53だからまずフーリエ変換を使わないプログラムを作るべきでは？
00331
2007/11/25(日) 18:54:30しかしフーリエで適用できるようにデータ構造は決めないと駄目なんです
00341
2007/11/25(日) 19:06:03可換環Ｒに対して、次を満たす要素ｅが存在するとする
・ ｅは1の原始ｎ乗根
・ ｋがｎ未満ならば、 Σ( i, 0, n-1) E(k) ^ i =0 ただしE(k) ＝ｅ＾ｋ
このときR[X]/(x^n - 1)の自己同型写像F
f → Σ( i, 0, n-1) f( E(i) ) X^i をフーリエ変換という
逆写像は、f → (1/n) Σ( i, 0, n-1) f( E(n-i) ) X^i で与えられる
このとき、畳み込み積 (f*g)( Ｅ（k）) = Σ( i, 0, n-1) f( Ｅ（k-i）) g( Ｅ（i）)に対して F(fg) = F(f) * F(g)が成り立つ
X^s * X^t = X^s (s=t) or 0 (それ以外)を満たす この性質から畳み込み積の計算は簡単にできる
00351
2007/11/25(日) 19:09:5400361
2007/11/25(日) 19:55:32最大位数が大きいほど、計算できる桁数が上がります しかし、pが大きすぎると計算時間がかかります
どうやって最大位数の大きい元をみつけたらいいんでしょうか?
00371
2007/11/25(日) 20:00:5000381
2007/11/25(日) 20:06:43#include <iostream>
using namespace std;
main(){
int n,k,N,cnt;
for(N=(1<<16)-1;N>2;N--){
for(n=2;n*n<N;n++){k=N/n; if(k*n==N)break;}
if(n*n<=N)continue;
for(n=2;n<=N/2;n++){
k=n;
for(cnt=1;k!=1;cnt++){k*=n;if(k>N)for(;k>N;k-=N);}
if(cnt+1==N){cout<<"素数 "<<N<<"に対し要素"<<n<<"の位数は"<<cnt<<endl;break;}
}}}
00391
2007/11/25(日) 20:16:0700401
2007/11/25(日) 21:55:11p=2^16 + 1 とe=3とおく
f(X) = Σa_i ・X^i (a_i < 2^16) を多倍長整数とします
これをフーリエ変換すると、 Σf( e^i ) ・X^i になります
g(X)も多倍長整数とするとフーリエ変換はΣg( e^i ) ・X^i になります
fとgの畳み込み積は、 Σf( e^i ) g( e^i ) ・X^i となり
これをフーリエ逆変換すると、Σf( e^(p-1-i) ) g( e^((p-1-i)) ) ・X^i になります
この係数のうち、2^16であるものは桁上がりを処理して結果が出ます
00411
2007/11/25(日) 21:59:03f(1)g(1) 、 f(3)g(3)、 f(3^2)g(3^2)、・・・をmod pの範囲で求めれば良いだけです
0042デフォルトの名無しさん
2007/11/25(日) 22:14:09もし本当にそうなら47氏逮捕のときにひろゆきも逮捕されてるはず
00431
2007/11/25(日) 22:18:37Z/(p)での演算から 1/3 ＝21846
0044デフォルトの名無しさん
2007/11/25(日) 22:21:16馬鹿？
金子がWinnyの実装を2ちゃんに書き込んだかよ？
00451
2007/11/26(月) 14:47:41それは、2進数に対応させるんだ 例えば1024*1024のサイズのフーリエ変換ならば
0〜1023の2進数ごとに一定の手続きをすることで計算が完了する
00461
2007/11/26(月) 14:50:1600471
2007/11/26(月) 15:00:41サイズは2Nの、(Xi) = (ω^ij) (xi)というフーリエ変換は、
(X2i) = (ω^2ij) (xi+xN+i)
(X2i+1) = (ω^2ij+j) (xi+xN+iω^N)
に変換できる
これを繰り返したとき、Xの添え字、ωの指数、xの足し算の仕方を
000011101などの2進数から決定できる
0048デフォルトの名無しさん
2007/11/26(月) 15:03:1800491
2007/11/26(月) 16:36:20単純な総当たり掛け算より多いような気がする 特典は桁上がりの死よりが少ないだけでは?
00501
2007/11/26(月) 16:45:06Karatsuba法だとN^1.59だね やはり高速フーリエ変換が最速か
しかし、より詳細に求めると、 2N* log N + N だから、場合によってはN^1.59のほうが速いかもしれないね
0051デフォルトの名無しさん
2007/11/26(月) 17:01:0200521
2007/11/26(月) 17:37:49使い方分からないし、整数演算に使えるか分からないので自作してみるよ・・・
あと、自作使用した理由が、多倍長ライブラリのコンパイルが出来なかった為だったのだ
C++言語のみで、他のライブラリに依存しないで単体で動くと導入が簡単なのだ
00531
2007/11/26(月) 17:50:11たとえば
Lint x;
x=2;
for(int i; i<1000; i++)x=x*x;
x.printf();
としたとき xのサイズが自動で拡張されるようにしたいのですが
0054デフォルトの名無しさん
2007/11/26(月) 17:54:49それで性能上困ることがあれば、
自分でmalloc/free呼んだり、OSのメモリ確保APIを直接呼んだり、
それをメモリプールしてみたり。
00551
2007/11/26(月) 18:03:24vectorは速度的に速いと思うので、内部でvector使うことにします 自分で領域を動的に管理するとバグでやすいですし
00561
2007/11/26(月) 18:25:05a = x + y という演算子を定義するとき、x+y演算と、代入演算を分離するとしない場合より代入分
計算コストがかかると思うのですが、tasu(&a, &x, &y)という関数と同じように定義することは出来ないですか?
これなら計算結果を直接格納できるのですが
0057デフォルトの名無しさん
2007/11/26(月) 18:41:310058デフォルトの名無しさん
2007/11/26(月) 18:41:4400591
2007/11/26(月) 19:00:39サンクス でも使い方分からなかったよ
なんか代入にかかる計算程度をケチっても
意味がある計算には変化なさそうなので知ってるやり方でやってみる
わざと、代入が多くなるような計算すれば違いが出るとはおもうけど
00601
2007/11/26(月) 20:21:12符号と数値を保存してあるとして、足し算が負になるか正になるかで計算を分類しなくていけない
00611
2007/11/26(月) 20:35:530062デフォルトの名無しさん
2007/11/26(月) 20:36:0400631
2007/11/26(月) 22:01:58http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/5338.txt
0064デフォルトの名無しさん
2007/11/26(月) 22:10:52コメントとインデントつけてくれるとうれしいな
00651
2007/11/26(月) 22:19:29int fugou; //正負
vector< unsigned short int > a; //一区切りは2バイトのunsigned整数
Lint& operator=(Lint x); // Lint の代入
Lint& operator=(int x); //整数の代入
int operator>(Lint& x);
int operator<(Lint& x); //絶対値の比較
Lint operator+(Lint& x) //足し算
絶対値の大きい方を先頭にして、残りの数値を引いたり足したりする
00661
2007/11/26(月) 22:24:20x / y = x * (1/y) だから1/yを求められればよい
すると、符号の他に小数(の位置)を記録する必要がある
ニュートン法で1/yを計算するのが良いらしいけど
有効桁数までもとめ続けた方が良いのだろうか
0067デフォルトの名無しさん
2007/11/26(月) 22:28:460068デフォルトの名無しさん
2007/11/26(月) 22:32:57あとFFTを理解するの面倒でスレを読んでないんだけど多倍長整数みたいなもんだよね？
Lint& operator=(int x)を見る限り4294967296までしか行けそうにないけど、俺が馬鹿なだけ？
0069デフォルトの名無しさん
2007/11/26(月) 22:37:30歌ってるのか？
0070デフォルトの名無しさん
2007/11/26(月) 22:40:55どうでもいいからやんわりと書こうとしただけで洒落ようとかこれっぽっちも思ってなかったのにorz
0071デフォルトの名無しさん
2007/11/26(月) 23:30:130072デフォルトの名無しさん
2007/11/26(月) 23:33:550073デフォルトの名無しさん
2007/11/26(月) 23:38:38FFTWとかFFTEより速いもんが出来上がる訳もないわな。
ついでにその整数環FFT使った多倍長乗算は普通のFFTの物より遅いでFA出てた筈。
プロセッサの設計・製造からやるんなら話が違うかもしれんがね。
0074デフォルトの名無しさん
2007/11/26(月) 23:48:06しーっ、リバーシスレのようになるから触っちゃダメ。
00751
2007/11/26(月) 23:49:350076デフォルトの名無しさん
2007/11/26(月) 23:52:070077デフォルトの名無しさん
2007/11/26(月) 23:54:49ところでoperator +=は？
そっち作った後、それを使って残りを定義するのが普通。
More effective C++ 22項
Lint operator +(Lint const& x, Lint const& y)
{
return Lint(x) += y;
}
あと、operator<はreturn x > *this;で十分なはず。
さらに!(*this < x)でoperator >=、!(*this > x)でoperator <=も実装できる。
ついでにoperator ==とoperator !=も作ってしまえ。
単項operator +と-も今すぐできるはずだ。
欲を言えばswapが欲しい。
0078デフォルトの名無しさん
2007/11/26(月) 23:55:36やっぱりリバーシスレと同じ匂い感じた人がいたかｗ
00791
2007/11/27(火) 00:29:23あと逆数の計算方法の書いてあるサイトをのせます
1/n を求めるには
http://www.nextftp.com/swlabo/m0_pctech/hp_ultraprecision/up_820.htm
http://yowaken.dip.jp/tdiary/20070428.html
00801
2007/11/27(火) 01:13:47引数1つにしてくれというエラーが出ます
Lint operator +(Lint const& x, Lint const& y) { return Lint(x) += y; }
0081デフォルトの名無しさん
2007/11/27(火) 01:29:47応援するよ
00821
2007/11/27(火) 01:29:58+は他で使えます +を定義してから +=を定義する方向で行こうと思います
0083デフォルトの名無しさん
2007/11/27(火) 01:38:29うまくまとめてるサイトってないものかね？
http://www.nitoyon.com/vc/tips/multi_precision.htm
こんな感じのサンプル上がってるとこ見て、見よう見まねで実装してるんだけど・・・
00841
2007/11/27(火) 01:52:2800851
2007/11/27(火) 02:19:09http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/5341.txt
00861
2007/11/27(火) 02:34:46opPostInc() {
int i,s=a.size();
for(i=0;i<s;i++){
if(a[i]==65535)a[i]=0;
else {a[i]++;break;}}
if(i==s){a.resize(s+1);a[s]=1;}}
00871
2007/11/27(火) 02:40:1900881
2007/11/27(火) 03:07:26Lint operator*(Lint & x){
Lint *p,*q;
if(*this > x){p=&x; q=this;} else {p=this; q=&x;}
int s,t,u;
s=(*p).a.size(); t=(*q).a.size(); u=s*t;
Lint y; y.a.resize(u+1,0);
if(sign + x.sign==0) y.sign=-1;
int i,n; unsigned w,k=0;
for(n=0; n < u; n++){
w=k; k=0;
for(i=0; i<=min(n,s); i++){
w += (*p).a[i] * (*q).a[n-i];
k+=(w>>16); w&=LIMIT;}
y.a[n]=w;}
if(k>0)y.a[u]=k; else y.a.resize(u,0);
return y;}
0089デフォルトの名無しさん
2007/11/27(火) 03:34:38ここを
a[i]==999999999
にすれば？
00901
2007/11/27(火) 03:53:38インクリメントの部分ですか? それはコードの中身ではなくて初めの宣言が違っていました
opPostInc() という名前はD言語用のインクリメントの宣言でした
2^16進数を10進表示にするにはどうしたらいいんだろう? 10で割ってその余りを出力していけばいいけど10で割るのが難しい
0091デフォルトの名無しさん
2007/11/27(火) 03:58:0500921
2007/11/27(火) 03:59:44小数点を導入して、値を1以下になるようにシフトさせてから10倍していきます
整数になった部分が最上位の10進表示になります それを0にして繰り返します
00931
2007/11/27(火) 05:44:19cout<< (x&65535)<<" "<<(x%65536);
この正解は10のはずなんですけど値が違います なぜでしょうか
00941
2007/11/27(火) 05:47:35int xx=4259850;
でした
0096デフォルトの名無しさん
2007/11/27(火) 07:36:290097デフォルトの名無しさん
2007/11/27(火) 13:33:2010000進の掛け算と足し算でできるのでは？
00981
2007/11/27(火) 16:00:47>>97 詳細を教えて下さい やっぱり割り算はいると思うのですが
xを表示するなら x%10を出力して、x=x/10として繰り返すという方法です
0099デフォルトの名無しさん
2007/11/27(火) 16:57:552進10進変換が10進多倍長の掛け算と足し算でできるということです。
0100デフォルトの名無しさん
2007/11/27(火) 17:00:06そのopeartor +は非メンバ関数。
swapはそれだと意味がない。代入より効率よく実装できる可能性があるからみんな定義する。
例えばstd::vectorなら、交換は内部のポインタを取り替えるだけで済む。
（代入ならメモリのコピーをしないといけない）
そしてswapという名前のメンバ関数にするのがお約束。
void swap(Lint& x) {
a.swap(x.a);
std::swap(sign, a.sign); //<algorithm>
}
そしてグローバルにもswapを定義しておく。
void swap(Lint& x, Lint& y) {
x.swap(y);
}
単項operator+と-はこういうメンバ関数でいい。
Lint opreotar +() const {
return *this;
}
Lint opreotar -() const {
Lint x = *this;
x.sign = -1;
return x;
}
っていうかコピーコンストラクタLint(Lint const& x)作れ。対称性からLint(int x)も欲しい。
>>98
こういう整数を十進法として出力するにはそれくらいしかないと思う。
0101デフォルトの名無しさん
2007/11/27(火) 17:14:170102デフォルトの名無しさん
2007/11/27(火) 17:27:11インクリメントはとりあえず*this + 1でいいよ。
Lint& operator ++() {
return *this += 1;
}
Lint operator ++(int) {
Lint t = *this;
return ++t;
} //あるいはreturn ++Lint(*this);とすれば1行にまとめられる。
とまあ、C++の演算子多重定義は面倒くさいので、
こんな余計なことに頭を使わないためにも、Boost.Operators推奨。
http://www.kmonos.net/alang/boost/classes/operators.html
boost::operators<Lint>とboost::operators<Lint, int>を継承し、
そこのsampleに載っているのと同じ演算子多重定義関数だけを実装すれば、残りは全て揃う。
ただし引数取るものはconst Lint&版とint版の2つを実装すること。
0103デフォルトの名無しさん
2007/11/27(火) 17:38:320104デフォルトの名無しさん
2007/11/27(火) 17:53:21今はとりあえず動く、使えるようすることに注力してほしい。
0105デフォルトの名無しさん
2007/11/27(火) 18:20:02<と==を定義して残りの> != <= >=をboostに任せるってやっているけど
これは問題だと思うね。
論理的には正しいが下手をすると処理時間が倍以上かかってしまいそう。
0106デフォルトの名無しさん
2007/11/27(火) 20:53:280107デフォルトの名無しさん
2007/11/27(火) 20:59:25>>77にあるようにオペランドの左右を入れ替えたり、結果を!で論理反転するだけ。
コンパイル時の最適化で消えたり、残ってもせいぜい数命令もあるかどうか。
だから無視できる範囲内。
それよりも>>85の現在のoperator ==（と!=）がよっぽどまずい。
!( (*this < x) || (*this > x) )と2度も比較演算を行っており、
これこそ処理時間が倍かかる。
0108デフォルトの名無しさん
2007/11/27(火) 21:17:23!( (*this < x ) | ( *this > x ) )これって最適化で、( *this >= x && *this <= x )とかにしてくれるのかな？
まぁ、倍とはいかないけど大きな期待ができるほどじゃないけど・・・
boost前提のライブラリはどうかと思うけど、楽に書き直せる範囲なら
機能実装から先にやっていけばいいと思うな。
比較に処理が2倍かかろうが、どうせ後でプロファイルするんだろうし。
0109デフォルトの名無しさん
2007/11/27(火) 21:26:59うわ、気付かなかった。
そういえばoperator <って符号を見ていないよな。
0110105
2007/11/27(火) 22:07:29素直に考えると(a<b)||(a==b)になると思うが
それだと最悪2倍程度時間がかかるだろう
0111105
2007/11/27(火) 22:11:00勘違いした。
0112デフォルトの名無しさん
2007/11/27(火) 22:18:38どんまいｗ
operator >の一つだけで一応、全部（>= < <= == !=）実装できるよ。
0113105
2007/11/27(火) 23:03:58でもそれだと処理時間が...
自分が作るとしたらまずCompare関数を作り
残りはそれを呼び出すようにするね。
それなら処理時間は遅くならないはず。
0114デフォルトの名無しさん
2007/11/27(火) 23:36:47処理時間は置いといてだから一応ね。
Compare作るくらいなら==作って、そのNOTで!=でいいんじゃないか？
0115デフォルトの名無しさん
2007/11/27(火) 23:44:11流石に==は実装しないと処理時間がかかる(>>107-108)けど、
比較比較の> >= < <=はどれか1つあれば、残りは速度低下なく実装できる(>>77>>107)。
例えば、a < bが定義されていたとして
>>110で挙げられたa <= bは、!(b < a)と定義すればよい。
(a<b)||(a==b)は悪いけど率直というより愚直。
Boost.Operatorsが比較演算に関してoperator <と==だけを要求しているのは
伊達にやっているからじゃないんだよ。
0116105
2007/11/28(水) 00:17:36a==b <=> Compare(a,b)==0
だからCompareを作れば基本的に１つですむということ。
a<bもa==bも実際は内部で同じような処理をするわけだから
同じようなものを2つ作る必要はないでしょう。
0117デフォルトの名無しさん
2007/11/28(水) 00:39:11つい遅くなるっていうほうにだけ反応していた。
0118デフォルトの名無しさん
2007/11/28(水) 00:42:22>>95から出てきてないことだし。
01191
2007/11/28(水) 23:28:41N=2^16 、p=N+1、f(X)= a0 + ・・・ + a(N-1) ・ X^(N-1) に対して、f(1)、f(3)、・・・、f( 3^(N-1) ) mod p を求める
#include <iostream>
#include <vector>
#include <time.h>
#define p 65537
unsigned int mod_p(unsigned int& x){
int y=(x&65535)-(x>>16);
if(y<0)y+=p; return y;}
main(){
int N=1<<13, i,j;
cout<<"初期データ生成中・・・\n";
vector< unsigned int > a, x; a.resize(N); x.resize(N);
for(i=0;i<N;i++)a[i]=((rand()&255)<<8)+(rand()&255);
vector< vector< unsigned int > > e;
for(i=0;i<N;i++)e.resize(N); for(i=0;i<N;i++)e[i].resize(N);
j=1; for(i=0;i<N;i++){ e[0][i]=1; e[i][0]=1; e[1][i]=j; j*=3;}
for(i=1;i<N;i++) for(j=1;j<N;j++) e[i][j] = e[1][(i*j)&(N-1)];
cout<<"計算開始・・・ ";
int cl=clock();
for(i=0;i<N;i++) for(j=0;j<N;j++){
x[i] += a[j]*e[i][j]; x[i]=mod_p(x[i]);}
cl=clock()-cl; cout<<cl<<" m秒\n";}
01201
2007/11/28(水) 23:30:2601211
2007/11/28(水) 23:48:13p=2^16+1に対して、p-2桁の多項式を扱う場合は良いんですが、
実用的なサイズは高々1000桁くらい 少なくとも2^15以上の桁で無いと効果はなさそうです
01221
2007/11/29(木) 00:03:152000に近い素数を見つけて2000進数に変換してから高速フーリエ変換を適用する方法がありますが
前後の基数変換と、フーリエ変換にかかるコストを考えると適用出来る桁は限られそうです
単純に計算した方が速くなるケースが多そうなため
0123デフォルトの名無しさん
2007/11/29(木) 00:09:53for(i=0;i<N;i++)e.resize(N);ってこれをループにする必要ない。
01241
2007/11/29(木) 00:39:15まずは、この計算を高速にするコードを作ることにします うちのパソコンは鈍いので47秒掛かります
高速フーリエ変換が正しく実装出来れば、最大 (2^15*2^15) / (2^16 * 16 * 2 + 2^16) =496倍高速になるはずです
0.1秒以内で処理が終わるはずですが・・・
#include <iostream>
#include <vector>
#include <time.h>
#define rnd() (((rand()&255)<<8)+(rand()&255));
main(){
int N=1<<15, i,j,n;
vector< unsigned int > a, b, c;
a.resize(N); b.resize(N); c.resize(2*N);
for(i=0;i<N;i++){a[i]=rnd();b[i]=rnd();}
unsigned int k=0, x, cl=clock();
for(n=0; n<2*N; n++){ x=k; k=0;
for(i=0; i<N; i++){x += a[i]*b[n-i]; k+=x>>16; x&=65535;}
c[n]=x;}
cl=clock()-cl; cout<<N<<"桁どおしの掛け算の処理時間 "<<(cl+0.0)/1000<<" 秒\n";}
0125デフォルトの名無しさん
2007/11/29(木) 10:37:250126デフォルトの名無しさん
2007/11/29(木) 11:22:230127デフォルトの名無しさん
2007/11/29(木) 19:09:33x += a[i]*b[n-i];
bの大きさはN個で、n = 0 -> 2N. i = 0 -> Nなんだから
n - iのとる範囲は0 -> 2Nで範囲外アクセスじゃないの？
01281
2007/11/29(木) 20:00:43#include <iostream>
#include <vector>
#include <time.h>
#define rnd() (((rand()&255)<<8)+(rand()&255));
main(){
int N=1<<15, i, n;
vector< unsigned int > a, b, c;
a.resize(N); b.resize(N); c.resize(2*N);
for(i=0;i<N;i++){a[i]=rnd();b[i]=rnd();}
unsigned int k=0, x, cl=clock();
for(n=0; n<=2*N-2; n++){ x=k; k=0;
for(i=max(0,n-N+1); i<=min(N-1,n); i++)
{x+=a[i]*b[n-i]; k+=x>>16; x&=65535;}
c[n]=x;}
cl=clock()-cl; cout<<N<<"桁どおしの掛け算の処理時間 "<<(cl+0.0)/1000<<" 秒\n";}
01291
2007/11/29(木) 20:27:16#include<iostream>
#include<gmpxx.h>
#include<time.h>
using namespace std;
mpz_class factorial(int n){
mpz_class x= 1;
for(int i=1; i<=n; i++) x*= i;
return x;}
int main(void){
int c=clock();
mpz_class x = factorial(50000);
c=clock()-c;
// cout << x.get_str() << endl;
cout<< (c+0.0)/1000<<" sec \n";
scanf("%d",&c);}
0130デフォルトの名無しさん
2007/11/29(木) 20:35:30minって関数？もしくはマクロ？
毎回計算させるよりローカルに入れたほうが早くならんかな？
最適化されてもよさそうなところだけど一応。
01311
2007/11/29(木) 20:46:25#include<iostream>に入っている関数だと思われ
なんかGMPは巨大な整数には対応していないのかも・・・ 65536進数の65535桁とかは扱えないかも・・ 計算途中で落ちる
0132デフォルトの名無しさん
2007/11/29(木) 20:49:24たしかmin関数はtemplateでしょ。
ローカルに落としたほうが早いよ。（最適化されないのなら）
01331
2007/11/29(木) 20:55:21円周率などは100億桁とか計算するはずだから
>>132 上のコードは高速化を目標にしてなくて単純なコードと、フーリエ変換のコードの速度を比較する為にうｐしました
0134デフォルトの名無しさん
2007/11/29(木) 21:22:20たぶんメモリを喰いつくすとかの見通しをもとにしてはいるんだろうけど。
0135デフォルトの名無しさん
2007/11/30(金) 12:17:31VC++でもGMPつかえる。
http://fp.gladman.plus.com/computing/gmp4win.htm
>>133
その程度の桁数では大丈夫なはず
ただ、桁数が32bitで表現できる数を超えるとだめらしい。
01361
2007/12/01(土) 05:09:31#include<bitset>
#include<vector>
#include<time.h>
using namespace std;
#define p 65537
#define ee 3
typedef vector< unsigned int > bsu; bsu X, e; vector < bsu > x;
unsigned int mod(unsigned int z){ int y=(z&65535)-(z>>16); return y<0?p+y:y;}
void Fourier_init(){ int k=1; e.resize(p-1); for(int i=0; i<p-1; i++){ e[i]=mod(k); k*=ee; }
X.resize(1<<16); x.resize(16); for(int i=0; i<16; i++) x[i].resize( (1<<(15-i)) );}
bsu& Fourier(bsu& y){
int i, d=1, b, N=32768; bitset<32> a;
for(i=0; i<N; i++) x[0][i]=mod( y[i] );
#define A a.to_ulong()
for(;;){ if(d<15){
b=16-d-1; N=1<<b;
for(i=0; i<N; i++) x[d][i]=mod( x[d-1][i] + e[(A<<b)&65535] * x[d-1][i+N] );
d++;}
else { X[A]=mod( x[14][0] + e[A] * x[14][1] );
X[A+32768]=mod( x[14][0] + e[A+32768] * x[14][1] );
for(d=14; d>=0; d--)if(a[d])a[d]=0; else{a[d]=1;break;}
if(d<1){if(d==0)d=1; else return X;}}}}
main(){ Fourier_init();
bsu a; a.resize(32768);
for(int i=0;i<32768;i++)a[i]=rand();
int cl=clock(); Fourier(a);Fourier(a); cl=clock()-cl;cout<<(cl+0.0)/1000;}
01371
2007/12/01(土) 05:12:27乗法で必要な分のフーリエ変換してみると0.15秒くらいかかりました
最大桁数32768桁の変換にかかる時間
GMPで3万桁の掛け算実行するとエラーになって分からないんですけど
だれか3万桁が出来るコードをあげてもらえませんか?
01381
2007/12/01(土) 05:22:36f(X)= a0 + ・・・ + a(N-1) ・ X^(N-1) 、N=2^16 、p=N+1
に対して、f(1)、f(3)、・・・、f( 3^(N-1) ) mod p を求める事と同じです
3^nはあらかじめ計算しておけば、単純に計算するとN*N程度の乗法が必要ですが
{ 3^n }の周期性から、f(1)、f(3)、・・・、f( 3^(N-1) )を一斉に求めようとすると
N * log2_N程度の乗法で済みます
0139デフォルトの名無しさん
2007/12/01(土) 05:28:37最近のコンパイラやCPUならそっちのほうが早い気がする。
まぁmodも最適化されて%と同じになるかも知れんが。
GMPとかFFTの話に入れなくてこんなことしか言えない・・・
0140デフォルトの名無しさん
2007/12/01(土) 05:31:2501411
2007/12/01(土) 05:56:26ほんとですね %でも同じ速度になりました しかし最適化をうまくやらないコンパイラ用にあった方がいいと思ってます
minGWの最新版で最大の最適化でやりました
01421
2007/12/01(土) 06:00:18しかし、答えが違いました N*Nの方はGMPと答えが一致しています
01431
2007/12/01(土) 06:08:120144デフォルトの名無しさん
2007/12/01(土) 06:14:4101451
2007/12/01(土) 06:36:040146デフォルトの名無しさん
2007/12/01(土) 07:47:010147デフォルトの名無しさん
2007/12/01(土) 11:52:18ここに張られただけのソースを見て、自分で整形までしようとは思わん
0148デフォルトの名無しさん
2007/12/01(土) 20:58:520149デフォルトの名無しさん
2007/12/04(火) 06:34:58>>33
データ構造は結局どうなってるの？構造決まらないとFFTで積でないよ？
多倍長浮動小数だとしたら指数部を記録しないと。
>>45
そんなことは既に考えられている。というより実質ω^iの全配列を作るようなのは無駄。
>>75
加減乗除のうち加減乗は各要素が整数になることは間違いない。
なので浮動小数を使った一般的なFFTを使っても整数化誤差が例えば0.1未満など保証されていれば問題ない。
除算については除算をどう行うか（筆算のようなやり方か、ニュートン法を使うか）、どの程度の誤差を
認めるか（整数演算でキッチリ末尾までか、浮動小数演算として末尾が１違うくらいは認めるか）次第で変わる。
（>>79を書いてるということは浮動小数型？）
>>90,92-94
自分が引用してきたサイトでも見直して配列と多倍長数とがどう対応してるか再考したほうがいい。
ついでにいうと>>98や>>122の発言を見てるとB進数という言葉を勘違いしてる気がする。
>>120-122
N(要素数)が任意でp固定なんてあり得ない。ωは1の原始p乗根のはずなのでFFTに使う要素数は
p-1で固定しなきゃいけない。ということはNがどんなに小さくてもサイズp-1のFFTと同じ時間がかかる。
>>1
ついでなので。リバーシのときと同じく他人の言うことをちゃんと聴くこと。聞くではなく聴くこと。
「まずは動くモノを作る」というのなら再帰使おうが％使おうが、FFTWやGMPより遅かろうが問題ないんだから。
まずはデバグのしやすさ、見易さ優先。アルゴリズムと違うレベルでの速度を求めるのはそれから。
01501
2007/12/04(火) 07:06:32あとpは固定でも桁数が2^n ごとに小さいサイズの計算で済みますよ
例えば、桁が8桁しか無ければ8*8行列のフーリエ変換を何度かやれば済みます
pは大きくしたり、小さくしたりすると不便なんです 小さくしたら2^16進数が扱えなくなり大きくすると、32bit内に計算がおさまらなくなります
工夫すれば、別のpでも良いんですが、簡単の為に固定してます
01511
2007/12/04(火) 07:15:37効率は良くないですけど、浮動小数点は使わずに格納可能な限り全ての桁を記録しようと思います
たとえば、1/3なら0.3333333・・・なら65536桁まで記録して小数点の位置も記録します
整数と同じ扱いにしようと思います
データ構造は、2^16進数で、0個に一番小さい数を入れます
もし、非常に大きい数を扱うならば、同じライブラリを2度使って65536^32786進数でやろうとおもいます
01521
2007/12/04(火) 08:57:33#include <iostream>
#include <vector>
using namespace std;
typedef vector< unsigned int > Lint;
#define p 65537
#define N 65536
#define M 1000
unsigned int mod_p(unsigned int z){ int y=(z&65535)-(z>>16); return y<0?p+y:y;}
Lint e; void Fourier_init(){ e.resize(p); int k=1; for(int i=0; i<p; i++){ e[i]=k%p; k*=3;}}
Lint Fourier(Lint f){ Lint F; F.resize(N,0);
for(int n=0; n<N; n++) for(int i=0; i<f.size(); i++)
F[n] = mod_p(F[n] + mod_p( e[(n*i)%N] * f[i] )); return F;}
main(){
Fourier_init(); Lint f, g; f.resize(M,0); g.resize(M,0);
for(int i=0; i<M; i++){ f[i]=rand(); g[i]=rand(); }
// FFT乗法
Lint F=Fourier(f), G=Fourier(g); Lint a; a.resize(N);
for(int i=0; i<N; i++)a[i]=mod_p(21846 * mod_p(F[N-i] * G[N-i]));
for(int i=0; i<N; i++)if(a[i]==N){a[i]=0; a[i+1]++;}
//普通の乗法
Lint b; b.resize(N,0); unsigned int x, k=0;
for(int n=0; n<=2*M-2; n++){ x=k; k=0;
for(int i=max(0,n-M+1); i<=min(M-1,n); i++)
{x+=f[i]*g[n-i]; k+=x>>16; x&=65535;}
b[n]=x;}
for(int i=0;i<100;i++)cout<<a[i]<<" "<<b[i]<<"\n";}
01531
2007/12/04(火) 09:16:45#include <iostream>
#include <vector>
using namespace std;
typedef vector< unsigned int > Lint;
#define p 65537
#define N 65536
#define M 2
Lint e; void Fourier_init(){ e.resize(p); int k=1; for(int i=0; i<p; i++){ e[i]=k%p; k*=3;}}
Lint Fourier(Lint f){ Lint F; F.resize(N,0);
for(int n=0; n<N; n++) for(int i=0; i<f.size(); i++)
F[n]=(F[n] + ( e[(n*i)%N] * f[i] )%p)%p; return F;}
main(){
Fourier_init(); Lint f, g; f.resize(M,0); g.resize(M,0);f[0]=f[1]=g[0]=g[1]=2;
// FFT乗法
Lint F=Fourier(f), G=Fourier(g); Lint a; a.resize(N);
for(int i=0; i<N; i++)a[i]=(21846 * (F[N-i] * G[N-i])%p)%p;
for(int i=0; i<N; i++)if(a[i]==N){a[i]=0; a[i+1]++;}
//普通の乗法
Lint b; b.resize(N,0); unsigned int x, k=0;
for(int n=0; n<=2*M-2; n++){ x=k; k=0;
for(int i=max(0,n-M+1); i<=min(M-1,n); i++)
{x+=f[i]*g[n-i]; k+=x>>16; x&=65535;}
b[n]=x;}
for(int i=0;i<10;i++)cout<<a[i]<<" "<<b[i]<<"\n";}
0154デフォルトの名無しさん
2007/12/16(日) 00:17:520155デフォルトの名無しさん
2007/12/16(日) 18:09:35（１）F=Fourier(f),
（２）G=Frourier(g)
としたとき
（３）A=FxG (要素毎の積)
を求めた後に
（４）a=(1/N)Fourier^(-1)(A)
とやる必要があるな。>>153では（３）と（４）が抜けてる。
0156デフォルトの名無しさん
2007/12/28(金) 15:00:05> 工夫すれば、別のpでも良いんですが、簡単の為に固定してます
なら精度考慮してdoubleとかを使うFFTのほうが良くない？
あと、2^16進数使うなら大体(2^16)^2*要素数を表現できるだけの精度が必要になるはずなんだけど。
なんかあちこち変じゃない？
0157デフォルトの名無しさん
2008/01/12(土) 21:35:14末尾に並ぶ0の個数を求めるのをおながいします
0158デフォルトの名無しさん
2008/01/12(土) 22:04:345000の倍数が1個、500の倍数が10個、50の倍数が100個、5の倍数が1000個
全部足して1666個と適当に予想して見る。
ってか>>1なのかな？
0159デフォルトの名無しさん
2008/01/12(土) 22:53:50全く同じ趣旨の問題がVBAスレかどっかでみた。
それは兎も角、鼬害。
>>158
末尾に0が並ぶということは、並んだ数をnとすると10のn乗の倍数ということ。
つまり、2のn乗*5のn乗の倍数になる。
このnを求めればいいわけだが、2の倍数は過剰に存在しているから
5の倍数がどれだけあって、それぞれ5の何乗の倍数か判ればいいことになる。
即ち、5の倍数の個数+25の倍数の個数+125の倍数の個数+……
だと思ったんだけどね。
0160デフォルトの名無しさん
2008/01/13(日) 00:17:05int main(void){
int i,n=1,o=0;
for(i=2;i<5001;i++){
n*=i;
while(n%10==0)
n/=10,o++;
n%=10;
}
printf("%d\n",o);
return 0;
}
1240になったけど、これであってる？
0161デフォルトの名無しさん
2008/01/13(日) 00:44:23それ途中でオーバーフローしないか？
0162デフォルトの名無しさん
2008/01/13(日) 03:37:54大丈夫なんじゃない？
0163デフォルトの名無しさん
2008/01/13(日) 03:41:545000 / 5 = 1000
5000 / 25 = 200
5000 / 125 = 40
5000 / 625 = 8
5000 / 3125 = 1
1249個になるね
0164デフォルトの名無しさん
2008/01/13(日) 09:28:47--
4228577926605543522201064200233584405390786674626646748849782402181358052708108200690899047871706387
5370847466573006854458784860666838127363372108937727876312793903630584621606439044789869822398719297
.
.全部で16300桁以上
.
3713673959956789408847059768595145050172415177460173514309909726155093783347200000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000
--
ということで、1249だった。
0165デフォルトの名無しさん
2008/01/13(日) 15:32:260166デフォルトの名無しさん
2008/01/19(土) 03:20:07剰余類によるFFTとdoubleによるFFTで乗算作ってみた。
C++で作ったんだけど、どうがんばっても、doubleのほうが早い。
とにかく法mがネック。
任意のmを用いることができないので設計が大変。
2^k+1の形にしておかないと、フーリエできないし、
素数じゃないといけないし、剰余が早くないといけない。
俺は
2^32(2^32-1)+1 2^32*(2^32-4)+1 2^16(2^16-16)+1 2^16(2^16-33)+1
などを使った。
で、剰余は結構早くできるようになったんだが、それでも遅い。
剰余が入るとdoubleのFFTに比べて大体2倍になる。
つぎに最大値の問題。
乗算後の各項の係数の最大値は「項数*(基数-1)^2」になるので、
法mはそれ以上であるか、もしくは法を二つ用意して2回FFTして、
中国剰余定理から求めないといけない。これでさらに2倍かかる。
結局、doubleで精度を考慮して作ったのと剰余類でがんばって作ったのだと、
4倍くらい速度差がでる。
>>73の言うとおりだった。
俺の実装が悪いだけかも知れんので、できればFAのソースが欲しい。
0167SNLIB
2008/04/15(火) 21:38:53今のCPUでは不動点小数演算の方が整数演算よりはるかに高速です。
したがって、FFTはdoubleを使うのがいいと思います。
数千桁程度まではアセンブラを使った「多倍長BASIC」が高速です。
それ以上になると・・・
Ｃ＋＋による多倍長計算
http://www.vector.co.jp/authors/VA018507/index.html
の作者です。
Wondows上でも動くgcc(minGW など)インストールすれば使えます。
Dev-C++と日本語環境をインストールすればさらに使いやすくなります。
SN Library は日本人（私^^）の書いた英語ですから分かると思います。
ちなみに、50000！は関数にしていますが、Pen4 3.0GHzで0.75secです。
普通のfor文にすると比較していませんが、GMPより遅いでしょう。
0168デフォルトの名無しさん
2008/04/16(水) 01:22:14大嘘と宣伝乙。
0169デフォルトの名無しさん
2008/04/17(木) 13:11:060170デフォルトの名無しさん
2008/04/17(木) 22:46:400171デフォルトの名無しさん
2008/04/17(木) 23:01:000172デフォルトの名無しさん
2008/04/17(木) 23:03:130173SNLIB
2008/04/17(木) 23:23:31PC98にコプロセッサを積むとフラクタル図形が１時間かかっていてものが
１分以内になったことに感動しました。１０年前の話です。
「Javaによるアルゴリズム事典」も読んだ人がいないようですね。
0174デフォルトの名無しさん
2008/04/17(木) 23:37:510175デフォルトの名無しさん
2008/04/17(木) 23:47:08Super PI ベンチマークランキング
http://www16.big.or.jp/~bunnywk/superpi_index.cgi
0176デフォルトの名無しさん
2008/04/17(木) 23:50:44一部大きな差が出たのは、HDBENCHのメモリ項目でメモリ項目で
Athlon 64 X2が20%以上早く、浮動小数点演算も35%早いものの、
逆に円周率演算のベンチマークソフトSuperπではCore 2 Duoが20%早いという結果に。
AMDはこのデータをもとにして「ひたすら円周率の計算をしたい人ならCore 2 Duoを買ってください」と皮肉った。
http://www.watch.impress.co.jp/akiba/hotline/20060812/etc_amdevent.html
0177デフォルトの名無しさん
2008/04/18(金) 19:48:14円周率の計算といえば、SuperPI, pi_css6, PiFast, QuickPiなどは軒並み、浮動小数点演算で計算してるな。
整数演算で計算してるのはGMP系(gmp-chudnovsky.cやmpfr_const_pi関数)ぐらいか？
0178デフォルトの名無しさん
2008/04/18(金) 20:19:400179デフォルトの名無しさん
2008/04/18(金) 21:05:39http://www.geocities.co.jp/SiliconValley-Bay/9439/negoto/ngt006.htm
今やSuperPIは実質、ランダムライトベンチマークと思っていい。
Core 2 はキャッシュがでかくて104万桁計算時に全部キャッシュに収まるから結果がいいだけ。
0180デフォルトの名無しさん
2008/04/18(金) 21:20:01浮動小数点が得意なAthlon64 X2 6400+ は、PentiumM やPentium 4 にも負けてるぞ
0181デフォルトの名無しさん
2008/04/18(金) 21:21:520182デフォルトの名無しさん
2008/04/18(金) 21:33:15作者に聞かなくてもVTune使えばすぐに分かることだろ。使ったことないのか？
0183デフォルトの名無しさん
2008/07/01(火) 16:42:560184デフォルトの名無しさん
2008/07/17(木) 08:41:19GMPのバイナリ置いてある
http://www.cs.nyu.edu/exact/core/gmp/
0185デフォルトの名無しさん
2008/07/17(木) 10:08:30C++の演算DLL作ったら、配布して良いんですか?
0186デフォルトの名無しさん
2008/11/08(土) 20:12:46FFTを使った多倍長演算とモジュラ法(中国剰余定理)を使った多倍長演算
どっちが速いの？
ちなみに変換にかかるコストを度外視すればどちらもO(n)時間で計算可能。
0187デフォルトの名無しさん
2009/02/11(水) 20:30:570188デフォルトの名無しさん
2009/04/01(水) 23:14:29多倍長演算ライブラリ。
386に最適化してるんで今のCPUじゃCの方が速そうだけど。
superPIの作者やPI計算のギネスに載ってた人（T大K氏）との意見交換とかもして、
当時としてはトップクラスだったと思うよ。
速度優先だと、
A=A+B, A=B+C が違う関数になるし、
A=B^2 は掛け算とは別の関数になる。
フーリエ変換は巨大メモリにバラバラにアクセスするので、
速度を稼ぐなら適宜並び替えると良いよ。
メモリに収まりきらないような巨大なFFTを高速に行う技術を、
今用のメモリとキャッシュ用の最適化にそのまま使えると思う。
ライブラリとして公開するつもりはないけど、
アドバイスはいろいろ出来ると思う。
0189デフォルトの名無しさん
2009/04/03(金) 20:56:08ソース公開しろ
0190デフォルトの名無しさん
2009/04/04(土) 09:55:32ソースもバイナリも公開するつもりはありません。
0191デフォルトの名無しさん
2009/04/04(土) 13:37:18まぁ、>188で「公開するつもりはない」と明言しているわけで。
恐らく、>188氏はくれくれに対しては厳しくても自力で頑張る人にはヒントをくれるんじゃない?
0192デフォルトの名無しさん
2009/04/07(火) 00:28:480193デフォルトの名無しさん
2009/04/16(木) 18:15:340194デフォルトの名無しさん
2009/04/17(金) 21:26:54というのはどう思いますか、普通のFFTの方がキャッシュのヒット率が良いと
思うのですが
0195デフォルトの名無しさん
2009/04/17(金) 23:32:49「なんの役にも立たないソフトを作ったら晒すスレ」に上がってるな
5000! を計算させたら１０秒くらいかかったぞｗ
0196デフォルトの名無しさん
2009/04/18(土) 15:07:40CPUのスペックにもよるだろうが、
5000!で10秒って遅いか？
0197デフォルトの名無しさん
2009/04/18(土) 16:44:20実行したとたんに答えが出ている。
0198デフォルトの名無しさん
2009/04/18(土) 17:21:010199デフォルトの名無しさん
2009/04/18(土) 17:29:03そんな事したら>>1は何をすれば良いんだ。
0200デフォルトの名無しさん
2009/04/18(土) 19:54:000201デフォルトの名無しさん
2009/04/18(土) 20:06:09電池が切れるんじゃね？ｗ
0202デフォルトの名無しさん
2009/04/18(土) 20:19:08前者は1秒弱の遅延があるが後者は全くなかったので、69エントリのテーブルを持っているのではないかと噂されていた。
0203デフォルトの名無しさん
2009/05/04(月) 14:12:57もしも嘘じゃないなら宣伝料支払うことになるけど？
0204デフォルトの名無しさん
2009/05/09(土) 13:49:250205デフォルトの名無しさん
2009/05/21(木) 21:13:160206デフォルトの名無しさん
2009/05/22(金) 09:39:18ARM では、整数 FFT で性能出してるよ。１もがんばれ
0207デフォルトの名無しさん
2009/06/15(月) 22:40:24もう作るの諦めた系なんですか？
0208デフォルトの名無しさん
2009/06/23(火) 10:37:130209デフォルトの名無しさん
2009/07/29(水) 07:32:150210デフォルトの名無しさん
2009/08/05(水) 02:19:19(CPUはNorthwoodの3.06GHzだ)。
10秒かかるようでは遅かろう。
0211デフォルトの名無しさん
2009/08/13(木) 20:38:580212デフォルトの名無しさん
2009/08/13(木) 21:43:30単なる汎用多倍長演算処理のソースになら著作権はあるだろうがな。
0213デフォルトの名無しさん
2009/08/28(金) 08:29:45言われた。3210!なら一瞬で終わった。
ということで10秒はやっぱり遅すぎ。
0214デフォルトの名無しさん
2009/08/30(日) 20:18:060215デフォルトの名無しさん
2009/08/31(月) 10:43:17既に公開してる（事前提の）物に特許とな？
0216デフォルトの名無しさん
2009/08/31(月) 11:04:490217デフォルトの名無しさん
2010/05/15(土) 18:45:360218デフォルトの名無しさん
2010/05/16(日) 00:17:020219デフォルトの名無しさん
2010/07/06(火) 12:13:330220デフォルトの名無しさん
2010/07/09(金) 22:00:380221デフォルトの名無しさん
2010/07/12(月) 10:30:100222デフォルトの名無しさん
2010/07/12(月) 11:30:380223デフォルトの名無しさん
2011/06/30(木) 11:48:29.190224デフォルトの名無しさん
2011/07/01(金) 03:04:59.84あの時お前が間違えなかったら
こんなことにはならなかった
0225デフォルトの名無しさん
2011/07/02(土) 03:59:28.190226天使 ◆uL5esZLBSE
2011/07/02(土) 10:01:45.59はいはいゴミゴミ
0227デフォルトの名無しさん
2011/07/09(土) 02:59:36.34マジレスすれば、日本は公開するからサブマリンは有り得ない。
0228デフォルトの名無しさん
2011/07/10(日) 11:36:34.240229デフォルトの名無しさん
2012/07/10(火) 19:12:51.59■ このスレッドは過去ログ倉庫に格納されています