計算アルゴリズム

プログラム板の皆さん、こんにちは。
無謀にもこんなスレを立ててみました。
四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
人間にとって計算しやすい方法についても別途語ることにしましょう。

無限の桁を計算できる計算機つくってくれ

7-ZIP使え
終了


と言ってみるテスト

↑あああああああああああああああああああああ
誤爆った

>>2
Ruby でメモリの限界までやってみれ。

>>2　不可能です。

以上終り。

初めに、十進数を二進数に変換する方法と、
二進数を十進数に変換する方法を述べよう。
私の知っている方法は、
十進数を二進数にする方法は割り算を繰り返すこと
(例えば、21は次のようになる。21=2^1*10+2^0=2^2*5+2^0=2^3*2+2^2+2^0=2^4*1+2^2+2^0=2^4+2^2+2^0となる。)
であり、二進数を十進数にする方法は、多項式計算である。
(例えば、2^4+2^2+2^0は1*2^4+0*2^3+1*2^2+0*2^1+1*2^0であり、それは、(((1*2+0)*2+1)*2+0)*2+1である。
ちなみにこれをやるには、十進法の範疇で足し算をしないといけない。)

基数変換が出来れば、あとは任意の基数で計算の説明ができる。

なんで king がここにいるの？

十進表現＞二進表現はビットマスクをシフトしていくだけでできる。

なお十進数と二進数は、あくまでも表現形式の違いであり、対象となる「数」は同じものである。
「十進表現を二審表現に変換する」が正しく、「十進数を二進数に変換する」は厳密にはおかしい。

Re:>9
帰れ。
http://tv6.2ch.net/ainotane/

Re:>10
ようやく話の出来そうな人が現れてくれた。
ちなみに、ビットマスクって何ですか？

int n = 12345, mask;
for(mask = 1 << (CHAR_BIT * sizeof(int) - 1); mask; mask >>= 1)
putchar(mask & n ? '1' : '0');

こういうことだべ。

>>11
まずANSI-Cから始めような

Re:>12
C言語のプログラムを実際に使おうと思ったらコンパイルしないといけない。
そして、そのコンパイルのときに12345を二進数に変換しなければいけないはずだが、
それはどうやっているのだろう？

>>14
12345がすでに二進数で管理されてます

以上、ANSI-Cから始めような

king ｶｴﾚ http://science3.2ch.net/math/

Re:>15
その12345は、
00110001
00110010
00110011
00110100
00110101
(順番が違うかも知れないが。)
というデータで管理されているに違いない。
一方、計算時に必要なデータは、
11000000111001
である。
よく考えよう。

素数を求めるアルゴリズムでも考えてくれ。

Re:>17
だから早く帰ってね。
http://science3.2ch.net/test/read.cgi/math/1087911996/l50

> というデータで管理されているに違いない。
環境依存では？

以上、ANSI-Cから始めような

>>14
まず最初に、コンパイラ作れ。

KingMath〜とは？
　・東京大学の院生で専門は解析らしい。
　　性別は男である可能性が高い
　・最初期には「Q.man」というハンドルを使い(違うかも)
　　現在は「FeaturesOfTheGod ◆UdoWOLrsDM」である
　・ハンドルは４、５回変えている
　・Q.man時代: 2002年(もっと前？)頃から確認されている。微妙にガキ臭い。
　　mathmania時代、supermathmania時代などを経て、
　　KingMath〜時代: 「Re:>>レス番」や「吾」などの独特の口調と、
　　良く分からんハンドルのせいでウザがられる。
　　煽られることもしょっちゅうだったが、自分から噛み付くことは少なかった。
　　比較的穏やかで、知識量も凄い。
　　FeaturesOfTheGod時代: 狂いだした。詳しいことは分からない。

私は狂ったのではない。新たなる自分を手に入れて大いなる目的を果たそうとしているのである。

数学のプロ目指してるなら数学やっていればいいのでは。
アルゴリズムを具体的な計算機の上にどのように実装するか
なんて泥臭い話は、はっきり言えば学問ですらない。

計算アルゴリズムの話をしようというのにANSI-Cをやれとはどういうことか？

コンピュータ・アルゴリズムの話では
ビットの話が出てくる可能性がある
（というか出てきてるのにビットについて理解してない）ので
ビットについて理解を深める為にもANSI-Cを始めような

Re:>22
アウェイで、気違いやらないで。
ホームに(･Ａ･)ｶｴﾚ!!
http://science3.2ch.net/test/read.cgi/math/1087911996/l50

物理屋と数学屋と計算機屋は似て非なるもの。同属相憎み相愛す。

さて、次は足し算をしよう。
初めに、符号無し8ビットのデータ同士の足し算を考えたいのだが、
ここでは話を簡単にするため符号無し1ビットとしよう。
天下り的に数データの他にCFというビットを付け加えよう。(これが何に使われるべきデータかは何となくわかるかも。)
CFには0が格納されていると仮定する。
0と0の和を計算するときは、計算結果を0とし、CFも0にする。
0と1の和、および1と0の和を計算するときは計算結果を1とし、CFは0にする。
1と1の和を計算するときは、計算結果を0とし、CFは1にする。
CFが1になっている場合は、
0と0の和の計算では計算結果を1としてCFを0にする。
1と0の和、0と1の和では、計算結果を0としてCFを1にする。
1と1の和のときは、計算結果を1として、CFも1にする。
(まだ完全な説明にはなっていないが、まあいいか。)

Re:>28
http://acm.uva.es/p/v102/10225.html
この問題を解いてくれ。
私には分かりません。

>>28
論理設計からやり直し。

mov eax, a+0
mov edx, a+4
add eax, b+0
adc edx, b+4
mov c+0, eax
mov c+4, edx

>>18
これの64から後で多くの言語による素数プログラムが公開された

【初心者】課題をクリアしていくスレ【講習会】
http://pc5.2ch.net/test/read.cgi/gamedev/1086858349/

このスレを思い出した
ﾊﾟｿｺﾝ初心者がﾌﾟﾛｸﾞﾗﾑを一から始めるｽﾚ
http://pc5.2ch.net/test/read.cgi/tech/1039176097/

バカは放っておけば勝手に飽きるからむしな

任意の整数値Ｎをあたえて
Ｎ番目に小さい素数、Ｎ番目までの素数の和、Ｎ番目までの素数の逆数の和
を求めるプログラム

FORTRAN II
http://pc5.2ch.net/test/read.cgi/tech/1068351911/550

>>33の自演ぐらい凄いことやればスレも続く

でも住民は放置な

Re:>33 私が欲しいのは計算アルゴリズムであって、プログラムではない。

>>28
そんなのはアセンブラの命令でもできる。
そういう話は高級言語レベルではない。
ハードウェアレベルの話。

「アルゴリズムについての話」と言うから、せめてニュートン法くらい出てくるのかと思った…
漏れは甘かった。

Re:>36
http://acm.uva.es/p/v102/10225.html
解いて(はーと

初等整数論だな。
ガウスでも読んどけ。

>>39
>>38は知ってて聞いてるんじゃない？
フェ…って。

> 「アルゴリズムについての話」と言うから、せめてニュートン法くらい出てくるのかと思った…
一応 king なんだし、ニュートン法くらい高校時代か、受験時代にやったことあるんじゃない？
というか、ニュートン法が出てきたところで何なの？

Re:>38 フェルマーの定理は群論の知識から明らかなんだよねぇ…。

Re:>36 まあ、[>1]を読め。誰もそっち方面の話をしないなんて言ってない。

Re:>37 まあ、[>1]を読め。誰もそっち方面の話をしないなんて言ってない。

Re:>39 ガウスを読むとは？

>>36
本屋に行くと解説している本はたくさんありますが、
http://www.amazon.co.jp/exec/obidos/ASIN/4822281655/
とかがわかりやすいと思う。

この際、足し算と引き算の説明は省略してもよいことにしよう。
私は、掛け算、割り算、そしてsin,cos,exp,ln,asin(Arcsinのこと。),atan(Arctanのこと。)などをどうやって速く計算するのかを知りたい。

>>45
ぜひ、足し算と引き算の説明をしてください。
興味あります。

> 私は、掛け算、割り算、そしてsin,cos,exp,ln,asin(Arcsinのこと。),atan(Arctanのこと。)などをどうやって速く計算するのかを知りたい。
基本的に、テーラー展開をただ計算するだけです。
たぶん、king が思ってるほどたいしたことをやってないと思う。

ここは計算アルゴリズムの最適化をするスレなの？
それとも公式化されてるものをC言語のコードに展開するスレなの？

>>41
> 一応 king なんだし、ニュートン法くらい高校時代か、受験時代にやったことあるんじゃない？
とてもそうは見えない。
http://www.amazon.co.jp/exec/obidos/ASIN/4874084141/249-5539512-0456302
このくらいは読みましょう、というレベル。

> というか、ニュートン法が出てきたところで何なの？
解析的に解けない関数の解を高速に求めるのです。
制限はありますが。

一つ言っておきたい。
ここで議論するなら、数式よりもコードの方がコミニュケーションとりやすい。
意味不明な日本語の羅列は論外。

rm -rf >50

バカな私としてはむしろ数式とコードを一緒に書いて欲しいな。
sinとかラジアンとかコードだけで理解してるのに最近疑問を感じる。

Σのズレまくりの式とかもう見てランナイ。

オイラー法が安定する条件が知りたい。

Re:>54
オイラー法は、精度がかなり悪くなかった？

Re:>king
http://acm.uva.es/p/v102/10225.html
の解き方はやく教えてね(はーと

ちなみに問題は、
B, N, P が与えられたときに
B^L ≡ N (mod P)
を満たす L を出力、無かったら "no solution"

精度はあまり気にしないんだけど、安定して動いてくれればいいという感じなんで。

計算機代数ｊについてかたるスレはここですか？

Re:>56
http://jun.artcompsci.org/~makino/kougi/system_suuri4_1998/all/node53.html

Re:>king
ﾏﾀﾞｰ?(AA 略

Re:>47
私も冪級数展開ぐらい知ってるよ。だが、冪級数じゃ遅いんだ。

Re:>46
足し算については、[>28]を参考にしよう。
引き算は、補数をとって足し算すればいい。

>>21
> 　　良く分からんハンドルのせいでウザがられる。
良く分からんが、良く分からんハンドルだというだけでウザがられる理由が意味不明。
親につけられた自分の名前きいたことも無い名前だったらウザいと思わなくちゃ行けないのか？

Re:>60 もういちいち粘着の相手をしなくていい。

>>49
C言語版よりも情報が10年も新しい分こちらもお勧めかな。
http://www.amazon.co.jp/exec/obidos/ASIN/4774117293/qid=1090244519/sr=1-4/ref=sr_1_10_4/249-4919465-9229144

>>60
親につけられたのならかわいそうだとも思うが、
自分でつけてるんだしなぁ。

Re:>59
三角関数なら、tan x を連分数展開すればはやくなるんじゃないの？

他所のライブラリでソース公開してるの読めばいいのでは？

はーどでは？

基本的に直列に計算する必要があるソフトによる実装と、
並列に演算を行うことができるハードによる実装では事情が異なる希ガス

>>12
> int n = 12345, mask;
> for(mask = 1 << (CHAR_BIT * sizeof(int) - 1); mask; mask >>= 1)
> putchar(mask & n ? '1' : '0');
>
32bits環境で使っているのでこいつをCHAR_BITを32bitsにしたらとんでもないことになりやがった。
1が無数に表示されて止まらないプログラムになった。

>>68
それはタダのバカ。sizeof(int)が何のためにあるのよ。

CHAR_BITを1にしたら1001と四桁で返ってきた。

>>28みたいな話って大学1年レベルだよな
本当に院生なの？

基本情報処理を取ってない奴なんてしょせんあんなレベル

でも>>28のFulladderだと伝播遅延の問題があるから
イマイチだと大昔に授業で習った事がある気がする

あーあ、king すねちゃってどっかいっちゃった〜

Re:>71 私はそんなこと知らないな。お前の所属研究科を言え。

Re:>72 そんなの知らないな。

Re:>73 それじゃあ、どんな加法があると？

Re:>75
おはよう

中学生の自由研究にはちょうどいいレベルかもしれない。

Re:>77 お前には[>1]が見えないのか？

Re:>76 七時五分。

>>78
つまり、中学生向けのスレということでOK？

sin　cos　級数展開が高速です 前処理として円を４または８、２４分割しておくのは当然ですね

exp 級数展開の他 exp(x+y)=exp(x)*exp(y) を使って分割するのも高速ですバイナリ分割すればビット数で計算できますから

asin/atan　近似計算をしておいて最後にニュートン法１発が楽で早いでしょうか

kingは確かに優秀だが、そろそろ2chについても理解を深めて欲しい。

スレ立てる時ぐらい名無しになりましょう。

> sin　cos　級数展開が高速です 前処理として円を４または８、２４分割しておくのは当然ですね
> exp 級数展開の他 exp(x+y)=exp(x)*exp(y) を使って分割するのも高速ですバイナリ分割すればビット数で計算できますから
> asin/atan　近似計算をしておいて最後にニュートン法１発が楽で早いでしょうか
どのくらいはやいの？

>>75
お前の専攻が何か知らないけど研究科とかの
レベルじゃなくて学部1年のレベルだよ。
さらにこの分野で基数変換やビット演算なんて
小学生に「1+1=2です、1+3=4です。」程度のレベルのことであって
それを「計算アルゴリズム」なんて大それた名前にして堂々と
書いてるのが痛々しくて見てらんない。

Re:>79 私は計算アルゴリズムが欲しいと言った筈だ。

Re:>80 もっと速い計算方法があるはずなのだが。

Re:>81 何故？

Re:>82 言っとくけど、計算可能ならいい、という話ではない。私も冪級数展開ぐらい知っている。

計算アルゴリズム云々の前に、それを理解する基礎学力が足りてない予感。

おれは行列の計算を速くする方法を知りたい

>>86
VPUで

周辺コードも含め、既に最適化されつくされてるんちゃうん？

LU分解について教えてください

三角関数は変なアルゴリズム使うより普通に計算したほうが速いよ。
現在の普通のCPUなら。単純な多項式展開ですら２項目まで計算すると勝てない。
それでも知りたいなら「Numerical recipes」を熟読すれば色々思いつくはず。
sqrtだったら逆平方根を求めるCPUの命令からニュートン法でだいぶ速くなる。
加算器の改良については「アルゴリズムイントロダクション3」が詳しいと思うのでそちらを参考に。

ビットフラグがいくつ立ってるか数えるってアルゴリズムが有るけど
あれは解答が常識外なやり方だからな

ソース嫁ってのが一番かと

Re:>85 誰に何が足りないと？

Re:>90 普通にとはどういうことか？

いちど、アセンブラで書いてみたら？

fld ang
fsincos

Re:>93
アセンブラで二進表現のデータから十進表現の文字列を取得するにはどうすればいいの？
アセンブラで十進表現の文字列から二進表現のデータを取得するにはどうすればいいの？
(とりあえず、Intel系プロセッサでおね。)

>>92
普通にってのはCPUに用意されている浮動小数点数命令を使えってことじゃないの

アセンブラスレで聞けばいいんじゃないかな？

綺麗に>>83だけスルーしたな

>>95
そんなん知って何をしたいのか知らんが、
とりあえずその辺のコードをディスアセンブルすればいいのでは？

ノイマン型コンピューターの十進数から二進数とかってどう考えても
何十年も前に語り尽くされてるだろ。
こんな大学で最初に学ぶようなことではなく院生なら新しいパラダイムの
コンピューターのアルゴリズムとか考えろよ。

やばい king 意味不明。

>>100
院生にまで行ける頭を持ってるのに、後追い学習で満足しちゃうってのはずいぶん無駄な事してるよな

kingの情報工学の知識があれなのはいうまでもないが、このスレの連中もそうとうヤバそう。

まだ19才だからね。

19なの？院生じゃねーじゃん

Re:>98 番号間違えただけだが。

そろそろ掛け算に行こう。
小学生でも思いつく方法は、筆算だ。
これは足し算の組み合わせでできる。
例えば、110*101は、11000と、110の和で大丈夫だ。
さて、問題は割り算の方だ。どうやってやろう？

掛け算割り算はレジスタがそういう命令持ってるだろ？

mov eax, [a+0]
mov edx, [a+4]
mov ebx, [b]
dvi ebx

おっと
×dvi
○div

Z80の時代にタイムスリップしたみたいだ。

>>107
筆算も知らんのか。

Re:>111 加減乗除ではそう感じるのも無理はない。

というか、関数計算のネタを用意してないんだけど…。
(再三に亘って言うが、冪級数展開、二分法、ニュートン法は知っている。)

既存のソースコードを抜き出してそれで検討してみたら？
ビット演算の性質を捏ね繰りまわしたものが多々あるから数学一辺倒では話が盛り上がらない

先ずは、平方根の計算方法について。(誰か語ってくれ。(いや、ちょっとは誰かが言ったけど。))

FSQRT

数値計算の話かと思ったら、突然加減乗除の話はじめたり(しかも中途半端)、
文字列と数値の変換の仕方教えろとか言い出すし。
なにがやりたいのかさっぱりわからんスレだ。

f(x) = x^2 - a をニュートン法

>>118
それは知ってるらしいよ。

コンパイラに付属してるコードってこういうところに公開するとNG?

gcc なら ok

>>120
ライセンスによるのでは？

sqrt(x) = exp(1/2 log(x)) とか？

"Hacker's Delight"

Oh Hacker's Delight !!

>>95
; eax　数値
; edi　32バイト以上ある文字列バッファへのポインタ
bin2str:
xor ecx, ecx
.next
xor bl, bl
shr eax, 1
rcl bl, 1
add bl, '0'
mov [edi+ecx], bl
inc ecx
cmp ecx, 32
jb .next

; esi　変換元への文字列へのポインタ
; eax　[戻り値]結果の数値
str2bin:
xor ecx, ecx
.next
cmp [esi+ecx], '1'
rcl eax, 1
inc ecx
cmp ecx, 32
jb .next
2つとも適当に作ったんで間違っている部分があるかも。

結局>>1のクレクレスレなわけね

从*･ ｡.･)＜ king がそんなことするわけないの

>>90
> 三角関数は変なアルゴリズム使うより普通に計算したほうが速いよ。
> 現在の普通のCPUなら。単純な多項式展開ですら２項目まで計算すると勝てない。
> それでも知りたいなら「Numerical recipes」を熟読すれば色々思いつくはず。
> sqrtだったら逆平方根を求めるCPUの命令からニュートン法でだいぶ速くなる。
> 加算器の改良については「アルゴリズムイントロダクション3」が詳しいと思うのでそちらを参考に。

へぇーあのほんそんなに凄いんだ。
英語版しかもってないが日本語版はどういういろの本だっけか？
英語版は赤い分厚い本だったな

>>95
>アセンブラで二進表現のデータから十進表現の文字列を取得するにはどうすればいいの？
A レジスタの値が二進表現で 00000101 だとすれば、
ADD A, 00110000
で取得可能。
(ただしAは10未満。10以上の場合は10で割りながら余りに対して処理してループ。)

>アセンブラで十進表現の文字列から二進表現のデータを取得するにはどうすればいいの？
上の逆を行えば良い。

>>118
ニュートン法は1回で精度が倍になるから最終段はニュートン法だけど、
回数を減らすには初期値＝近似値をどう計算するかにかかってるね。

掛け算が高速ならバイナリ検索も早い

>95
＞(とりあえず、Intel系プロセッサでおね。)
浮動小数点命令使えよ。
まさか、コプロ以前のCPUとか言い出さんだろうな？
んなもんは10年以上も前に語り尽くされた事だし、書籍も腐るほど出てる。
いまさら実装する意味も無い。

>1
＞四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。
とあるが、精度が変われば最適なアルゴリズムだって変わる。
最適化を目的としてるなら、まずターゲットを決めろ。

＞人間にとって計算しやすい方法についても別途語ることにしましょう。
完全に板違い。

> 完全に板違い。
まぁ、数学板の住人だからね。

人間にとって計算しやすい方法を研究することが、無駄とは限らないんじゃない？

CS板がないことの弊害だな。情報システム板をそろそろ潰そうぜ。マジで。

>>132-133
コンピュータにとって計算しやすい方法を研究する方が良いよね

人間にとって計算しやすい方法を研究することによって、
新しいコンピュータの研究に繋がらないとは言いきれない。
それはそれで面白いと思う。

人間にとって計算しやすい方法は
コンピュータにとっても計算しやすい事が多い

人間にとって計算しやすい方法は十進数であるか？

指が十本だからキリがよくて数えやすいんだよ

>人間にとって計算しやすい方法は
>コンピュータにとっても計算しやすい事が多い
んなこともない、得意分野が違う

指が十本だから 2^10までじゃない？
从*･ ｡.･从＜とかいってないで、期末テスト勉強汁

十進法の加減乗除は多分小学校で習う。これについては今更多く説明することもあるまい。
とりあえず、平方根はどうしよう？これにも実は筆算がある。
sin,cosなどは、それこそ冪級数からの計算となるか。

> 平方根はどうしよう？
開平を少しして、そこからニュートン法とか？

く、くだらねー。
素数とか乱数とかbignumとかやっているのかと思ったら。

>143
禿同。

>141
お前はレス読んでないのか？

平方根は>>118, >>131 でFAだろが。

三角関数なんかに関しても散々ガイシュツだが、
ttp://oku.edu.mie-u.ac.jp/~okumura/algo/archive/
にアルゴリズム事典のソースあっから、trig.cを読め。
ってーか、多倍長で高精度を求めるとかじゃなければ浮動小数点命令使え。

  てすと

Re:>144 人間がやる計算の話に移行したつもりだったのだが。

プログラミングの為の数学と算数
http://pc5.2ch.net/test/read.cgi/tech/997150743/

重複スレ。
削除依頼出しとけよ>>1

Re:>147 私がやろうとしているのは、計算のためのプログラミングだ。

世界最速らしいぞ　⇒平方根
ttp://ayusya.hp.infoseek.co.jp/ProgramAlgorithm.html

解説
http://backno.mag2.com/reader/Back?id=0000020674
http://backno.mag2.com/reader/BackBody?id=200406090500000000020674000
http://backno.mag2.com/reader/BackBody?id=200406070500000000020674000

ニュートン法で平方根を求める方法も
y=x*x となる x を求める方法と、その逆数を求める方法の２つがある。

除算命令を持っていないなら逆数を求める方法の方が早い

主催するわけでもなく、議論するつもりもなく
なんかやだ、なんかやだというレスしか繰り返せない>>1
・・・将来が心配です

>>148
146で自ら「人間がやる計算の話に移行」と仰られてますが、
考えまとめてから発言されたほうがいいんじゃないですか？

Re:>151 それに関しては識者が降臨するのを待つことにしよう。純粋数学ではせいぜい冪級数、ニュートン法レベルまでしか行けないのだよ。

Re:>152 周りの者の所為で考えがまとまらなくなるわけだが。全員に[>1]ぐらい読んで欲しい。

>>146
板違いなので、他でどうぞ。

>>153
つか、あんたが発言するから茶々が入るだけだと思うが。

>>1は100回くらい読んだけど、何が求められてるかわからない
レベル高すぎ（ﾌﾟｹﾞ

本読めばいいじゃん
どんな解答も納得しないんだろ？ｗ

>>1
単発スレ氏ねヴォケ
━━━━━━━━━━━━━終了━━━━━━━━━━━━━━━

>>1-157
自演乙。死んでこいクズ

FeaturesOfTheGodって頭悪すぎ。
実際にアルゴリズム語ってるレスは全スルーしといて、
「周りの者の所為で考えがまとまらなくなるわけだが」
とか恥ずかしげも無く言ってるし。
考えまとまらないなら書くな、って言われてんのも理解出来ないのか？

-------------------------THE END------------------------------
これ以降書き込んだら荒らしと見なします。

>21にFeaturesOfTheGodは数学科って書いてあるから
ちょっとはFeaturesOfTheGodに、まともな事を質問してあげよう。

コンピュータは、ビットでデータが格納されている訳だから
当然、それらのnビットのデータ全体は、
F_2上のn次元ベクトル空間とみなす事ができるな？

このベクトル空間は、適当な積を入れる事で、
F_2上のｎ次代数拡大F_{2^n}と同型になる。

さて、ここからが質問だが、
１．F_{2^n}の和は、どのように、計算すればよいか？（これは超簡単）
２．F_{2^n}の積はどのように計算すればいいか？
３..同様に商はどのように計算すればいいか？
４．平方根は？

この位の計算アルゴリズムを書けばみんな相手してくれるよ。

問題の意味が分からないとかって言うなよ？

問題の意味が分からないとかっ

削除依頼出しておきました。後は放置でよろ
- - - - - - - - - - - - 終了 - - - - - - - - - - - - - -

お題提供「多倍長乗算のディジタル法」
…って終わりか。

三角関数の効率の良い計算方法について知りたい香具師は
CORDICでぐぐりましょう。
…終了。

おはよう King

CORDICは掛算が遅いという条件では有効な計算方法だけど・・・・

指数関数にいたっては、どうやって計算するのか？
ちなみに、
exp(z)=�農{n=0}^{∞}(z^n/n!)としても一応計算は出来る。
(それにしても、一体プログラマはどの程度数学やってるんだ？)

>>1の呟きだけで何の公共性もないスレだな

Re:>170 どんなスレが公共性があると言えるのだ？

>>2

数学

>>162 = 線型代数ならいたてのガキ

ずっと分からないこと

√の計算ってどうしてるの？

　　　　　緊急告知
　みんなで打ち水をしよう。詳しくはこちらへ
http://tokyo.txt-nifty.com/fukublog/2004/07/post_32.html
　打ち水をすることで気温が下がります。
　打ち水に使う水はなんでも構いません。
　とにかく参加してください。

　この文章をコピぺしてほかのスレへ張ってください、
宣伝の為ですお願いしますm(_ _)m

>>174
学校で特殊学級だったの？

FeaturesOfTheGod君には、車輪の再発明という言葉を送ろう。
テキストも見ずに脳内で自己満足に浸ってても仕方ないよ。

> exp(z)=�農{n=0}^{∞}(z^n/n!)としても一応計算は出来る。
基本的に、それを計算しています。
職業プログラマは馬鹿だからそれしか出来ません。
他に出来たとしても、何も理解してません。
動けばいいのです。

> それにしても、一体プログラマはどの程度数学やってるんだ？
職業プログラマは、人生の敗北者です。
勉強できたら職業プログラマにはなりません。
東大大学院出てプログラマになる人なんて、ほとんどいないでしょ？

>>1はまず三角関数のアルゴリズムを、手に入れるなり考えるなりしてベンチマークしなさい
話題を振っておいてそれに対する反応に何のフィードバックもないんじゃ、相手する価値が無い

Re:>179
それについては識者の降臨を待つことにしよう。

自分じゃ何もしないんだな
アレか、本読むだけの暗記っ子か

>171
頭の悪いコテの居ないスレは公共性が高いな。
>180
お前そればっかりな・・・。
テメェで立てた糞スレだろ？
テメェで調べるなり、テストコード書くなり、少しは行動してみせろよ。

Re:>182
私が頭悪いのなら、このスレに頭悪くない人は居ないということになるのだが。

勉強しすぎて一周しちゃった子なのかな？
たまには学校さぼってアメフトでも見てきな

私は早めに学位を取得せねば。
ちなみに、書くネタは解析学がらみのものになる。

>>180
お前が識者とやらになってから出直して下さいませ。

ちょっとシミュレート板に主に出現するコテハンを召喚してくる。
それまでごきげんよう！

>>178
>東大大学院出てプログラマになる人なんて、ほとんどいないでしょ？
おまえが知らんだけだ

>>169
＞exp 級数展開の他 exp(x+y)=exp(x)*exp(y) を使って分割するのも高速ですバイナリ分割すればビット数で計算できますから
って書いてるじゃない。
　aを0.5〜1の範囲として
　x = a*2^N に分解して（浮動小数点ならそのまま）
　 a= Σa[i]*2^-i とバイナリ分解して
　exp(2^-i)を先に求めて掛け算するだけでも、そこそこ早いよ

>>174
>>149-150を参照

>>144
> >141
> お前はレス読んでないのか？
> 平方根は>>118, >>131 でFAだろが。
> 三角関数なんかに関しても散々ガイシュツだが、
> ttp://oku.edu.mie-u.ac.jp/~okumura/algo/archive/
> にアルゴリズム事典のソースあっから、trig.cを読め。

おれ的にはこっちのほうがお勧めだ。こっちのほうが読みやすい。

Atan.java
ArcHyperbolic.java
Trig.java
Trig.javaはなぜかFincViewer.javaというアプレットを継承している。
継承せんでもAppletから使えるだろと言いたいところだが。
このコードを書いた香具師は継承の効率のよい使い方というものををわかてないな。
デザインパターンくらいいい加減に覚えろや。
Atan.htmlとかいうのがあるがAppletは起動せずコンパイルしても使えない。
肝心なAtan.jarが入っておらんのだから。

しかし、AtanT.javaというソースコードはいただけないな。「テスト」と書いておきながら
テスティングフレームワークすら使ってない。JUnitくらい使えよとコーダに言いたい。
学生が書いたんだろうかねえ。

行列クラスとか複素数クラスの肝心なメソッドがstaticになっているのもいただけないねえ。
Javaの特徴を生かし切れていない証拠だね。

kingかわいいよking

497 ： ：04/07/22 00:35 HOST:cr3-163-082.seaple.icc.ne.jp
削除対象アドレス：
http://pc5.2ch.net/test/read.cgi/tech/1090227743/l50
削除理由・詳細・その他：
５．掲示板の趣旨と違う投稿

オートマトンやλ計算などの計算論について
語るスレはここですか?

>>169
奥村の本ではそんな効率の悪いやり方はしていなかったと思ったぞ。

圧縮とTex好きの彼はプログラマーとしてはどないなの？神？

XMLが普及している今、彼は徐々に古い人となっている。
TeX用スタイルファイルで jsarticleとかいうほかの環境と互換性が薄いわけのわからんものを
作って論文書くのに混乱させるし。
変なTeX用インストーラ作って自分の書籍にCD-ROMとして載せて
大事なファイルを上書きさせたり
へんなところにゴミファイルため込ませてしまうし。

>>190
Java厨ってｷﾓｲね

>>197
お前はウザイから死滅スレにでも消えてすっこんでろ

おはよう

king おはよう

なんだかんだいって，のびてるよね．このスレ

中身はゼロだけどな

kingｦﾀの自演です。

kingは解析が専門と言いながら、代数に結構詳しい。
そして書き込みも代数方面のスレに目立っている。
本当は香具師は純粋数学で勝負したかったのではないか？
漏れはそう読んでいるんだが。

>>204 スレタイからして間違ってる

>>1
板違いです。数学板へどうぞ。

> kingは解析が専門と言いながら、代数に結構詳しい。
> そして書き込みも代数方面のスレに目立っている。
> 本当は香具師は純粋数学で勝負したかったのではないか？
> 漏れはそう読んでいるんだが。

ｦﾀですね.
king で ﾊｧﾊｧ やってるんですか？

ﾊｧﾊｧ,ﾊｧﾊｧ

>204
いや、あの程度の代数なんて
詳しいの内に入らない。

というか、まともに、純粋数学で勝負したいのなら
数学の論文を書くだろう。普通は。

なんでム板で数学理論なんかやってんだ？
マ板ならともかく。

数学板にスレ立て直せヴァ？

>>208
>>204は>>1の自作自演、自画自賛でしょ多分。

> なんでム板で数学理論なんかやってんだ？
ﾀﾞﾒなの？
情報系の大学生は数学理論をやらないの？
それは、プログラムの一部ではないの？
The Art of Computer Programming は、プログラムに関する本であることと、
数学理論に関する本であることを同時に満たさないの？

人生の重大な分かれ道なので、説明ｷﾎﾞﾝ。

>211
一度このすれを見直してみなさい。
お前さんが考える情報系で使える数学理論というのは
１０進法を２進法に変換する事なのか？

>>211

>>147

結論としては、このスレが削除される理由は、

(1) 板違い
(2) 重複スレ

どっち？

>>214
(3) >>1がスレの趣旨を明示しないまま逃げた

x ^ (x + 1) → ?

>214
(1) スレ的にはアリだと思うが、kingがスレ内で示したやりたいことは明らかに板違い。
(2) スレ的にアリだった場合、重複スレ。
(3) 更に糞スレ

？
１）　x^(x+1) = x*x^x
２）　x xor (x+1)

おはよーーーーー！！！

kingｷﾃﾈー

kingは今頃パタヘネ、ヘネパタ、レシピ本を読んでると思われます。

じゃ、初等関数放談を。

FPU前提であっても、三角関数や平方根は整数化する。
指数対数はなんとか整数化出来ないか考える。が、多倍長が必要ならあきらめる。

整数は、少ないデータ長で済まないか考える。
32bitプロセッサでは32bit数でも16bit数でも速度は同じ
などと言う者が居たら、実際に走らせて結果を示す。

数学的には意味無いけど、やっぱスピードは大事よね。

>>221
>32bitプロセッサでは32bit数でも16bit数でも速度は同じ
>などと言う者が居たら、実際に走らせて結果を示す。

16bitの方が遅くなったり

>>221
それは>>124を読みましょう。

スレタイは「算術演算アルゴリズム」が適当だね。

標準関数がdouble/intにキャストしてるから、double/intが速いと信じている者は多い。

議論するより試して見るといいよ。

また、ここは標準関数で満足出来る人には無用のスレかも。

アプローチはニュートンラプソン法とテイラー展開に尽きる。
問題は、工夫次第で標準関数よりも遅いものが出来上がること。

内容によるね。量多ければメモリアクセス・転送に時間かかったりするし。
ただ、doubleで書いてたコードをfloatに変更するのは危険なんでやりたくない。
もともとfloatで書いてるものならいいけど。

longをshortに書き換えるには勇気が要るが、doubleをfloatになら気軽にやりなされ。

整数化は確実に高速化しそうだね。
>>124 のサンプルソースどこかに落ちてないかな。

>>228
整数演算のテクニックは
ttp://www.tensyo.com/urame/prog/ALGO.HTM
に少しあるよ

>>229
おおー、感謝。
でも、初等関数の組合せの回避方法は豊富だけど、初等関数自体の記述は少ないね。

ぐぐるとそれらしいのが出てきた。今読んでるところ。
http://www.google.co.jp/search?hl=ja&ie=UTF-8&q=sin+cos+%E8%87%AA%E4%BD%9C+%E6%95%B4%E6%95%B0%E5%9E%8B+%E9%80%9F%E5%BA%A6&lr=lang_ja

ぐぐって一番上に出てきたのを読んでみた。
double sin(double)をint sin(int)にして、速度は６倍かあ。
もう少し速くなると期待したんだけど。

>231
その程度ならsin/cosはテーブル化した方が速そうだね。

>>231
浮動小数点の標準関数そのものがFPUで高速だからね FPUならsin/cosも同時に出るし。

こういうテクニックはDSPとかを使う機会がないと磨けないしね。

>>231
ロジックはテーラー展開そのものだけど、前処理・後処理がポイントだね。
そのへんをちゃんと解説してるサイトは少ない。
THX.参考になったよ。

>>228
> >>124 のサンプルソースどこかに落ちてないかな。

あるよ。著者のサイト。
http://www.hackersdelight.org/HDcode.htm

こういうの興味ある人は必読の本。
CGとか組み込みとかでカリカリチューニングする必要のある人など。

>>235
おもしろーい。
ありがとう。本も買ってみます。

king がいなくなったらまともになったね.

>>183が証明されたわけか（藁

他には有名なHA(C)KMEM。

MIT AI MEMO No.239
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

召喚失敗か？

誰だか知らないけど、糞スレageないでね。

Kingｷﾀ━━━━━━━━━(ﾟ∀ﾟ)━━━━━━━━!!!!!!!!!!!!!!

アク禁解けたのか.

カーナビにて
斜め上からの視点の地図を表示できるんだけど、
あれって２次元のノーマルな地図に何らかの処理をしてるんだよね？
その「何らか」がわかる人いたら教えて。
車に乗っててかなり気になった。

>>244
さんかくかんすうってしってますか？

任意のラジアンを、[-2π,...,2π]の区間に正規化したいんですけど、なんか効率のいい方法はないですかね？
単純に下のやりかたでやってたんですけど、15439054.2345ラジアンとかいう莫大な値もとるので困ってます。
　Real r = fabs( fRad );
　while( r > NGL_PAI*2 )　{
　　r -= NGL_PAI*2;
　}
　r = r * SIGN( fRad );
　return r;

>>246
　Real r = fRad - 2*NGL_PAI*floor(fRad / (NGL_PAI*2));
　return r;

そのソースプログラムから言語の仕様を適当に類推して書いてみた。
floor(x)はxを超えない最大の整数。
これならいくら fRad が大きくても大丈夫。但し、fRad が大きいほど精度は落ちる。

keta = 5
r = r - ([r / (2*π)] * (2*π))

king≒void

> [-2π,...,2π]の区間に正規化
> [-2π,...,2π]の区間に正規化
> [-2π,...,2π]の区間に正規化
> [-2π,...,2π]の区間に正規化
> [-2π,...,2π]の区間に正規化
> [-2π,...,2π]の区間に正規化
> [-2π,...,2π]の区間に正規化

[0..2π)かなあ?

>>251
アフォですか？

>>247-248
返答ありがとうございます。
除法定理で解くのも考えたんですが、仰るとおり誤差が問題なんです。

あと、どうせやるなら(-π, π]でした。

引き算繰り返したときは誤差は出ないのか？

あと、どうせやるなら[-π, π)でしょう？

return atan2(sin(x),cos(x))

>254
そもそも>246みたいなデカイ値の時点で（ry

>>253
誤差については引算繰り返しと同等の筈だよ。
もともと浮動小数点で桁数の大きいものだと少数点以下の有効桁が減少してる事に注意すべきだ。

この誤差が気に入らないというなら、最初から浮動小数点を使わない事だ。
たとえば、$80000000〜$7FFFFFFFを-π〜πにするとか

>258
誤差が見えなくなるだけで、無くなる訳ではない。

>>259
　言ってるのは、浮動小数点を使う為に、桁数の大きい時とそうじゃない時で有効桁数が違うという点について
　改善出来るという事だ。


0.001 は誤差を持ってるけど 1万倍して 記録しておけば浮動小数点でも 誤差なく記録できるのと同じだ

まぁ、ラジアンの誤差が気になるような所ならdouble使わないで多倍長使うだろうし、
ゲームなんかなら速度優先で気にしない。

なんで 15439054.2345 なんつうデカイ値になるのかわからないけど、
そんな値になる前の段階でこまめに正規化するべきだと思うけどね。

確かに気になるね.
15439054.2345 って何回転だよ！！

そういう問題かよ…

>>258
>たとえば、$80000000〜$7FFFFFFFを-π〜πにするとか
その程度の範囲しか取れないなら浮動小数点数使った方がマシ

関係ない話だが変換したらいきなり「不動小数点数」と出やがった orz

>>262
周波数カウンタで測定した結果とか

>264
ところが、
log2(15439054)≒23.88
64bit浮動小数点だと仮数部52bitで、29bitぶんくらいしか小数に割り当てられない。

そんな議論をするよりも、15439054.2345ラジアンなんて値が出てくる
>>246のプログラムを見直した方が早いような気がする。

最初から 32bit整数の最大最小を　-π〜π に
割り当てておけば足し算引き算で桁あふれを考慮しないだけで自動的にモジュラ演算になる

>>267
>そんな議論をするよりも、15439054.2345ラジアンなんて値が出てくる
> >>246 のプログラムを見直した方が早いような気がする。

15439054.2345 は外部からいきなり入力されて来るのでは？

>268
加減算だけなら。良い方法だね。
オーバーフロー検知する処理系も有るから注意。
そういう処理系では、回避する方法も普通ある。

あのお、>>256はいかがでしょう。

>271
自己主張の強い奴だな（藁
せっかくだから、精度がどんなもん出てるか比較してみた。

x = 15439054.2345

多倍精度で x - 2 * PI * floor( x / ( PI * 2 ) )
= -1.268224314194249899401256
多倍精度で atan2( sin( x ), cos( x ) )←試算の結果これが一番正解に近い
= -1.268672294250273768493362
64bit float精度で x - 2 * PI * floor( x / ( PI * 2 ) )
= -1.5027243141942499
64bit float精度で atan2( sin( x ), cos( x ) )
= -1.268672293997

超越関数３つも呼んでるから速度遅いだけかと思ったら、
こんだけ精度出るなら、CPUによるけど>247の式よりいい感じ。

それでshell sortの計算量はいったいいくつなんだ？

>272
ありがとうございました。


あと調べてみたらfmod()とかremainder()とかいう関数も見つかった。
fmod(x, 2 * pi)
5.0145130137844731　　（一回転ずれてるだけ）
remainder(x, 2 * pi)
-1.2686722933951131
(ともに倍精度）

ヘッダファイルから見つけただけで詳しい仕様は分からないけど
今回の目的そのものの関数みたい。

みなさん、ラジアンの正規化の件ありがとうございました。
>>274
fmodはまさにそのものですね。おそらく内部的には
x - 2 * PI * floor( x / ( PI * 2 ) )
と似た事をやっているんだと思いますけど。
これでテストしてみます。ありがとうございました。

244 ：デフォルトの名無しさん ：04/07/29 23:46
カーナビにて
斜め上からの視点の地図を表示できるんだけど、
あれって２次元のノーマルな地図に何らかの処理をしてるんだよね？
その「何らか」がわかる人いたら教えて。
車に乗っててかなり気になった。


245 ：デフォルトの名無しさん ：04/07/29 23:48
>>244
さんかくかんすうってしってますか？


...三角関数は関係ないだろ？
画面の下の幅よりも画面の上の幅に広い距離が表示されれば良いだけなんだから

>>276
投影変換で

>>276
その 「何らか」 が、>>277 の投影変換なら、割と基本なので
知っている人はたくさんいると思うが。

そうではなくて
　２次元の地図データから、どうやって３次元データを推定しているか？
って質問なら答えは
　もともと３次元データを持っている。
ってことで。

ごめん。わかりにくかった。
別に >>277 が間違っていると言ってる訳じゃないです。
>>276 の質問の意味が別のところにある可能性も
考えただけです。

見てる位置（真上から、斜めから）が必要なんだからその時点で３次元だとおもうが。

>>280
そのへんは、F-ZERO式に処理することもできるけどね。

>>280
そんなことを質問しないだろ。
最近のカーナビではビルや立体交差がそれなりに
立体っぽく表示されるから、それをきいてんだと思う。

おまえら違うぞ。
>>276 は コピペで、
>>244 の質問に >>245 が関係無いこと言ってると思うがどうよ？
ってことだな。

回転のところで三角関数は使うが、３D→２D写像では使わん。
確かに関係無いな。

>>244が何を知りたいのか曖昧だから>>245が関係ないのかどうかもわからん。

>>284
２次元の地図を斜めに表示してるだけってことじゃないの？

>>1
この板の香具師はハードウェア(一般的にはCPU)の上で
物事実現してるだけなのに、さもゼロから全て考えたかのような
錯覚してる香具師が多い。おまいが考えたいことはズバリ
ハードウェアの設計に絡む事柄。よって板違い。でも数学板に
逝けという意味じゃないぞ。電子板へ逝けということ。
でもあっちはあっちで、この板とは別の数学アレルギーが
あるからな。注意しろｗ

>>286
自治厨ﾜﾗﾀ

また凄いのが湧いたな。
いかにも「夏ッ！」って感じのが。

２つの整数の、整数比を求めるにはどうしたらいいんでしょうか。
（たとえば800と600なら4:3という整数比を求めたいんです)

ユークリッドの互助法で
最大公約数を求めて割ってやればいいのか。

Re:>289 ぶっちゃけ、整数m,nの整数比はm:nなんだけどね。

多倍長整数や多倍長浮動小数点数とかそれらの複素数化とか
いろんな数値クラスを作って勉強しています。ちなみにC++使っています。

それらの数値クラスに対して三角関数を始めとして
いろんな数学的関数を用意してあげたいと思っています。
全ての関数を全ての数値クラスに対して個別に用意するのは手間なので、
最初は計算アルゴリズム用の抽象クラスで多くをカバーしたいと思います。
パフォーマンスは落ちると思いますが
高速化については必要に応じて後から特殊化したいと思っています。

三角関数そのものについては良くある話らしく
様々なアルゴリズムの書籍で紹介されていました。
しかしそれ以外となると見付けるのが大変です。
この手の情報を分かりやすく紹介しているサイトはありませんでしょうか？
あと、もし何か面白いアルゴリズムがあれば教えてください。
よろしくお願いします。

『Javaによるアルゴリズム事典』
とか。

>>292
あなたの作ったライブラリで e^(iπ) = -1 を証明してください。

>>292
http://www.ecs.umass.edu/ece/koren/arith/
http://www.ece.ucsb.edu/Faculty/Parhami/text_comp_arit.htm

>>294
それって証明じゃなくて検算じゃねーの？

できました
http://www.google.co.jp/search?hl=ja&ie=UTF-8&q=e%5E%28i+pi%29+&lr=

四則演算を正確に行えるライブラリで
pow(e,i*PI)==-1を失敗する可能性は極めて低い。
複素数対応の pow(a,b) は、exp(log(a)*b) に置き換えられる。
複素数対応のexpは、実数だけ対応したexpとsinとcosに置き換えられる。
pow(e,i*PI)は exp(log(e)*i*PI) で計算される。
log(e)は当然1でありこの計算が失敗する可能性は低い。
exp(i*PI) は実数のみ対応する関数だけを使い
実数部は exp(0)*cos(PI) 虚数部は exp(0)*sin(PI) で計算される。
exp(0)==1、cos(PI)==-1、sin(PI)==0の計算方法は
知名度が高く確立された枯れた技術のためそれを採用すれば失敗する可能性は低い。
そのためライブラリの中のどこかに分かりにくいバグが潜んでいたとしても
途中の計算は『元々バグが入りにくい関数に都合の良い値を与える』ことになるため
pow(e,i*PI)==-1はそのバグに触れることなく計算が終ってしまう。
pow(e,i*PI)はとても都合の良い計算のため
ライブラリの動作確認用として使ってもあまり意味がない。
しかし-1が表示されたときの充足感は貴重なので一度は計算してみることをおすすめする。

---------------　めでたく終了 ---------------

Re:>299 何が終了した？

>>300
お前の人生
http://2chart.fc2web.com/2chart/shr.html

Re:>301 お前に何が分かるというのか？

>>302
おまえがばかってこと

Re:>303 要するに、お前は私の能力を理解できないわけだ。

>>304
このスレお前のコテで検索したけど、
基本情報レベルのことしかいってないじゃん。

>>304
あといちいち挙げんな低脳

>303-304

>183, >237-238
証明終了。

Re:>307 お前日本語は分かるか？

>>308
I'm exactly a nature English speaker.
What do you have a question?

まったりいこーやー、世の中色んな人がいるって。
人に自分の正義を強要しだすと進む話も進まなくなるわな。

ちなみにこのスレの目的は？
そんなに気合入れてち盛り上がるトピックではないと
思うんでゆっくり進めていけばいいと思うんですけど。

Re:>309 I guess I'm the greatist mathematician.

>>311
No.
I assure you are certainly a better mathematican.
But you have no new ideas.
In addition you are noting but changing very easy things into
very difficult things.
So you are seemed a silly person.

>>311
Don't up to the thread.
You must write 'sage' to E-mail cell.

自作自演おつ

don't make this thread upじゃねーかなぁ

　　　　　　　 ／　／　 ,. '´　　　,. ---｀,r＝､　　　ヽ
　　　　　　 ,:'　／　 ／／　　／　　　 i　｀丶､　　 　 ヽ
　 　 　 　 /　/　　/ , '　　／　　　　/ l!　 　 ､ヽ　　 　 ',
　　　　　/　/　　/ /　　,ｲ 　 　 　 / /||　 ',　ヽヽ　　 　 !
　　　　　!　i　l　 i /　 //　　　　／, '　l '､　',　 ヽ',　　　 |
　　　 　 !　|　!　l| !　//　 ,ｨ´∠∠',,,,,,,_', ヽ ヽ 　 ',!　　　|
　　　 　 !　l　!''7|!',´i｀!／'／／'´_,,......._ ヾ｀ヽヽ　 l!|　　 !
　　　 　 |　',　!ﾉ''ﾗ∀､､　　'´　 ,r'''ﾗ""''ヽヽ､ ヾ､　ﾘ /　|
　　　　　',　ヽ{i　{_)::::::i　　　　　　 !_）::::::::!ヽヽ　}__// 　 !
　　　　　 ',　!ヾ､ !:::::::::} 　 　 　 　 |::::::::::::} ﾉ､ !',　 ヽ 　 !
　　　　 　 ', | | ! ゝ--'　　　　　 　 ゝ---'､　 ﾉ l ノ ﾉ　/
　　　 　 　 ',', ',',　　　　　　　　　　　　　 　 /／ ,ｨ´　/ 　　　　　　　　
　　　　　 　 ',', ',丶､　　　r--､　 　 　 　 ／' ￣/　　{
　　　　 　 　 ',ヽ',　 ｀丶､ ｀　´　　_,.. ィ´'´　i 　 !　　 ヽ
　　　　 　 　 ﾉ　ヽ　　 | }｀T;ーr '´　//　　/!　　',　　　'
　　　┌/）/）/）/）/）/）/）/）/）/）l . . .l l:. l-､ . i. .i
　　　 |（/（/（/（/（/（/（/（/（/（/│. . | i:. l 　＼ .:i
　　 r'´￣ヽ.　　　　　 　 　 　 　 | | |　 .| i: .l　　　＼
　 /　￣｀ｱ >>311は　　　　　　 | | |　/| i: .l　　　　 入
　 〉　￣二).とんでもない　　　　| | |./ .| i: |　　　
　 〈! 　 ,. -'勘違いを　　　 　　　| | ヽ,r| i. l---',　'´　 　 ',
　 | ＼| |　　していたようだ　　　　　　　 　

Re:>312
If you feel my documents difficult, you are a silly person.

Re:>316
お前に何が分かるというのか？

http://science3.2ch.net/test/read.cgi/math/1096523745/l50

>>317
Your articles are michy-mouse(w
What can you know about us?

Re:>319 I cannot understand what you are saying.

>>316じゃないけど、アホなFeaturesOfTheGodのために>>316を解説してやると
>>309では
＞What do you have a question?
と言われているのに、
＞I guess I'm the greatist mathematician.
と関係のない(questionでない)ことを言っているので>>316から
＞>>311はとんでもない勘違いをしていたようだ
と言われるわけだ。わかった？

なんだ。FeaturesOfTheGodって、ただの荒らしじゃん。
アルゴリズムを期待してたのに。

> ただの荒し
< 馬鹿で異常性格者

英語が下手だな。

が→も

>>320
Your English speaking skill is very poor.
I think your article is no use.

King Mathematican cannot image mathematical concepts.
So he(she?) has written postings using abstract discriptions.
The most important thing for learning Mathematics is
to make original understandings without other person's help.

恥ずかしい英語晒すな
せめて書き込む前に辞書引いて確認しろ
image は名詞だし(書くなら imagine だろ。それでもまだ変だが)

imageでもいいんだけど、そういう場合には普通imagineを使う。
音の流れがいいんだろう。ついでに、he(she?)はhe/she/itと
書いてやるとアレっぽくてナイス。その後はグダグダなので書き直し。

レス書いてるうちに書かれた

>>328
残念ながらimageにはimagineの意を持つ動詞用法もある。辞書を引いて確認してね。

スレ違い

Most King's postings are directly written on books.

King ran away(w

>>1は数学板でも嫌われている本人は自覚していない荒らしです。
非常にたちが悪いです。

>>320
Can you tell your friend about your contribution in 2ch?
Not ashamed?

Re:>332 Merely that's a superstition.

>>336
You're wrong. They are exact.

>334
だな。
自分で立てたスレすらスレ違いの英文で荒らしたり、
程度の低い煽りにのせられてるし。

>336
お前が居ない時の方がこのスレまともに機能してるんで、
スルー出来ないなら鬱陶しいから消えてくれ。

>>338
ちょっとまて消えたら俺らの保父さんは？バブーもっと遊んでー。

まぁなんだ、英語力を誇るのは恥ずかしいな。
英語力がないのを恥じるのは分かるんだがあるのを自慢されても・・・
ガイジンさんが日本語能力を自慢しているところを想像してみなさい！

I can't quite get over the fact that Inhabitants of this board
cannot make out English.

>>339
本人は英語力があるのを自慢しているつもりでも
周りから見れば度素人の糞文だからいいんだよ

七誌のほうは腐りすぎてて読む気も失せるんだがな

Enginner needs speaking English.

>>341
しー

>>341
Why don't you retort in ENGLISH?
You seem look bad because of your soliloquy.

>>342
たった４つの単語で間違いまくってる。。。
engineer の綴間違ってるし、冠詞ないし、
というかそもそも主語は複数じゃないといかんし、
need speaking じゃなくて need to speak だし、、、
これでも英語で書き続けるのかねえ。

>>345
>>344

今のKingって何代目？

Version 3.14159

最近のKingﾀﾝ、害虫に似てきて鬱

速い計算方法は、既に今持っているソフトに入っていたりして？

荒らしが自分の名を騙られたからという事で名前を変えたようです。

King ありえないよ King

うんこ食べたい

また、名前変えてみましたづら

Re:>352 また何を言い出すのか？
Re:>353 お前こんなところにまで出張すんな！それにお前誰だよ？
Re:>354 お前何を企んでいる？

Re:>355 そっちこそオラのスレで何をするづら！

>>354-356
面倒なので省略しました

Re:>356 これお前のスレだったのか。それじゃあ、exp,sin,cos,tan,cot,sec,cosec,lnの速い計算方法を説明してくれ。

三角関数（circular function）を定義します。。

xy平面上に於いて、始線をx軸の正方向にとり
xy平面上の点Ｐと原点との距離をr
点Ｐを通る動径が始線となす角度をθとすると

θの値に対して６つの関数を定義できる。すなわち:

sinθ=y/r（sine：正弦）
cosθ=x/r（cosine：余弦）
tanθ=y/x（tangent：正接）
cotθ=x/y（cotangent：余接）
secθ=r/x（secant：正割）
cosecθ=r/y（cosecant：余割）この６つの関数を三角関数と総称する。


　　　　　y
　　　　　|
　　　　　|
　　　　　|　　　．Ｐ
　　　　　|　　　 （動径ＯＰのなす角θ、ＯＰ=r）
　　　　　|
　　　　　|
------------------------------x
　　　　　Ｏ
　　　　　（原点）

>>359
sin(x) = Σx^k / k! 　(k ∈ odd)
cos(x) = Σx^k / k!　(k ∈ even)
でいいだろ。

Re:>360 Hyperbolic sine, hyperbolic cosine か。何やってんだよ？

量子コンピューターが出来たらみんな解決だね！by小柴さんｗ

>>362
量子アルゴリズムを考えなくちゃいけない。
別の仕組みのコンピュータで最適なアルゴリズムを考える必要があるから
一般にそう簡単に解決できない。
量子コンピュータで魅力的なのはいまのところ素因数分解やデータベース検索以外に何があるの？
shorからいったいどれだけ進んでるの？

　　　　　　　　　FoG (若しくは LoL)、貴様は何を知りたいのだ？

Re:>364 速いexp,log,sin,cos,tan,sqrt,atan.

>>362-363
計算しても結果を取り出す方法がない。

>>365
君のメールアドレスを俺に教えろ。
気分がのればいくつかのアルゴリズムを送ってやる。

要素が1９万個存在するデータが２つありその差分をとりたいのですが、
LCSをメモリをあまり使用せず実装する方法ご存知ありませんか？
現在だと１６０００ぐらいでメモリを使い果たしてしまって困ってます

1要素はどんなデータ？

最長共通部分列は英語では、 longest common subsequence と呼ばれ、頭文字をとってLCSという。

char だったらその程度で破綻しないと思うが

要素はですね、
1ページ２０ｋｂ程度のメモリダンプのログがあって
最長で19万ステップ分のダンプログの比較とかをしたいのですが、
比較するときの良いアルゴリズムを知らないせいで１６０００ぐらいで、
メモリを５１２MBも消費してしまうため、何か良い手法を探しています。

>>372

ファイルに書き出せばよい、という問題でもないのですよね。
もうちょっと具体的に問題設定が欲しいかも。
ステップとページの関係がよくわからないです。

ブロック単位での処理でいいのならハッシュ取っておくとか。

近似アルゴリズムでいい?
ページのハッシュ列でLCSを計算して終了。

>>374
ｹｺｰﾝ

CRC

「珠玉のプログラミング」に出てきそうなネタだね

要素数が違う場合もあるんだよな？
差分を取るって事は、大部分は同じで極一部だけが違ってて、その違いを知りたいって事だよな？

orz‥頭のいい人ﾖﾛ

両方ソートしてからマージっぽく比較していけば？
メモリを消費してしまうというのがよく分からんが。

わからんのでググった

ttp://docs.hp.com/ja/B2355-60104-01/bdiff.1.html
>bdiff ― ラージファイルのdiff

>bdiff は2つのファイルを比べて、 diff ( diff(1) 参照)によって生成される出力と同じ出力を作成し、
>ファイルを同一にするための変更を指定します。 bdiff は diff には大きすぎるファイルを処理するために
>設計されていますが、任意の長さのファイルに使用できます。
>
>bdiff はファイルを次のように処理します。
>
>両方のファイルの先頭に共通な行を無視します。
>
>指定した各ファイルの残りを n-line セグメントに分割し、次に 対応するセグメントに対して diff を実行します。
> n のデフォルト値は3500です。
（略）
>ただし、どこでファイルが分割されるかに応じて、 bdiff が必要最小限の
>ファイル相違を探し出せる場合と探し出せない場合があります。

やっぱ駄目かもｗ

>372
すべてのファイルで一致する最長のバイナリ列を求めればいいんでしょ？

１．１件目と２件目を比較して、一致する部分の配列を新たに作成。
　　＞[バイト数, 抽出したバッファ] * 一致した個所の個数だけ
２．比較結果の配列と３件目を比較して、配列を再構成。
　　＞この時、３件目と一致しない要素は削除出来るので計算量は減っていく
３．以後４件目、５件目・・・と繰り返し。

LZ法みたいに「位置と長さ」だけ残しといて、
データの比較をする時は１件目とｎ件目、とかでもいいけど。

二分検索より速い検索アルゴリズムってあるのですか？

計算量の話ですか?

>>382
条件による。

条件は、検索される対称がソートされているとした場合です。
例えば、1,2,3,4,5,6,7,8,9,10,.......の中で、ある数字を検索する、といったものです。

計算量というのは、よくわからないですが、この場合に利用できる
私が知っている検索方法として線形検索と二分検索があり、検索対象がソートされているという条件のものでは
二分検索の方が一般的に速く検索できる、....
この意味での『速い』です。

4を探したければ、4つめを見ればいい。

>>387
radix searchだな。

>>387
すいません、検索対象がところどころ飛んでいたら..としてみて下さい。
例えば、3,100,2000,1555555,364256787, ....
の中から 1555555 を探す場合です。

>>389
一般的には二分法を元にした方が速いけど、データの量や質、構造によっては
ハッシュ値を元に探したほうが速いかもしれないし、
二分法で探したほうが速いかもしれないし、
素直に先頭から探していったほうが速いかもしれない。
複数の探査方法を組み合わせることもある。

ただ二分探索と線形探索以外の探索アルゴリズム知りたいだけなんじゃ

>>391
二分探索と線形探索以外 でかつそれより速いものを知りたいのです。

データの偏り方によっては(ry

>>392
検索しないのが一番速い
例えば>>387みたいなやつ

対象が飛んでても関係ないよ
メモリを馬鹿食いするだけ

>>394
>>387の方法では、1555555が何番目にあるかわからないので、
それが何番目にあるのかを調べる方法が知りたいわけです。

90 という要素を x という配列から探しているとき
検索途中で x[50] = 10, x[100] = 110 と分かったとき
次は、真中の x[75] でなく、x[50] と x[100] を 4:1 に分ける
x[90] を調べるとかいう方法をどっかで見た気がします。
一般には遅くなるけどソート列のデータが比較的均等な間隔で
並んでいる場合はちょっと速いとか。。。。
でも自信ありません。うろ覚えですみません。

基数ソート書いてもらえませんか？

アルゴリズム事典読んどけ。

>一般には遅くなるけどソート列のデータが比較的均等な間隔で
>並んでいる場合はちょっと速いとか。。。。

というかそういう場合にしか使えないだろうと。。。

>>397
内挿探索だな。二分探索よりも計算量の上でも速いらしい。

>>396
table[n] = -1;

table[3] = 0;
table[100] = 1;
table[2000] = 2;
table[1555555] = 3;
　：

1555555は3番ですね

>402
ﾜﾛﾀ（藁

まぁでもそういう話だよな。
連想配列使うにしても、内部の実装は良くて二分探査、
下手したら線形探査だろうし。

データの偏りとそれに対するアルゴリズムの向き不向きくらいは考えられないと、
プログラマとして生きてる価値無いと思われ。

連想配列ならハッシュだろ

うーん、結構多くの実装は赤黒木じゃない?
VC++とかlibstdc++とか

ハッシュは振る舞いが安定的じゃないから。
amortizeしないとinsertの計算量がO(n)になっちゃうし。

>>403
君も結構やばいかも(w

>>405
perl は連想配列のことをハッシュって呼ぶくらいだし、ハッシュでの実装じゃないの？
あと、C++ の STL も、非標準だけど、hash_map ってのがあるよ。

ハッシュもバランス探索木も両方良く使われるよ。

> ハッシュは振る舞いが安定的じゃないから。
これは実装かハッシュ関数が悪い。

> amortizeしないとinsertの計算量がO(n)になっちゃうし。
そんなこたあない。(というか最悪と平均とamortizeの違いを理解してないんだろう)

ある個数の整数列が存在するとします。例えば、2から17までの16個の整数があるとし、
このとき、この整数列を2グループに分け、一方のグループに属する数の平方根の和と
もう一方のグループに属する数の平方根の和との間の差が最も小さくなるような、グループ分けの
方法を発見する。このようなことを行なうにはどうしたら良いですかねえ。

>>408
ナップサック問題 or ナップザック問題でクグる。

>>408
グループの数の和が小さい方のグループに元の数列から降順に追加していく。
和は平方根のでもどちらでもいいと思う。

>>408
平方根の和が平方根の合計の半分に近い選び方を適当に選べばいいんじゃない?

>>408の16個の例だと、全検索でも32768パターンだな。

>>410
残念だがこれは0-1 knapsackなので、そういう
greedyなやり方では最適解を見逃してしまうよ。

>>412
問題のサイズが固定だから、そういうアプローチも確かに一つの見識だな。

>>412
ん？もっとパターンあるのでは？
８個と８個に分けるとは限らないだろ。
２グループとしか言ってないんだから。

ここまでのレスでは数列が「整数」列という条件はまだ誰も使ってないな。
実はこの条件を使えば魔法のように解けるんだよ。

平方根ってのにも気づいてるか？これ幾何的解法の存在の隠喩なのさ。

まあ、オマエらのような馬鹿にはこの程度のヒントじゃどうにもならんだろうが。

と、まっっったく何の見通しもなく言って orz 休日の釣りを楽しむテスト

>>408
差が最も小さくならないと死んでしまうこたあないだろう。
文句言うにもそれ以上の計算時間掛けなきゃいけないから
俺は忙しいんだと言って適当に打ち切れよ。

>>414
15bitの整数は32768個では？

>>414
> ２グループとしか言ってないんだから。
単純な数え上げもできないやつは黙ってるように。

32767通りだと思います。

>>417
> 15bitの整数は32768個では？
16bit目を0か1に固定してるから、00...0か11...1かのどっちかは含めることができないんだよ。

>>416
> 差が最も小さくならないと死んでしまうこたあないだろう。

ﾜﾗ

応用編:
・全部順番に並んでないと死んでしまうこたあないだろう。
・誤差ε内に収まらないと死んでしまうこたあないだろう。

>421
その程度出来ないとクビは切られそうだがな。

・この程度のプログラムも書けないと死んでしまうこたあないだろう。

100!の100!乗-1は素数です。

AMDのPDFにあったサンプルを見よう見まねで
平方根を求めるプログラムを書きました。見てください。

#include <stdio.h>
#include <mm3dnow.h> // vc toolkit2003

float mysqrt(float r)
{
__m64 a, b, c, d;
a = _m_from_float(r);
b = a;
c = _m_pfrsqrt(b);
d = c;
c = _m_pfmul(c, c);
b = _m_punpckldq(b, b);
c = _m_pfrsqit1(c, b);
c = _m_pfrcpit2(c, d);
b = _m_pfmul(b, c);
_m_femms();
r = _m_to_float(b);
return r;
}
int main(void)
{
for(float i = 2; i < 10; i++)
printf("√%f = %f\n", i, mysqrt(i));
return 0;
}

ねたですか？

露出狂なんだろう

4×4のフリップゲーム
・白と黒。どれか一つを選ぶと、それとその周りの色が逆転する。
例
０ １ ２ ３(y)
+--+--+--+--+
0 |●|○|●|○|
+--+--+--+--+
1 |○|●|●|●|
+--+--+--+--+
2 |●|●|○|●|
+--+--+--+--+
3 |○|○|○|●|
(x)+--+--+--+--+

(x,y)=(2,1)を選ぶと、
０ １ ２ ３(y)
+--+--+--+--+
0 |●|○|●|○|
+--+--+--+--+
1 |○|○|●|●|
+--+--+--+--+
2 |○|○|●|●|
+--+--+--+--+
3 |○|●|○|●|
(x)+--+--+--+--+
となります。
初期配置はランダム。
すべてを白、または黒にするのに必要な最小回数を求める。（求まらない時もある）

総当たりでいくしかないという結論に至ったのですが、どれだけの数があるのか
検討がつきません。人に聞いたところ２の16乗あると言われたのですが
もっとあるような・・・。
何かアイデアや質問とかあったらお願いします。

>>428-429
ttp://www.ic-net.or.jp/home/takaken/nt/light/light2.html

>430
ありがとうございました！！
すごい感動。

ここでいいかわからないけど、質問させてください。

アルゴリズム関係のWEBを探していたら、次のような所が見つけました。

ttp://tcslab.csce.kyushu-u.ac.jp/~u1/algo/report2.html
ttp://tcslab.csce.kyushu-u.ac.jp/~u1/algo/report3.html

個人的に結構興味深かったから何度も読んでみたのですが、いまいち理解できないんです。

理解した範囲では、文字数をNとすると2^Nのループ回処理を行うというように思えます。
例えば文字数が1000ならば、2^1000=1606938044258990275541962092341162602522202993782792835301376回のループの処理を行うという判断でいいのでしょうか？

それだと全然終わらないと思えるのですが、問題では2000文字以上の文字数だから、そんな問題出すとは思えないし．．．

何か理解が間違っているようでしたら、指摘ください。

済みません一部間違えました。

>例えば文字数が1000ならば、2^1000=1606938044258990275541962092341162602522202993782792835301376
↓↓
>例えば文字数が200ならば2^200=1606938044258990275541962092341162602522202993782792835301376

でした。

>>432
片方の文字列を一文字ずつ回転させて比較し最長の一致文字数を探すからN＾２かN＾３かな。

王(長島)

>>434
>片方の文字列を一文字ずつ回転させて比較し最長の一致文字数を探すから
というのは具体的にはどのようなことでしょうか？

私は次のようなものだと思っていました。
比較元がABCDEの5文字だとすると、
00001→A
00010→B
00011→AB
00100→C
．．．
11101→ACDE
11110→BCDE
11111→ABCDE
といったような文字列を作成して比較するのだとばっかり．．．

>>432
しらみ潰し法の話をしてる？それなら君の考えで合ってる。
2^N回ループを繰り返さなければならない。当然終わらないだろう。
計算量が指数時間かかるアルゴリズムは、一般的に終わらないアルゴリズム
（N=100超えると人間の生きている内には終わらない）と言われているので
もっとよいアルゴリズムを考える必要がある。
そのアルゴリズムとして、動的計画法としてそのページでは書いてあるようだ。
指摘する場所検討違いならスマン。

訂正
×そのアルゴリズムとして、動的計画法として
○そのアルゴリズムとして、動的計画法が

>>437
あ、やっぱり私の理解は合ってましたか。
漸くスッキリしました。

その後、動的計画法についてもいろいろ調べたので、他の方法は理解していたのですが、
このしらみつぶし法だけが非効率過ぎて納得できていませんでした。
これで頭を悩ませなくて済みそうです。
どうもありがとうございました。

>>439
一応言っておくと，これはLCSといってDPの中でも有名な問題．

大学のＣ言語演習でわからない問題があったのでおしえてくれませんか？

＜問題＞
文字列s1、s2を引数で受け取り、s1に文字列s2が含まれているかどうかを調べる関数searchを作成しなさい。
実行結果は、含まれているならば1を、含まれていないならば0をそれぞれ返すようにしなさい。
文字列検索関数strcmpなどは使用しないこと。

あと、string.hのインクルードも禁止らしいです。

>>441
そうか。それはよい問題を出してもらったね。
でも教えてあげない。

>>441
てか、宿題スレで答えてもらってたじゃん

わからなければ質問すればいいってのは見事に能無し養成教育の賜物だなあ。

それにしてもこれしきも自分でやろうとしない奴が大学生とは聞いてあきれる。
どこの大学よ。

>>441
どｯかで答えた記憶があるぞ
たしか"abc"が入っているかどうかってやつ

>>432
パクリチェックに使えませんか。

>>441
system関数でgrepコマンドを呼び出して、s1, s2をコマンドライン引数に当てる。
strcmp関数は使用してないし、string.hのインクルードもしてない。









これで君のレポートは０点確実だ。

マルチに仕立て上げて宿題答えさせないためのコピペ厨だろ、どうせ。

>>448
こんな問題を自力で解けないのに単位もらってちゃいくらなんでもまずいだろ。

>>441 問題の答えです。

#include <stdlib.h>

int search(char *s1, char *s2)
{
char *str;
int retval;

str = malloc(sizeof(s1) + sizeof(s2) + 20);

sprintf(str, "echo %s | grep -e %s", s1, s2);

printf("%s\n", s3);
retval = system(s3);

free(s3);

if (retval != 0)
return 1;
else
return 0;
}

おっとミスった。

#include <stdlib.h>

int search(char *s1, char *s2)
{
char *str;
int retval;

str = malloc(sizeof(s1) + sizeof(s2) + 20);

sprintf(str, "echo %s | grep -e %s", s1, s2);

retval = system(str);

free(str);

if (retval != 0)
return 1;
else
return 0;
}


これで>>441のレポートも満点だ。（ｗ

>>448
なにか問題が？

>>451
ﾜﾗﾀ

正規表現でマッチしてしまうのと、標準出力に出てくるので
仕様に反しており0点です

grep -sだなって…板違いやんか！

fgrep -s だったらええんちゃうか？
正規表現は使えんし、 /dev/null へリダイレクトしてくれるから >>454の課題はクリアしてるけど。（ｗ

まあ、>>441は grep のソースコードでもじっくり読んで勉強せぇや。

>>456
-q もいるのかな？

>>457
じゃあ450は441のためにFAをさくっと解説してやってくれや。

s1やs2にスペースが入ったら>>456も0点

その程度の問題が解らない大学生がバカなのか、
車輪の再発明をさせるような問題出しちゃう
教授だか講師だかがバカなのかは知らんが、
スレタイ読めない>441がメクラだってーのは理解した。

おまえら、それ以前に sizeof(s1) とかって気にならんのか？

それでええのんか？

450も厨なのは自明なのでどうでもいい。

すげえ
>>４50得意気

車輪は大いに再発明されるべきだと思っちゃうな。
漸次良い車輪が生き残るだろうし。

再発明だったらいいけれど、再発見は必要無し。

教えてないのにBM法考えついて実装する学生がいたら
先生やめたくなるだろうな

それでも車輪の歳発明なんだけどな。
>>461は初心者が次々新発見しないと講師が馬鹿だと思うらしい馬鹿だが。

作ってみるのはいいんじゃないの？
うまく回すためにはいろんなことを考えないといけないんだし。

BM法なんて大学まで来て教わるまでもなくどっかで見て知ってるだろ。
数式がいるわけでもないから小学生でも実装できる。

スレタイ見てうきうきして来たらずいぶんレベルが低くなってるじゃぁないか．
1はどこいった？

>>235=>>124です。
http://www.hackersdelight.org/ ←この本翻訳出たよ。

>>471
数学板で昔からあばれてる香具師だろ

>>472
ﾏｼﾞｽｶ？
アマゾンでは見つけられなかったよ

http://www.hackersdelight.org/JapaneseHDCover.jpg

http://www.amazon.co.jp/exec/obidos/ASIN/4434046683/
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

ありますた！

> 本物のプログラマはいかにして問題を解くか
FORTRANで

Pascalでなく

>>10 見てマジ！？と思ったけど、
>>12 見て笑った。

やっぱ２ｃｈは２ｃｈだな。

テンプレ

The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition
著:Donald E.Knuth
http://www.amazon.co.jp/exec/obidos/ASIN/475614411X/

The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition
著:Donald E.Knuth
http://www.amazon.co.jp/exec/obidos/ASIN/475614411X/

岩波講座 ソフトウェア科学(3) アルゴリズムとデータ構造
著:石畑 清
http://www.amazon.co.jp/exec/obidos/ASIN/4000103431/

アルゴリズムC・新版―基礎・データ構造・整列・探索
著:Robert Sedgewick
http://www.amazon.co.jp/exec/obidos/ASIN/4764903091/

>>480
クヌース

The Art of Computer Programming, Volumes 1-3 Boxed Set
著:Donald E.Knuth
http://www.amazon.co.jp/exec/obidos/ASIN/0201485419/
バイブル。必読の書。枕。

Algorithms in C++
著:Robert Sedgewick
http://www.amazon.co.jp/exec/obidos/ASIN/020172684X/
そこそこ。

岩波講座 ソフトウェア科学(3) アルゴリズムとデータ構造
著:石畑 清
http://www.amazon.co.jp/exec/obidos/ASIN/4000103431/
日本語の中では良書。

差し替え。補充よろしく。

Knuthは面白いけど、必読とは思いません。
いまやバイブルでもないし。

よいこはセジかコルメン他にしておきましょう。

ご要望にお答えして

Introduction to Algorithms
著:Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
http://www.amazon.co.jp/exec/obidos/ASIN/0262032937/

乙

質問です。重み付きの有向グラフにおいて、最長の一筆書きを得る
アルゴリズムをご存知の方がいらっしゃれば、ご教示ください。よろしく
お願い致します。

最長の一筆書き？

東大の鉄道研究会に聞けや

よくわからないけど一筆書きだったらすべての辺を通るんじゃないの？

全て通るのは辺じゃなくて節だろ

申し訳ありません、「最長の一筆書き」では言葉がおかしいですね。
「重み付きの有向グラフにおいて、《すべての辺を通る必要はなく、
同じ辺は一度しか通ることができない》という前提を満たす経路のうち、
重みの和が最大となるものを求める」という問題です。

プログラムで全パターン試行錯誤してください。

そうですか…お手数をおかけしました。ありがとうございました。

>>491
一筆書きじゃなくてハミルトン閉路といいます。
ハミルトン閉路とか巡回セールスマンでググれば出てくると思います。

>>494
ありがとうございます。調べてみます。

>>486
最長でなくとも死ぬことはない。

>>495
http://www.swa.gr.jp/lop/

たぶんおまいさんのやりたい事の
そのものずばり答えがあるぞ。

もう遅いかもしれないけど。

>>497
ご協力本当に感謝いたします。

ドラゴンブックとかコンパイラの本読んでたんですが、
DAGってどうやって作るんでしょうか。
「閉路のない有行グラフ」
といわれてもさっぱりです。
持ってるどの本も概念的な説明だけで実装については
詳しくされてませんでした。

もうちょっと簡単なサンプルみたいなのが欲しいです。
例えば

d = b + c;
e = b + c;
a = e + d;

とかの式で b + cが共有されるのはわかるのですが、
プログラムとして表現しようとするとどうなるのかが想像つきません。
DAGの作成と、作成したDAGからコードに出力する簡単なサンプルや
アルゴリズムをご存知の方がいらっしゃれば、ご教示ください。

アルゴリズムは本に出てるよな？
要するに、構文木を作る時に一手間掛けるって事だよ

漏れは作った事無いけどｗ

d = b + c
で
　　d
　　↓
　　+
b　　　c

まずこうなるよな
ここまでは問題ないとする
んで、e = b + cについて

　　+
b　　　c
の部分が合同だから

　　d, e
　　↓
　　+
b　　　c
と共有することになる
最後のa = e + dで

　　a
　　↓
　　d, e
　　↓
　　+
b　　　c

になるんじゃないかなあ。
↓矢印が依存関係。
これがDAGか自信ないけど。

あ、間違えた
　　a
　　↓
　　+
d　　　e

と
　　d, e
　　↓
　　+
b　　　c
の２つになる。
aからぶら下がるdとeは同じ木を共有するということになるな。
・・・おれもわからん。

で、この木からコードを生成となると
木を左から辿っていきながらやるんだろう


まず
　　+
b　　　c
から
t1 = b + c
が得られると思う
t1というのは一時記憶とか、そんなやつ
その後は
d = t1
e = t1
となるな

最後に
t2 = d + e
a = t2
となる

まとめると
t1 = b + c
d = t1
e = t1
t2 = d + e
a = t2

こんなもんかな

t1 = b + c を生成した段階で、
この式は共有されてるわけだから、生成フラグみたいなのを用意して
二重に出力しない工夫をする必要がある

>>499
>「閉路のない有行グラフ」
>といわれてもさっぱりです。

下手に "DAG" などとという数学的な言い回しに
囚われるから、抜け出せなくなる。
所詮プログラミングはエンジニアリングなのだから、
その「目的」と「効用」だけに注目すればよい。

c = a[i+4] + b[i+4]

という、よくある配列の例
これはi+4が共有できるのがわかる
配列参照をrefと定義すると

　　c
　　↓
　　+
a　　　 b

　　a, b
　　↓
　　ref
　　↓
　　+
i　　　　4

出力コード
t1 = i + 4
t2 = a ref t1
t3 = b ref t1
c = t2 + t3

副作用とか考えると難しいかもな

巡回セールスマンのオーダーっていくつなんですか？
O(n!)?
O(ｎ＾n)?

>>507
アルゴリズムによる。

総当りだといくつですか？

それぐらい計算せえよ。高校生でも計算できるはず。

総当たりってのは
　全部の経路の長さを計算して一番短いものをみつけるわけで
　全部の経路数はn!　でもさ

じゃ全部の経路をどう探索するのか？　データ構造をどうするのか？

>>511
ノード数が n　なら、辺の数もたかだか n(n-1)
必要メモリ量も O(n^2)

>>499
> 「閉路のない有行グラフ」
> といわれてもさっぱりです。

形式言語と有限オートマトン入門―例題を中心とした情報の離散数学
http://www.amazon.co.jp/exec/obidos/ASIN/4339023396/
離散数学―コンピュータサイエンスの基礎数学 マグロウヒル大学演習
http://www.amazon.co.jp/exec/obidos/ASIN/4274130053/

この辺りを読めば?
独学最初には丁度いい難度だよ。

質問です。
参加者数が変動する大会のトーナメント表を作りたいと考えています。
参加者数が変動するため、シードが一定数出るのですが、できるだけバラバラにシードを割り付けたいと考えています。

例えば以下のように割り付けたいのです。

12345678（試合目）
10000000：15人参加の場合
10001000：14人参加の場合
10101000：13人参加の場合
10101010：12人参加の場合
11101010：11人参加の場合
11101110：10人参加の場合
11111110：　9人参加の場合

（1がシードの試合）

この場合はどのようなアルゴリズムを用いれば良いのでしょうか？

（こちらは計算アルゴリズムに関してのスレッドですが、他に適当なスレッドが見当たりませんでしたのでこちらに書き込ませていただきました。
スレッド違いの場合は誘導願います。）

言ってる意味がわかんね

見たまんまじゃないの？
シード一人目が１、２人目が５‥になるようなプログラムを書くだけ

>>514
//参加者n人の時の(一回戦の)試合数を求める。
int siaisu(int n){
int s=1;
while(s*2<n) s *= 2;
return s;
}

//n回の試合に seed人を配置する。
void haichi(int n, int seed, char *siai){
int ss, nn;
if(seed <= 0) return;
if(n == 1) {*siai = '1'; return;}
ss = seed/2; nn = (n+1)/2;
haichi(nn, seed-ss, siai);
haichi(n-nn, ss, siai+nn);
return;
}

続く

main(){
int game, seed, sanka, i;
char siai[99];
//(テスト)参加者1人〜20人の場合を計算する。
for(sanka=1; sanka<=20; sanka++){
game=siaisu(sanka); //試合数
seed=game * 2 - sanka; //seed人数
for(i=0; i<game; i++) siai[i]='0'; //配置テーブル初期化
siai[i]='\0';

haichi(game, seed, siai); //配置を求める
printf("%2d,%2d,%2d, %s\n", sanka, game, seed, siai); //結果表示
}
}

実行結果。左から、参加者数、(一回戦の)試合数、seed数、配置。

1, 1, 1, 1
2, 1, 0, 0
3, 2, 1, 10
4, 2, 0, 00
5, 4, 3, 1110
6, 4, 2, 1010
7, 4, 1, 1000
8, 4, 0, 0000
9, 8, 7, 11111110
10, 8, 6, 11101110
11, 8, 5, 11101010
12, 8, 4, 10101010
13, 8, 3, 10101000
14, 8, 2, 10001000
15, 8, 1, 10000000
16, 8, 0, 00000000
17,16,15, 1111111111111110
18,16,14, 1111111011111110
19,16,13, 1111111011101110
20,16,12, 1110111011101110

>>519
参加者が一人の時も、試合をやるのか？

自明な試合

>>514
微妙に仕様を読み間違った。コメントが変なところあるけど、
プログラムはこのままで大丈夫だと思う。

>>520
決勝戦が不戦勝ということでお許しを。

シード選手の場所、BYEの場所、試合順序は各競技団体のルールで定義されていたりする。
その辺りは大丈夫なんだろうか。

六角形の敷き詰められたマップの距離を計算したいんですが
何かいい参考サイトはありますか？

ランダムに並んでいる要素があるときに、昇順で最長の組み合わせを求めたいと思っているのですが、いいアイデアが浮かびません。

例えば

1 8 9 10 3 4 2 5 6

という要素がある場合には

1 8 9 10
1 3 4 5 6
1 2 5 6

という組み合わせが考えられますが、この中の

1 3 4 5 6

を容易に求める方法はないでしょうか？
連続する部分を１ブロックとして全ての組み合わせを求める方法は思いついたのですが、これだと要素数が100とかの場合にはものすごく遅くなってしまいます。

いいアルゴリズムをご存知の方は教えてください。

>>525
ナップサック問題に帰着。
NP完全です。

>>526
そうなのですか．．．
諦めることにします。
どうもありがとうございました。

>>526
おいおい、適当なことをいうなよ。

あっさり騙される方もどうかしてるけどな。もともとやる気ナシと見た。

>>528
正解は何？

計算量についてなら、O(n^2)。

O(n!) かと思った・・・

で、いいアルゴリズムはないの？

O(n^2)のアルゴリズム。

長さだけなら下のプログラムで簡単に見つけれます。

#define N 100

int data[N];
int length[N+1];

int search(void)
{
　　int i, len, longest = 0;

　　for (i = N-1; i >= 0; i--) {
　　　　for (len = longest; len > 0 && length[len] <= data[i]; len--)
　　　　　　;
　　　　if (++len > longest) {
　　　　　　longest = len;
　　　　　　length[len] = data[i];
　　　　}
　　　　else if (length[len] < data[i])
　　　　　　length[len] = data[i];
　　}
　　return longest;
}

ヒントとしては、先頭からi番目までの要素を見た場合の最長系列は
i-1番目までの結果を元に求まる。

もうちょっというと、その最長系列はi番目の要素a_iを含むものであるか
含まないものであるかのどちらかである(当たり前)。
含むならば、i-1番目までにおいてa_i未満のものしか持たない系列で最長のものに
a_iを追加したものである。
含まない場合の最長系列は、i-1番目までの最長系列である。

つまりi番目の要素をみたとき、最長系列の候補はi個しかない。
だから計算量としては 1+2+3+...+n = n(n-1)/2 → O(n^2)。

マージソート風の分割統治で O(n・log n) になるのかな。

>>537
おいおい、適当なことをいうなよ。

また適当かよ。

ところで「適当」って２通りの解釈があるよな。
文脈でも判断できない場合がある。
ここが日本語解析の困難な所でもある。

>>536の補足と改善。

計算量は >>536 で述べた長さiの最長系列候補をi個つくるための計算量の他に
a_iを含む最長系列を作る計算量があって、共にO(n^2)だ。

ところが考えてみると、a_iを含まない最長系列候補を毎回律儀に延長せずともよく、
そうすると計算が必要なのは実は後者の処理だけだ。
後者の処理ではi個の候補の中から最大値 < a_iで長さ最長のものを選ぶわけだが、
最長系列候補を常にソートした状態で持っておけばこの計算量を減らせる。

具体的には、最長系列候補を単にリストや配列で持つのではなしに
系列長でソートして持ち、さらにその中で最大値でソートするようにする。
これにRed-Blackツリーを使えば一回のオーダーはほぼO(log n)にできる。

こうして計算量はO(n log n)となる。

問題が、np完全かそうじゃないかを判断できるのは経験？
それとも何か判断基準があるもんなの？

>>541
適当です

>>541
ある証明済みのNP完全問題に多項式時間で帰着するという証明をすればよい。
あるいはもっと直接的な証明

>>541
計算論とかTuringMachineとか勉強し直せ。

531って、計算量とかオーダーの記号とかはきちんと使ってるのに、
アルゴリズムの入門のコースは取ったことないの？
やったことがあれば一目瞭然のすげー有名な問題なんだが。
宿題とか試験にも良く出るよね、これ。

誰か中学生でも理解できそうな割り算のアルゴリズム教えてください。

>546
引き算を繰り返す

>>545
> アルゴリズムの入門のコースは取ったことないの？

ないんですよ。この問題も恥ずかしながら未見です。
よろしければ適当なw 資料(英文可、web上のURL希望)のポインタを頂けまいか。

ついでに540の方針で実装した例を貼っておきます。至らぬ点があれば指摘願いたい。
なお系列長が同じものでは最大値が最小のもののみを持てばいいことに気付いたので
そのように修正しています。
Ruby 1.8.2とRuby/RBTree(http://www.geocities.co.jp/SiliconValley-PaloAlto/3388/rbtree/README.html)を使用。
require 'rbtree'

class Sequence
　　def initialize(prev, max)
　　　　@prev = prev
　　　　@len = prev ? prev.len + 1 : 1
　　　　@max = max
　　end
　　attr_reader :prev, :len, :max

　　def result()
　　　　r = []
　　　　seq = self
　　　　while seq
　　　　　　r << seq.max
　　　　　　seq = seq.prev
　　　　end
　　　　r.reverse
　　end
end

def longest_seq_with(sequences, x)
　　sequences.reverse_each { |len,seq|
　　　　return Sequence.new(seq,x) if seq.max < x
　　}
　　Sequence.new(nil, x)
end

def find_longest(ary)
　　sequences = RBTree.new # lenをキーとするRBTree (Integer->Sequence)
　　ary.each { |x|
　　　　seq = longest_seq_with(sequences, x)
　　　　s = sequences[seq.len]
　　　　sequences[seq.len] = seq unless s and s.max <= seq.max
　　}
　　sequences.last[1].result
end

系列長が同じものでは最大値が最小のもののみを持てばいい点を押し進めると、
RBTreeの必要はまったくなくなっていることに気付きました。

class Sequence
　　def initialize(prev, max)
　　　　@prev = prev
　　　　@max = max
　　end
　　attr_reader :prev, :max

　　def result()
　　　　# 省略
　　end
end

def find_longest(ary)
　　sequences = Array.new(ary.length+1)
　　maxlen = 0
　　ary.each { |x|
　　　　j = maxlen
　　　　j -= 1 while j > 0 and sequences[j] and sequences[j].max >= x
　　　　len = j+1
　　　　maxlen = len if maxlen < len
　　　　s = sequences[len]
　　　　next if s and s.max < x
　　　　sequences[len] = Sequence.new(sequences[j], x)
　　}
　　sequences[maxlen].result
end

数学系の人？
食えなくなったら是非プログラマに
物足りないかもしれないけどｗ

>>525
再帰を使え。

あと、最長の組み合わせが見つからなくとも死にはしない。

え、俺は氏ねって言うけど？

漏れも初見だけどこれってO(n)じゃない?
一番長いのと二番目に長いリストのペアを返す関数。

(define (search l)
  (if (null? l) '(() . ())
    (let ((a (search (cdr l))))
      (cond ((null? (car a)) (cons (list (car l)) '()))
            ((< (car l) (car (car a))) (cons (cons (car l) (car a)) (car a)))
            ((null? (cdr a)) a)
            ((< (car l) (car (cdr a))) (cons (cons (car l) (cdr a)) (cdr a)))
            ((null? (cdr (cdr a))) a)
            ((< (car l) (cadr (cdr a))) (cons (car a) (cons (car l) (cdr (cdr a)))))
            (else a)))))

ごめん上の間違ってた。
最悪の場合(すでに昇順の場合) O(2^n)になりそうだけど、こんなのとか。

(define (search n l)
  (cond ((null? l) (cons 0 '()))
        ((< (car l) n) (search n (cdr l)))
        (else
          (let ((a (search (car l) (cdr l))) (b (search n (cdr l))))
            (if (>= (car a) (car b)) (cons (+ (car a) 1) (cons (car l) (cdr a)))
                b)))))

>>555
やっぱこういうアルゴリズムはLISP系だなあ。
とか思って試してみたけど

>(search 0 '(1 8 9 10 3 4 2 5 6))
=>(5 1 3 4 5 6)

頭の5は何？

あ、五個ってことか。
さすがｗ

今度は大丈夫だと思います。updateは可読性のため末尾再帰にしてません。
それぞれの長さのリストを返します。たぶん 535と同じアルゴリズムだと思います。
550 は計算量 O(nlogn)なんでしょうか？

(define (update a ll)
  (cond ((null? (cadr ll)) (if (> a (car (car ll))) (cons (cons a '()) '(())) ll))
        ((<= a (car (cadr ll))) (cons (cons a (cadr ll)) (cdr ll)))
        (else (cons (car ll) (update a (cdr ll))))))

(define (search6 l)
  (cond ((null? l) '(()))
        ((null? (cdr l)) (cons (cons (car l) '()) '(())))
        (else
          (let ((ll (search6 (cdr l))))
            (let ((r (update (car l) (cons '() ll))))
              (if (null? (car r)) (cdr r) r))))))

>>558
> 550 は計算量 O(nlogn)なんでしょうか？
550はn^2でしょ。あなたのもn^2。

updateの中のifが要らなくて、それにともなって search6の二番目の cond節も要らないです。

>>559
O(nlogn)にするのは無理なんですかね？
分割統治法も使えそうにないし。

1. リストに最初から順番に番号を付けるのにO(n)
2. 値1>値2 && 番号1>番号2 でソートするのにO(nlogn)
3. 値1>値2 && 番号1>番号2 で連続になっている(安定なソートなら値の比較だけでいい?)最長の領域を捜すのにO(n)

でO(nlogn)でできるのかな?

ocamlで書いたらもっとすっきりしちゃった。見たい？

別に。
そろそろ別の話題よろ。

話題が無いから引っ張ってるのに。ひどいわ。

じゃ、ハノイの塔を解くアルゴリズムを1tapeTMで定義してよー

Cプリプロセッサで解くやつならあるけどなー

>>565
結構でかくなった
レスにすると7，8レスくらい
出題者として責任もって合ってるかどうか確認しろよ

>>565
viで表示しながら解く奴があったな。

emacsじゃないの?

>>568
emacs -f hanoi

http://www.kernelthread.com/hanoi/
100個以上の言語で書かれたハノイの塔を解くプログラム集。
良くこれだけの言語で書いたものだ。すごいね。

くだらん。ばかじゃねーの。

>>572
なんでよー
夢がないこといわないでよー　にゃんにゃん

ごめん。いいすぎた。

ローパスフィルターのアルゴリズムについて教えてください

フーリエ変換して
周波数成分の中から
高周波領域部分の係数をカットして
逆フーリエ変換する

RとCを適当に入れた回路を作って、微分方程式を解く

振幅特性と位相特性の離散的なリストを用意して、そいつを逆フーリエ変換したやつで畳み込みをかける。

>>575
ここで大原ゆきが解答しているぞ。
http://pc5.2ch.net/test/read.cgi/tech/1091054082/

>>575
バターワースフィルタ とか チェビシェフフィルタ とか 楕円フィルタ でぐぐれ。

0からある数値（例として3とします）までの間の組合せを列挙する
アルゴリズムでいいのありましたら教えてください。。
（キーワードだけでも。。）

例の場合：
0
1
2
3
01
02
03
12
13
23
012
013
023
123

>581
三進数、繰り上がり、ビット演算、ぉっぱぉ

>>581
n個の数字があるから x を1〜(2^n-2)までループさせる。
その x においてビット0が1ならば'0'、ビット1が１ならば'1'・・・ビット(n-1)が1ならば'n-1'を
表示する。

で、どうですかね？

>>582
>>583
ありがとうございます。1から順にn進数に変換して・・・ってやろうと
してたんですけど、ビット演算でやったほうがスマートそうですね。
どうもです。

http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec9-1.html
ここにあるような方法にならって、動的計画法を用いてナップザック問題を解きたいんですが、
一般的なナップザック問題は、品物A,B,Cがあった時にカバンにAを3つBを2つといった感じで
同じ品物を複数詰め込むことができますよね。じゃなくて、カバンに同じ
品物を複数詰めることができないような場合を取り扱いたいんですが、
どういう風に実装すればいいでしょうか？

カバンに同じ品物を複数詰めることができないように実装すればいいでしょう？

>>585
ナップザック問題はNP完全だから、要素が多くなると、厳密解は求まらないよ。
近似解を求めるのに、遺伝的アルゴリズムでも使えば？

>>586
いや厳密解求めるならそれでもいいかもしれないけど、
動的計画法の中に埋め込む制約としては厳しいんじゃないの?

>>587
NP問題だって厳密解は求まるだろ。計算量がすごくなるというだけで。

>>589
NP問題というか、さらにNP完全だし。
厳密解は、理論的には求まるが、計算時間が現実的ではないから、彼は計算途中で
計算機を止めてしまうだろうという推定が入っている。

>>588
> 動的計画法の中に埋め込む制約としては厳しいんじゃないの?
厳しいも何も、NP完全として知られるのは0-1ナップザック問題と言って正に
>>586の言っている形なのだが。

計算途中で息絶えてしまうだろう

NP完全ではあるものの、実際には品物1万個でも0.1秒以内で解けてたりする。

行列のexpはどうやって計算しますか？

>>594
1. 普通に Σ(1/n!)A^n を逐次計算
2. 対角化 → 固有値の exp を使って求める

awe

C言語での除法のアルゴリズムを教えてください

>>597
除法という演算の定義を与えてもらわないと

>>597
a / b;

>>598
商と余りを導出するものです。

整数x,yについて、y=ax+b　(a,bは非負整数で、0≦b<|x|)
ときのaを商、bを余りとして、(a,b)を導出する演算をx/y
(除法)とします。
これでお願いします。

>>600
正直>>599で正解で終わりと言いたいところだが、それを聞きたいわけ
じゃないだろう？エスパーしてみるが…

1. 「C言語で割り算をする場合、中の人はどんな処理をしているのか？」
　⇒コンパイラを通した後の機械語によってCPUに依存。
2. 「C言語で'/'を使わずに割り算を実装するにはどうしたらいいのか？」
　⇒解1:定義通りに引き算を繰り返す。(比較的小さな数の場合)
　⇒解2:割る数の逆数をニュートン法で求めて乗算を行う。(数万桁以上
　　　　　など、大きな数の場合)

>>600
これでどう？
void mod(int x, int y, int* a, int* b)
{
　if (y < x) { *a = 0; *b = y; return; }
　mod(x*2, y, a, b);
　*a *= 2;
　if (b >= x) { (*a)++: b -= x;}
}

2進数の割り算を自分で筆算でやれるか？
やれるなら、シフト演算と引き算と足し算でなんとでもなる。

重ね重ねすいません。
二進数の除法のアルゴリズムが知りたいのです。
｢/｣は10進数演算子だから、二進数の除法はこれではダメだと
きいたので…

ちょっと前どっかのスレで同じ様な質問した奴と同一人物かな
C言語スレだったか忘れたけど

>>604
2進数だったら & 取ればいいだけじゃないの？

> ｢/｣は10進数演算子だから
誰だよ、そんなこと言うやつ

>>604
整数の除算に10進も2進もねえよ。
中学レベルから数学をおさらいした方が身につくんじゃない?

でた、２ｃｈお決まりの煽り文句ｗ
どうせなら小学校からやり直したいです

お決まりっていうか、N進数だとかって中学あたりでやるだろ?
整数除算が基数ごとに異なるとか思ってるのはかなり重症だと思うが。

中学ではやらない

私立ならやるだろう。

1101101010111101010 / 10 = 110110101011110101

>>604
四則演算だけでやるコードが見たいという事？
なら、ここの除算の所にある
http://www.tensyo.com/urame/prog/ALGO.HTM

でも、最近のCPUは殆ど除算命令を持っているよ。
そのアルゴリズムはこれと似た方法のものもあるけど（その場合は遅い）
もっと高速のものもあったり
高速な掛算命令を持ってる機種では、
最初の数桁が出てきて、あとはニュートン法で計算させたりと色々だよ

>>613
＞四則演算だけで
は?

>>613
> でも、最近のCPUは殆ど除算命令を持っているよ。
Z80を思い出した…

>>614
ゴメン。　四則だと掛け算割り算を含んでるね。
足し算引き算と、左右シフトだけの事ね

漏れが >>602 で既に答えてるのに皆さん華麗にスルーですか。
バグでもあるのかな。

>>609
> N進数だとかって中学あたりでやるだろ?

爺ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!

初期のsparcは除算命令が複数に分かれていたね。

3
6
12
20
30

という数値配列があって、例えば「７」って入力されると「７は添え字番号１と２の間にある」
っていう風に検出する一番最適な方法を教えてください。

>>619
バイナリサーチ。
http://www.google.co.jp/search?hl=ja&q=%E3%83%90%E3%82%A4%E3%83%8A%E3%83%AA%E3%82%B5%E3%83%BC%E3%83%81&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=

お前ら難しい話するな。

>>619
ヘボソース

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5

int main(void)
{
int line[SIZE] = {3, 6, 10, 20, 30};
int i, num;
char str[BUFSIZ];

puts("数値を入力してください");
if(fgets(str, sizeof(str), stdin) == NULL) exit(1);
if(sscanf(str, "%d", &num) != 1) exit(1);

for(i=0; i<SIZE; i++)
{
if(line[i] > num)
{printf("%dは、添え字番号%dと%dの間にある\n", num, i-1, i); break;}
else if(line[i] == num)
{printf("%dは、添え字番号%dの値と等しい\n", num, i); break;}
}

return 0;
}

>>622
それスレタイに全然合ってないよ！

>>617
突込み所が無い程完璧なソース出すと誰もコメント出来ないからスルーになる。

2ch住人……なんて性格悪いんだ…

いやこことプログラマー板の住人が性格悪いの多い気がする

ヲタが多いからさ
ヲタの価値基準は「知ってる奴は偉い」だからな
すぐ聞いても無いのに説明はじめたりするだろ

と、「オレはオマエラとは違う」と思っている人がおっしゃっています

人の説明が少しばかり偉そうでもそこは我慢したらどうですか？
そういうことを指摘すると荒れる原因になりますし…
注意するにしてももっと思慮のある言い方にすべきと思います。
人に説明しようとしている人に悪意があるとは考え辛いです。
それよりもその人に対し自慢げだ、ヲタだなどと意味のない叩き
書き込みをするほうがよっぽど質が悪いし、無駄な書き込みでは
ありませんか？

すみません、ここに書き込むべきでない低レベルな質問をしてしまいました。
大変失礼ですが質問を取り下げさせてください。

フレッシュマンに送る言葉
聞きやすい人は知らない。
聞きにくい人が知っている。

>>631
おお、なかなか含蓄のある言葉だな。

>>630 == >>600 == >>597
おまえここで質問してた香具師か？
http://pc5.2ch.net/test/read.cgi/tech/1106406806/344-347
http://pc5.2ch.net/test/read.cgi/tech/1106650397/891-892

>>597 >>600 のような聞き方では何言ってるのか分からんかったぞ。

最初から多倍長計算のアルゴリズムの話だと書けば
ここで答えてくれた人もかなりいただろうに。

>633
わかりにくい質問をしてしまった上に、何度も聞きなおすのもどうかと思い、
一度質問を取り下げて他スレで聞き直すことにしたのです。もし気分を悪く
されたのなら誤ります。申し訳ありません。

>>634
質問取り下げなくても素直にあやまったら
みんな答えてくれると思うよ

そうか？
宿題丸投げすんなとか、スレ違いとか、
筆算もできんのかとか、煽られて終わりそう

一応多倍長計算の専門スレがあるらしいのだけれども。
C++の機能だけで多倍長計算を考えるスレ
http://pc5.2ch.net/test/read.cgi/tech/1033797624/

>>637
どう見てもネタスレにしか見えないんだが

やっぱサザンは神だな

>>637
多倍長計算は
openssl/bn.h
を使え。

√の計算はニュートン法でできるのは当然だけど、
CALCなどでやるとニュートン法よりもずっと計算が速い。
その計算方法は誰かが知っている、あるいは過去に知っている人が居たはずなんだけど、
計算の高速化の技術が今ひとつ身に付かない。
こういうのはどういう分野の研究者がやるんだろう？
さて、次から選択。
プロに任せる。
何とかして計算の高速化の技術を習得する。
量子コンピュータの発明。

ﾄｳｼﾂｸｻｲｿﾞ

「プロに任せる」。具体的に言うと「既存のコードを利用する」。

平方根を計算するハードに任せる。

>>641
√はニュートン法でやるより、より単純で誰でも思いつく二分法が速いだろ。
二進法だから、二分法のネックである試行錯誤に時間を取られない。実質的に筆算による
平方根を求める手法の二進法版だ。

SINやCOSなどの初等関数は、STL法が速い。これは、SINやCOSを加減と2倍や1/2倍など
のコンピュータが無茶得意とする演算（数表との加減とビットシフト）だけに限定して、高速化
をはかったものだ。
SINなら引数の範囲を-π/2〜π/2に限定できれば、小数の乗算1回程度の速度でSINを
計算できてしまう。つまり、元々の引数を２πで割って余りをだし、さらにその範囲を考えて
SINやCOSどちらに引き渡し結果の符号を変えるか判断する…こっちの時間の方が、関数
計算の核心部分より遅いわけだ。

SSEに4ついっぺんにsqrtを計算できる機能があるけど
それより速く出来るの?

>>646
それは無理。√もSINもCOSもLOGも、>>645に書いたような練りに練られたアルゴリズムがまずあって、
それをハードで実現したのだろう。だから、当然同じ精度ならハードでやっちゃう方が速い。

ただ、多倍長精度演算をやろうとして、ごりごりアセンブラなどで記述するような場合なら、上記の方法は
当然有効だろう。ハードで計算できる精度以上の数値を求めようとするなら、ソフトで計算するしかない
わけだしね。

2分法は、1回のループで1ビット精度が増える
ニュートン法は、1回のループで桁数が２倍になる

ある程度の精度を必要とするとニュートン法の方が当然良い。
ただ、平方根の場合、32ビット整数の平方根は16ビットに収まるわけで、
整数に限るような事をすればループ内が単純な2分法が速いという結果にもなる。

100迄の整数平方根なんてのに限れば
1+3+5+7+...
奇数列を加算してオーバーするかどうかの方が速いだろうしね

>>645
そういうのHacker's Delightに山ほど載ってるよ。

>>647
ありがとう。
物理シミュでルートの計算を膨大に使用するつもりだったから
SSEかそれ以外のものを使うか迷ってたんですよ。

物理で平方は大量に出るだけろうけど平方根は出る？
距離なら√（x^2+y^2+z^2)だろうし

平方根出てるじゃん。

>>648
普通の浮動小数点実数の場合は、コンピュータ内部で

ａ×２＾ｂ　　のような形になっているわけだ。ここで仮にｂが奇数なら
２ａ×２＾（ｂ−１）　のような形にするとして…√を求めるには…

√（ａ×２＾ｂ）＝√ａ×２＾（ｂ／２）

となるから、結局問題になるのは√ａの部分だ。
この部分は固定小数点と考えることができるので、結局整数と同じ手法で
√を求めることができる。

要するに、浮動小数点の場合にもニュートン法より二分法の方が速い。

>>653 見て思ったんだけどさ。

単精度だと仮数部(23bit)の組み合わせは2^23=8388608しかないじゃん。
これの√を全部テーブルにしても、2^23 * 23(bit) / 8 = 24,117,248(bytes)。
あと数年したら、テーブルによる実装も現実になったりしないかな。

メモリにアクセスするより、内部でまわした方が速そうだ。

>>652
距離は、たとえば引力なら距離の2乗に反比例するので、
平方根を出す必要は普通は無い筈。

たとえば、一定の距離に近づいたら　というような条件でも、やっぱり2乗した状態で比較すればいいんだし

>>656
いや、その程度の簡略化したとしても
そういうシーン以外で多用するんだけど。

STLとかCORDICを使っていたのは
乗算もマイクロプログラムの時代
乗算がハードワイヤドロジックの今時は
マイクロプログラムのSTLやCORDICより
近似式のほうが速いのは常識だ

>>655
実際、8ビット程度の荒い結果がテーブルで出てくる命令を持ってたりするチップはあるね。
残りはニュートン法一発で精度が２倍になってゆくから。


>>655
√(x)= √(1-y) =1- 1/2*y -1/8*y^2 - 1/16*y^3 - 5/128*y^3 　出：http://www.tensyo.com/urame/prog/ALGO.HTM

だから、超並列化がすすめば、多項式近似の方が早くなる可能性もあるかもね。
ニュートン法やバイナリ-法はループが必要だから。

>>657
俺は物理計算で距離が実際に必要になるケースというのが実在するというのは疑問だけど

キミが実際に必要だというなら、そうなんだろう。

でも、出来ればどういう計算に必要なのか知りたい希望はある。

>>658
というか…SINやLOGなどの初等関数は全てＦＰＵ内部で演算できるから、
わざわざプログラムで最速を求める意義は、高精度の数値を求めたりする
場合だろ。その場合には乗除もアセンブラ等でプログラムしなきゃならなく
なるから当然ＳＴＬの出番がまわってくるわな。

多倍長なら桁数によってある程度桁数が増えれば、
乗算はアセンブラでカリカリに書くより素直にFFT方式にした方が早くなるよ。

そこらへんになると精度のコントロールが難しいからSTL作る方が難しいんじゃない？

>>662
ＦＦＴってフーリエ級数にするの？それよりなら単純にマクローニン展開やテイラー展開の方がいいだろ。
多倍長でも桁数が変動するやつなら、それらの級数展開に頼るしかないだろうね。
桁数が固定されてて、多倍長演算が高速で求められているなら、ＳＴＬでいいだろ。演算に求められる
テーブルを計算するのは単純に桁数少ない奴のアルゴリズムを流用すれば良いだけ。

>>663
えと、掛け算を　FFTでした方が　と書いてるのですが？

中国剰余定理だと、それこそ桁数が変動するのに耐えられないと思いますし・・・・

マク浪人

>>664
すまん…どうやったら、乗法をＦＦＴでより速く計算できるんだ？わからんｗ
ははー降参しますｗ！
参考になるＵＲＬなどあったら教えて欲しい。

つまり、多倍長演算で、基本演算の四則演算中

足算引算はN　のオーダで出来ますが、
掛け算は筆算方式だとN^2となります。これは分割統治法を使えば緩和しますが
FFT方式ならN*log(N) で可能となります。

この板にも、昔、素数スレでFFTで掛け算を大幅に高速化したコードが実際にあったのですが・・・
と、検索したらありました。
http://pc.2ch.net/tech/kako/993/993457354.html

>>667
なるほど…
http://homepage2.nifty.com/m_kamada/docs/fftmul.htm
↑とかね。

そいやオレ、「電脳倶楽部」とってたから以前これ目にしたことあったはず…
すっかりわすれてた。

うわ、ロッパーユーザーかよ。
ところでルートの逆数を求めるのに、

inline float rsqrtf(float v){
float v_half = v * 0.5f;
int i = *(int *) &v;
i = 0x5f3759df - (i >> 1);
v = *(float *) &i;
return v * (1.5f - v_half * v * v);
}

なんてのがあるんだな。精度は低いけど。

>>660
>でも、出来ればどういう計算に必要なのか知りたい希望はある。

657じゃないけど、
http://homepage1.nifty.com/kaneko/wire.htm
↑。ワイヤーをバネモデルで動かしてるけどそこで使う計算で
距離を求めている。バネモデルを距離で計算しなくて済むように
出来るの？

>>670
バネだから、力は近似的に距離 L に比例するから、平方根が必要という事だね。
それなら必要じゃないの？ 　

ただ、そのプログラムだと
　　　double dis = sqrt(dx * dx + dy * dy);
　　　double d = (10 - dis) * 0.2;
　　　px[i] -= dx / dis * d;

て部分は、何か適当な計算をしてるだけのように見えるんだけど・・・・・2乗のままでもそれなりに動くんじゃない？

ようするに物理計算じゃなくて、長さＬが１０に近づくように
その部分の長さを　 １-　((10 - L) * 0.2)/L*2　倍してるだけみたいだよ。

だから １-　((10 - L) * 0.2)/10＊２　でも似た感じになるだろうし
　（L+dL)^2= L^2 *2*dL+dL^2 だから
そこを １-　((100 - L^2) * 0.1)/100＊２　でもいけるんじゃない？

で、ホントの物理計算としてのバネの場合も、
力が比例するのは　Ｌ　じゃなくて　Ｌ＋ｄＬのｄＬの　微少な部分に比例するのだから

Ｌ^2のまま使っても、
（L+dL)^2= L^2 *2*dL+dL^2　と、ｄＬ^2は十分小さいから無視して、2*ｄＬの効果として使えるから

やっぱり平方根は必要ないと思うよ。

×　L^2 *2*dL+dL^2
○　L^2 +2*dL+dL^2

ね。　


どうしても、平方根が必要な事があっても、こんな感じのＤＤＡ処理をするなら、
微少差の場合はニュートン法的な逐次演算に変換する事も一つの方法だしね

>>670
47氏じゃないか。
あのひとはほんといろいろ作ってるな。

>>673
あのページからソースを落としてVC6で動かしたんだけど、
// ワイヤp[i]とp[i+1]間の距離は常にdr
for (i = 0; i < PMAX - 1; i++) {
static CVector3 dp;
dp = p[i + 1] - p[i];
double dis = dp.abs();
double d = (dr - dis) * 0.2;
p[i] -= dp / dis * d;
p[i + 1] += dp / dis * d;
}
この部分をどう変えたらいいんですか？
実際やってみるので改変後のソースを示して欲しいんだけど。
本当に平方根なしで動きに問題が出ないのか確認したいので。

>>656
> >>652
> 距離は、たとえば引力なら距離の2乗に反比例するので、
> 平方根を出す必要は普通は無い筈。

引力でも、そのベクトルを出そうと思ったら平方根がいるのでは？
まあ、惑星のシミュレーションなんかで使われるハミルトン系専用の
数値計算法ではいらなくなるのかも。

>>676
試すだけなら

{
double dr2 = dr*dr;
for (i = 0; i < PMAX - 1; i++) {
static CVector3 dp;
dp = p[i + 1] - p[i];
double dis = dp.abs();
double d2 = dis*dis;

double d = (dr2 - d2) * 0.2/2 / dr2;
p[i] -= dp * d;
p[i + 1] += dp * d;
}

}

ごめん。　こうしてみて。

{
　double dr2 = dr*dr;
　　for (i = 0; i < PMAX - 1; i++) {
　　　static CVector3 dp;
　　　dp = p[i + 1] - p[i];
　　　double d2 = dp.abs2();
　　　double d = (dr2 - d2) * 0.2/2 / d2;
　　　p[i] -= dp * d;
　　　p[i + 1] += dp * d;
　　}

}
abs2というのが、2乗和の事みたい。

おお、ちゃんと動いてますよー！
バネモデルはいろんなところで使ってたからこれで高速化が
期待できそうです。
本当に平方根がいらなくなるとは恐れ入りました。

>>673
ん？
（L+dL)^2= L^2 *2*dL+dL^2　　　　　　　　　　　　じゃなく…
（L+dL)^2= L^2 *2*dL・L+dL^2　

だし…　やはり平方根ひつようなんじゃ…

>>681
(L+dL)^2= L^2 *2*dL+dL^2　　　　　　　　　　　　じゃなく…
(L+dL)^2= L^2 +2*dL･L+dL^2　

なんじゃ…

>>680
そりゃ動くとは思うが…精度的に問題出てこないのかあ？

確かに。実際に平方根の元のアルゴリズムと>>679のアルゴリズムで
誤差を見て見たらかなり誤差が大きかった。
理想を言えば平方根のバージョンと近い値を期待したいところだけど
ここまで誤差があるなら別の手法として割り切って使えばいいのかなぁ。
例えばワイヤーとして破綻のない動きであるならコレでもいいって感じ。

>>683
もともと、物理計算じゃなくて、偏差に比例するような速度で戻るという仕掛けで動かしてるだけだから
最初から物理計算からは精度外れまくりでは？

よ〜し、パパ、マジメに変換しちゃうぞ。

>>676
double d = (dr - dis) * 0.2;
p[i] -= dp / dis * d; ⇒　　e = (dr - dis)/dis *0.2 とすれば 　　p[i] -= dp *e; と置き換えられる

dr^2-dis^2 =(dr+dis)*(dr-dis) 　だから

e = (dr - dis)/dis *0.2　=　(dr^2-dis^2)/ ( (dr+dis)*dis)　*0.2 = (dr^2-dis^2)/ ( dr*dis + dis*dis)　*0.2
ここまでは誤差のない変換だ。

で、drとdis は、そもそもdisをdrに近づける為なんでループの結果同じ値に近づく筈
だから同じとみなして dr*dis ≒ dis*dis 　とすると >>679に化けるわけだ。

誤差の部分はここにあるけど、そもそもの計算方法がマジメな計算じゃないから、似た結果になりゃいいじゃんてことだな。

という事で、少しだけ元の値に近づけるなら
dr*dis + dis*dis と　2*dis^2 の比率を (dr^2-dis^2)/dr^2　から補正してやればいい。
単純な1次の線形近似　>>659 から



double dr2 = dr*dr;
for (i = 0; i < PMAX - 1; i++) {
static CVector3 dp;
dp = p[i + 1] - p[i];
double d2 = dp.abs2();
double e2 = (dr2-d2);
double e = 0.2*e2/(d2*(2 -e2/dr2*0.4 ));//　<--- 0.3〜0.5の範囲で適当に
p[i] -= dp * e;
p[i + 1] += dp * e;
}

使ってる環境によっては、平方根どころか除算でさえネックになるから
似た結果でいいなら、どんどん変換しちゃうわけね。

さらに昔は、掛算さえ嫌って、変数追加してＤＤＡ方式でゴチャゴチャやったよな

スマン、符号を間違っていた。
ところが、符号を正しくすると、異常な領域に飛んでいってしまうと逆に精度が悪くなる。
といって、途中に判断が必要になるのも、あんまり好ましくない。
で、誤魔化す方法を考えた結果、近似計算として

for (i = 0; i < PMAX - 1; i++) {
static CVector3 dp;
dp = p[i + 1] - p[i];
double d2 = dp.abs2();
double e2 = (dr2-d2);

double e;
// if(e2>0) e = 0.2*e2/(d2*(2 + e2/dr2*0.4 ));
// else e = 0.2*e2/(d2*(2 + e2/d2 *0.4 ));
e = 0.2*e2/(d2*(2 + e2/(d2+dr2)));
p[i] -= dp * e;
p[i + 1] += dp * e;
}

どれくらい誤差が小さくなるかだけど
dis/dr = 1.1 の時　4.7 ％　⇒　 -0.2%
dis/dr = 10 の時　 82 ％　⇒　 -0.8%

dis/dr = 0.9 の時　-5 ％　⇒　 0.3%
dis/dr = 0.3 の時　-51 ％　⇒　 -34%
dis/dr = 0.1 の時　-81 ％　⇒　 -72%

disが極端に小さい方にはあんまり効果ないね。
やっぱり、小さい方には別の近似関数を用意する必要がありそう

小さい方に精度を上げるには
if(e2>0) e = 0.2*e2/(d2*(2 +0.50 * e2/(d2+dr )));//disが小さい
else e = 0.2*e2/(d2*(2 +0.93 * e2/(d2+dr2)));//disが大きい

のようにすれば緩和出来るけど、
ただ、どうしても、disが小さくなるほど、誤差は-100%に近づいてしまう。

誤差100％というと大きいようだけど、ようは2倍という事、

それと、disが小さいと逆数で効くので、そもそもeが１以上になってしまう。
そんな条件だと本来の物理計算としてメチャクチャな所にあるんで、
>>689あたりの近似で十分じゃないかな

あと、>>678がダメで　>>679がＯＫなのも、結構面白い。

この計算式が本当のバネを計算してるなら、いつまでも振動は収まらない筈。
なのに、適当に振動が収まるのは、このチョットとした工夫が抵抗項として
働いてるんだろうね。

>>688
似た結果というのは、ちょっと違うかな。

ＤＤＡを使えば、一般的に微少な2次の項を省略しても、必要なだけ細分化すれば誤差は必要なだけ抑え込める。

たとえば
　a+b*dx+c*dx^2
てな感じだと、
処理分解数を２倍にすれば　dxは半分になる。
　 dxが1/2になれば dx^2は 1/4になる。

だから2次以上の項目は必要なだけ小さく出来る。

>>692

工夫というより、巧夫だね

>double d = (dr - dis) * 0.2;

この0.2を適当と呼んでるけど物理の本でフックの法則をみてると
上の式が出てきて0.2の部分はバネ係数として定義されてます。
なのでこの係数を変える事で硬めややわらかめと言った調整が可能です。
http://homepage1.nifty.com/kaneko/abodyp.htm
もう一度上のページを読んで見てもちゃんとバネ係数と言っているようです。

フックの法則はここに持ち出すのは正しくない。

dが力だとすると、力＊質量に加速度が比例して、加速度を積分して速度になり、速度が積分されて位置になるけど

ここでは、dをいきなり積分している。だからdは力ではない。
擬似的にそれなりの表現が出来ているのだから面白いという事でいいのだと思う。

正しくないは言い過ぎたな。

強い摩擦が働いていて、その時間分解能の中では
速度が力にほぼ比例する特殊な状況のシミュレートと考える事は出来る。

だから、バネ係数であり摩擦係数でもあるわけだ

はさみうち法のＣ言語でのプログラムを教えてください。

>>698
マルチポストには教えられません。

>>698
いわゆる2分法と同じものですよ。
たとえば、このスレで言ってた平方根なら、
http://ayusya.hp.infoseek.co.jp/ProgramAlgorithm.html#Sqrt

わざわざありがとうございました。参考にしてみます。

>>198
わたしは部外者だけど、あなたはキモいと思う。

半年も経ってからご苦労様。

「C/C++の宿題を片付けます」スレからこちらを奨められました。
よろしくお願いします。

重点サンプリング法の質問はここで良いでしょうか？
プログラムを組もうと思っているのですが、重点サンプリング報じたいがよく判らないので、
『解を得るまでのフロー』があっているチェックしてください。

『問題』
P[R<S]を求めるのが最終目的です。（RとSは互いに独立）
fr,fsはS,Rの確率密度関数（それぞれWeibull,Frechet）
I(R<S)はR≦Sなら1を、R>Sなら0を返す関数
重点サンプリング関数は互いに独立な2次元正規分布で平均、標準偏差は共に（18,4.5）

『解を得るまでのフロー』
１. 正規分布(18,4.5)に従う乱数を2つ生成し、(r,s)とする。
２. I(r<s)を計算する。
３．fr(r)*fs(s)を計算する。
４．φ((r-18)/4.5)*φ((s-18)/4.5)を計算する。（φ(●)は標準正規密度関数）
５．（2の結果）*（3の結果）/（4の結果）を計算する。
６．１−５を繰り返し、平均値を取る。

よろしくお願いします。

longest common subsequence使用して行単位差分を取ろうと思ったのですが、
トップダウンだと計算量が指数的に増えるし、
ボトムアップだと、LCSは求まるが、経路求めようとするとでかいメモリが
必要でどうしたいいものなのでしょうか？

MMO製作企画を立ち上げました。協力できる人はこちら
http://www112.sakura.ne.jp/~kaientai-project/creategame.htm

2chスレ
http://game10.2ch.net/test/read.cgi/mmominor/1108379282/l50

ただ今職人（プログラマ、グラフィッカー）はげしく募集中！

>>705
Gusfieldの本でも読みなさい

SuffixTreeでパターンマッチングして最適解探せってことか....

> SuffixTreeでパターンマッチングして最適解探せってことか....
違うだろーが

違うのが、Gusfieldの本手元にないからわかんね

ttp://www.xmailserver.org/diff2.pdf
これ、全部理解できる人いますか（自分6ページ目から解らない）

組み合わせについて教えてください。
自然数の配列 int[N] のなかから、任意の組み合わせを
抜き出し、その要素の合計がXを超えない最も大きい組み合わせ
を求める。
という問題なんですが、Nが大きくなると、計算量が爆発的
大きくなります。
どうにかならないものでしょうか？

なお各要素はXを超えないとします。

モンテカルロ法。

>>713
すいません。モンテカルロ法ということは、
要するに、全部の組み合わせを考えないで、適当に選んだ
物の中から、最善なのを選べばよい、ってことでしょうか？

行列の固有値を求めるには？

>>712
それってNP完全のナップザック問題でしょう？
ヒューリスティックな解法やらいろいろな近似解法が考えられているから調べてみなよ。

ヒステリックな解決法ですか。
調べてみます。

円周率を11進数で求めてみたいのですが参考になるサイトはありますか？

>>718
2進数で求めた小数部を次々と11倍しては整数部を引いていくのはいかんのけ？

>>717
テメー　それわざとか？わざとなんだろ？あやまれよ、あやまれ！！！！！

>>717
/::::::/::::::::::::::::＼/　　　|:::::/|:::::|　|::::::|　|::::|::::::::|:::::::::::::|::::::::::＼:::::::::::::::
:::::::/::::::::::::::::::／ ヽ､ 　|::/　|::::|　|::::::|　|::::ﾄ､:::::|､:::::::::::|:::::::::::::::ヽ:::::::::::
:::::/::::::::/::::::/　 ,=＝＞ﾄ{_,　|:::|　|::::::|　|::::|　＼|＼::::::::|::::::::::::::::::|::::::::::
／|::::::/|:::::::| イ ／(　)､ヽ 　|:::|　l｀'十┼┼-----‐＜「:::::::::::|:::::|::::::::::
　 |:::/::ｏ::::::|　| {::::::l|l|::!｜　 V　 |:::::!　ﾚ/´,ｨ´￣｀ヽ::::ﾄ、::::::::|:::::|::::::::::
　 ﾚ'.:::::|::ｏ::!　ヽヾ､:::ノノ　 　 　 ヾ､| 　 | /::ヽ､＿ノﾚ'　ヽ:::::::|:::::|::::::::::
／.:::ﾟ:::∧:::::|(__)ﾆ＝=ﾆ 　 　 　 　 　 　 | |::::::l|l|ｌ:::::::|　　 ﾄ､::::!::::｡:::::::::
.::::::::::/::::ﾊ:::| ´￣￣｀　　　　 　 　 　 　 ヽヾ､;;;;;;;;;;ノ　　Ｏ::::ｏ::::::::::::::::
::::::::/::::/ .:ヾ､　　　　　　.:::　　　　　´￣ ＝=‐-　二つ /:::::::::::::::::::::::::::　　　　　あやまれ!!
:::::/::::/ .::::∧　　　　　　 ｀　　　　　　 　 　 　 　 　 　 /::::::::/::::::::|:::::::::　>>716さんにあやまれ!!
::/::::/ .:::::/::∧ 　 　 　 ヽ｀'ー---　、 　 　 　 　 　 ／.::::／:::::::::::|:::::::::
/:::/ .:::::/.::/.::.ヽ 　 　 　 |:::::::::; -‐::::.ヽ　　 　 　 ／.::::／:::::::::::::::::|:::::::::
::::;' .:::::/ .::ｉ:::::::::.＼　　　 !:::/7:::::::::::::::::ｉ　　　 ／.::::／:::::::::::::::::::::::|:::::::::
.:::! .:::/ .:::::!:::::::::::::/＼　　Ｖ〈::::::::::::::::::::| 　 ∠:::::／:::::::::::::/.:::/::::::|:::::::::
::::|:::/ .:::::::l::::::::::::/.::::::.＼　＼ヽ､＿／/　　　　/::::::::::::::::/::::/|:::::::|:::::::::
::::ﾚ' .::::::::/::::::::::/.::::::::::::::.＼　｀'ｰ--‐'　_,. ‐'"/.::::::::::::／.::::/::|:::::::l＼::::
:::::::::::::／.::::::／.::::::::::::::::::::::.｀'ｰ--‐''"´ヽ　／.:::::::::／.:::::／::::|:::::::|　 ＼

SEX

>>718
10進数で求めるプログラムの10を11に変えればいいんでは？

ヒステリックな苗木野そら

不定な連立一次方程式の解を求める手法希望

Az = 0

N : >= 2 の整数
A : size NxN, rank(A) = N-1 の行列
z : size N

[zの要素の和は1] の条件を加えて制約条件 Nつで。
よろしく。

シンプレックス法

まだ試してないけれど道が広がった。ありがと。>>726

ついでと言っちゃなんだけれど、>>725 のAのN行の中から、
不要な条件(行)を求めるにはどういう方法があるかどなたか知りません?

あとシンプレックス法って、
条件数N=10000くらいでも速く(できればLU分解程度)解を求められる?

固定小数に関する質問ですが、
例えば、
小数部に16Bit幅、整数部に16Bit(合計32Bit)を持つ固定小数を求める場合、
25.6を固定小数に直す方法は
　u16 KoteiShousu = 25.6 * (1<<16);
で合ってますか？

調べたサイトに　25.6 * 0xffff のようなやり方を使ってたので、
こちらが正しいのか、それとも、
このやり方は別の表現方法(固定小数の)なのか、分別付かない。

>>729
>で合ってますか？
合っている。

>このやり方は別の表現方法(固定小数の)なのか、分別付かない。
そこだけ書かれても、なんとも言えない。


ところで25.6は無限小数だから正確には表わせない事は理解してる？

>>730
thanks
勉強不足でした。質問忘れてください。スミマセン。

有向であれ無向であれ、節と節を重み付き枝で結ばれたグラフの
最長経路を導く問題は、最短経路のアルゴリズムの内、「最小をみつけたら更新」
みたいな部分を単に「最大を見つけたら更新」に変更するだけで実現できるものな
のでしょうか？んなこたないのでしょうか？

ループの検出を加える必要がある。
「最小選択」にはループの検出の機能がある。

>>733
ループの検出・・・ですか。ありがとうございます。

そんな簡単にはいかない。何か他にも問題があったはず。

>>732
最短経路を導出するアルゴリズムは、
注目する道を順次伸ばしていくアルゴリズムだから、
ある時点で注目している道の中で最短の道より
短い道がそれ以後現れることはない。
(もちろん距離が負の辺はないとして)

でも、ある時点で注目している道の中で最長の道より
長い道は、それ以後いくらでも現れうる。
だから>>732みたいに単純にはいかない。

単一パスのコストc_{n}の最大値Mが分かっていれば、
c'_{n} ← M - c_{n}として最短経路を求めれば、
それは最長経路となっている。

もちろん嘘です(w

最長経路の定義によっては、更に厄介になる悪寒。
仮に、閉ループが形成されない限り経路が重複してもいいとしたら?

>>736
＞でも、ある時点で注目している道の中で最長の道より
＞長い道は、それ以後いくらでも現れうる。
そうなんですよね・・・。ここに苦しんでおります。

>>737
この方法も考えてみました。
（頭の中でシミュレートした結果、上手くないなと思い実行はしていませんが）

>>738
やはり嘘なのですか？

>>739
＞最長経路の定義によっては、更に厄介になる悪寒。
今のところは、閉路であることが前提としたものを作っています。

>>740
> ＞最長経路の定義によっては、更に厄介になる悪寒。
> 今のところは、閉路であることが前提としたものを作っています。

意味がわかんねえ。

ノードの重複通過は許容するのか?
する場合、
パスの逆方向通過は許容するのか?
パスの同方向重複通過は許容するのか?

とっとと書け。全然難易度が違う。
最短経路問題と違って上の条件設定があり得ることを理解してないのか?

>>741
ノードの重複通過は許容しません。
（閉路であれば）重複通過を許容しないものが基本だと決め付けていたので、
過去のレスには書きませんでした。

じゃあ、総パス探索してから、最長を選択して終了。

>>732では閉路なんて言ってないじゃん。(w

入力：有向グラフG=(V,A)、枝の重みw:A->R
出力：Σ{ w(a) | a ∈ P } が最大である単純な道P

（注）同じ点を重複通過しない道を単純な道と呼んでます

っていう問題ならＮＰ困難（さらに近似困難）だよ。

FX = lnX0 - 2 '解こうとする関数FX

DF = '関数FXの微分式

X1 = X0 - (FX / DF) 'ニュートン法の基礎式よりX1を計算

DX = Abs((X1 - X0) / X0) 'X1とX0との隔たりを調べる変数DXを計算

N1 = N1 + 1 '繰り返しの回数N1をカウント

誘導されてきました。このVBコードの一部を書き換えて√２の近似値を求めるプログラムを作成したいのですが
分からないです。どなたか教えてください

age

>>746
ニュートン法でしょ？
特に書き換えず、そのまま適用してよいと思いますよ。

メディアンフィルターについて教えてくだすれ

>>749
2次元なら、周囲9ブロックの値をソートして5番目の値を使う。
25ブロックとか49ブロックにしてもよい。

>>750
そうすると、メディアンフィルターはボケ効果ですよね。
3x3の平均を取るフィルターでもボケると思うのですが、較べるとどう違いますかね。

ttp://cutie.dip.jp/pc/image/7.php

>>750
なるほど、ぼかしと言うよりノイズ除去ね。THX

×>>750
○>>752

囲碁のプログラムを組んでるんですが、
強さを表すのにレートを使おうと思ってます。
条件として

１　レートの高い人（強い人）がレートの低い人（弱い人）をボコってもレートが殆ど上がらない。
２　逆の場合はレートがグンと上がる。
３　同じ位のレートなら一律+1とかちょっとだけ上がる。

以上の条件を満たすような計算アルゴリズムで何かいいのありませんかね？

>>755
例えば、√(相手のレート/自分のレート)とか?
つまりレートが同じなら1、相手のレートが自分の9倍なら3、相手のレートが自分の1/4なら1/2って計算。
この数値だと、レート9倍の相手となら5連勝すれば追いつけるね。
#って、負けた方は下げないのかな?

>>756
負けた方は下げます。なるほど√か、いいかも。

１ と ３ が矛盾しているように思いますが

>>758
そうそこの境界が曖昧なんだよなぁ。
今のところ何戦かして標準偏差出してって境目を作ろうと思ってるんだが・・・。

レートが整数であるならば、

「殆ど上がらない。」
は +1 または +0 という意味かな？

「+1とかちょっとだけ上がる。」
は +1 または 2〜3 程度上がるという意味かな？

漏れは同じ位のレート同士の対戦でももっとレートの変動があっていいと思うべな

http://game10.2ch.net/test/read.cgi/gameama/1116492510/5
稼動しているゲームでのレーティングなのですが、結構うまく機能してるように思います。

Aをn次正方行列、x,bをn次ベクトル、0をn次ゼロベクトルとしたとき、
Ax=0のトリビアルで無い解を解くロジックってあるのでしょうか。
巷の本はすべてAx=bでAは正則行列としているので、
一意の解を求める方法しかありません。

ある

そんな意地悪しないで、せめて書籍ぐらい教えてあげなよ。。。

ニューメリカルレシピとかいう本に載ってなかったか？
最小ノルム解でぐぐるとか

>>762
馬鹿かおまえは

Gauss の消去法でも使えよ

>>766
ここにも馬鹿

固有値がわかっていて、固有ベクトルを求めるルーチンと同じにならないか。

じょるだん標準形はどうやって求めるのでせう。

先ず、最小多項式を計算汁。

レポート課題（2回目）

上記のアプレットを用いて、次の1, 2 のどちらかのプログラムを作成せよ。

1. data[0] (データ用メモリの 0 番地) に置かれた値の階乗を計算して出力す
るプログラム。

2. 面白い問題を自分で考えて、そのプログラム。

プログラムは、上記のアプレットのページで実行しているところを、プリント
アウトせよ。1. の場合、10 の階乗を計算しているところをプリントアウト
すること。それに、説明（どのメモリアドレスが何に用いられているかなど）
を書き加えること。
http://www.i.h.kyoto-u.ac.jp/~tsuiki/lecture/jouka/3.html
1を誰か教えてください。どこに何を記入すればいいのか。
まじおねがいします。

>>771
しかし幼稚なことやってんな
大学ならもっと理論的なことやればいいのに

こんなもんアビバでやるべきことだよ

アビバってプログラミング教えているの？

浴び場はc言語やd言語、vbにじゃ場やでるふぁいとか教えてるだろ

マジですか？

指針は、
とりあえずdata[1]にデータコピーして、
data[1]==2なら終了
そうでないなら、1減らす。
data[0]とmulを取る。
store、loadしてから繰り返し。

>>776
すいませんね。大変参考になりました。

Hirschberg Algorithmの実装したソースコード
てどこかでダウンロードできないでしょうか？

>>778
JavaScriptだが
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Hirsch/

どなたかラスターオペレーションコードから計算式を求める方法をご存知でしょうか ?

Destination, Source, Pattern, Mask の 4 項からなるラスターオペレーションコードは 16bit 値になり,
それぞれの項は,

Destination: 0xaaaa
Source: 0xcccc
Pattern: 0xf0f0
Mask: 0xff00

という値になります.
演算子は, AND, OR, XOR, NOT の 4 種類になります.
ラスターオペレーションコードは, これの演算結果が値となっていることまでは理解しました.

たとえば, Source と Pattern を AND したものを Destination に OR する場合,

D | (P & S) -> 0xaaaa | (0xf0f0 & 0xcccc) -> 0xeaea

となり, D | (P & S) のラスターオペレーションコードは 0xeaea になります.

ですが, 逆に 0xeaea から 0xaaaa | (0xf0f0 & 0xcccc) という計算式を求める方法が
分かりません.

Windows と X で, ラスターオペレーションに同様のコードを用いるので, 一般的な
アルゴリズムのように思うのですが, 検索でもこれを解く方法を見つけられませんでした.

最悪, すべてのラスターオペレーションコードと計算式を関連付けた 65536 個のテーブルを
持つという方法も考えたのですが, あまりにバカなコードになってしまうので, なんとか
計算で求めたいと思っています.

どなたかご存知の方がいらしたら, 知恵を貸してください.

>>780
まず、8ビットを分解して2進化する。
0xff = 0x80 | 0x40 | 0x20 | 0x10 | 0x8 | 0x4 | 0x2 | 0x1
= 0x80 & 1 | 0x40 & 1 | 0x20 & 1 | 0x10 & 1 | 0x8 & 1 | 0x4 & 1 | 0x2 & 1 | 0x1 & 1
つまり、
0xff = 0b11111111
これを0xeaに当て嵌める。
0xea = 0b11101010

さて、それぞれのビットの重みはd, p, sの演算によって作られる。
0b10000000 → p & s & d
0b01000000 → p & s & ~d
...

つまり、
0xff → p & s & d | p & s & ~d | p & ~s & d | p & ~s & ~d | ~p & s & d | ~p & s & ~d | ~p & ~s & d | ~p & ~s & ~d
0xea → p & s & d | p & s & ~d | p & ~s & d | ~p & s & d | ~p & ~s & d
となるのでビットごとにp, s, dの(反転と)&演算を行なうかどうかの判断をすればいい。

尚、これを整理すると、
0xff → p & s | p & ~s | ~p & s | ~p & ~s = p | ~p = 1
0xea → p & s | p & d | ~p & d = p & s | d
となるので意味が変わっていないことが判る。

ラスターオペレーションコードから演算式を作りだしてコードを動的に作って高速処理させようって事？
ハードウエアで処理しちゃうから、あんまり流行らないと思うけど

>>780
16ビットそれぞれに、　チップセレクタ
http://www9.wind.ne.jp/pakoton/HOSPITAL/kimo1/a_dec.gif
がついてると思えばいい。

つまり、１６個の　4入力ANDで　入出力にインバータがついてるかどうかの回路にいったん置き換えて
あとは変換してゆく

>>781
>>783
ありがとうございました !
おかげでロジックが見えてきました.

>>782
あまり詳しくは言えないのですが, 特殊な組み込みのフレームバッファボードで
ラスタオペレーションの描画をすることになりまして･･･
私も今更ソフトでこんなことするハメになるとは思っていませんでした.

与えられた平面上の二線分の交差判定ってどうやるのがシンプルですか？
なお、交差には二線分がぴったり重なってる場合も含めます。

重なってるのを交差と見なさない場合は外積ふたつ計算してやればいいんですが、
重なってるかどうかで分岐したりするとプログラムが冗長になってしまいます。

ぜんぶで5〜6行に収まるシンプルな方針があれば教えてください．

>>785
外積を計算するという事は、回転変換しているとも考えられる
ttp://www.tensyo.com/urame/prog/linealgo.htm
　ここの　”線分が交わるか？”を参照

だから、回転変換して

ここで聞いていいことなのかわからないけど、
学校の問題でこんな問題が出たんですけど
なんて答えればいいと思いますか？

「次の専門用語を解釈せよ」って問題に
「アルゴリズムの正当性と停止性」ってのがあるんですけど、
言葉で表すならどうしたらいいのかわかりません。

間違った答えを返さないかどうか＞正当性
永久ループに陥る事がありえるかどうか＞停止性

>>788
ありがとうございます！助かりました！

ゲーム木を探索する時に最も評価の高い葉を保存しておきたいのですが、定石的なものはありますか？

最大値というのはαβ戦略にそった根の値です。
最大値かどうかは探索が終了するまで分かりません。
ですから、可能性のある葉を全て保存していては効率が悪いような気がします。
枝でもいいです。(葉までのパス)

>>790
priority queue

ありがとうございます。参考にしてみます。

非線形方程式を解くものにニュートン法がありますが、これは除算が含まれているため、
０に近い解を出す場合などにオーバーフローを起こしてしまいますよね。
この問題が（ニュートン法よりも）解決されているアルゴリズムはあるのでしょうか？

>>793
ニュートン法でも、除算の分子と分母の両方をxの累乗であらかじめ割った式に変形しておくと、
オーバーフローしないよ。

>>794
むむ、確かに！ありがとうございます。

ax^3+bx^2+cx+d=0の3次方程式を解く方法教えて下さい。
取りあえずaで割って
x^3+Bx^2+Cx+D=0とするかな？とおもってます

>>796
4次までの代数方程式には解の公式が存在する。
ニュートン法を使うまでも無い。

>>797
http://cat.edu.kagoshima-u.ac.jp/Text/Public/Physics/Math/AlgebraicEq/SolOfEq.htm
これですかね？

>>797,798
ただ単なる3次方程式じゃあつまらないから、
虚数解まで出す、っていう条件をつけたらどうだろう？

ageてしまったorz
スマソ

そして800ｹﾞﾄ

ていうか、解析的に出てるんだから虚数解だって簡単だってね。
何言ってるんだろ俺orz

じゃあ一般的にn次方程式だったらどんなアルゴリズムがありますか？

>>801
C言語なら俺に聞け! Part 111
http://pc8.2ch.net/test/read.cgi/tech/1121657911/138

>>797
3次の場合は、
- 解の公式使うと複素計算になる＆精度が微妙
- 1つは必ず実数解
という性質から、
1つの実数解をニュートン法使って求めてから、
その1個を因数分解して、残り2個は2次の解の公式で解くことが多いみたいよ。

4次の場合、1つは必ず実数解ってところが成り立たないから微妙だけど、
精度考えると多分、こっちもニュートン法使う方が確実。

スレ違いだったらごめんなさい。やりたいことはこうです。

1. 32ビットのポインタではなく、16ビットのハンドルを返す mymalloc() を実装したい。
2. myfree() されたハンドルは、なるべく遅く再利用する。

これを実装するために、mymalloc() と myfree() を以下のように実装しました。

unsigned short mymalloc(size_t size)
{
p = malloc(size);
h = obtain();
btree_insert(h, p);
return h;
}
void free(unsigned short h)
{
p = btree_search(h);
btree_remove(h);
lose(h);　free(p);
}
続く…

>804 の続き

これで基本的にはうまく動いているのですが、obtain() と lose() の実装をどうするか、悩んでいます。これらの仕様は以下です。

1. obtain() は 1〜65535 の間の数字を返す。使用済みの数字は破棄されるまで返さない。
2. lose() はすでに使われている数字を破棄する。
3. obtain() は、破棄された数字をなるべく「遅く」再利用する。

コードで書くと、
for (i=0; i<65535; i++) {　n = obtain(); lose(n);　}
この n ができる限り一つも重複しないで、
for (i=0; i<65535; i++) obtain();
lose(30000);　lose(65535);
n = obtain(); // たぶん 30000 を返す
n = obtain(); // たぶん 65535 を返す
この最後の二行が十分速く実行できるアルゴリズムを考えています。
現在は、65535ビットのマップを使って、つまり unsigned char bitmap[8192]
とやって使用済み番号を管理しているのですが、実際に obtain() が利用される
回数が 100回くらいしかない場合でも 8Kb も消費するのが気に入りません。
未使用のハンドルを探すのに btree が使えたらいいのですが…

いい方法、ヒントがあったら教えてください。よろしくおねがいします。orz

#16ビット環境のエミュレートに使うんだろうか。

自分ならセマフォかプロセスレベルで最初に一回だけmalloc(65536)して
先頭アドレス、サイズの構造体をリストで管理。myreallocのような実装や
デフラグな機能を考慮する。

>>796
激しくマルチ、ﾊｹﾞｼｸ(・A ・)ｲｸﾅｲ!

ぼるじょあがC/C++の宿題を片づけますYO! 48代目
http://pc8.2ch.net/test/read.cgi/tech/1121471445/207

C言語なら俺に聞け! Part 111
http://pc8.2ch.net/test/read.cgi/tech/1121657911/128-138

>>805
8k バイトぐらい気にするな

(;´∀｀)うわぁ

>806
ビットマップを使う方式で 8Kb 消費すれば
十分高速なものがすで作れていますので
malloc(65535) はちょっと…

>808
うーむ

>>805
　static uint16_t last = 0;
　uint16_t obtain(void) {
　　uint16_t x = last;
　　while (btree_search(x)) {
　　　x++;
　　}
　　last = x + 1;
　　return x;
　}

>811
それ、ただ実装しただけです。ぜんぜん速くないです。
>805が書いてるビットマップという方式の方が遥かに
速い。だから、８ｋｂくらいけちけちすんなっつー話かと。

>>811
1,3,2と開放されたら1,3,2と返さんといかんのやないの？

>>813
逆やろ。1,3,2はなるべく遅く再利用。

>>814
813 で言いたいのはそういうことやない。

1,2.3,...,65535 全部使われた後に 1,3,2 の順で開放されたら
三つ空きが出来るやろ。

そこから三つ要求したら 1,3,2 の順で割り当てられんといかんのやないの？

という話や。

空きブロック ⇒ 空きブロック をリストで管理して、
末尾⇒先頭に連結した　ﾘﾝｸﾞﾊﾞｯﾌｧ形にしたら速そうな気はする
が、断片化が激しいと 8kb 超えるかもしれない。

>815
必ず遅くじゃなくて、なるべく遅くだから、べつに 1,2,3 と割り当てられて
も問題ないでしょう。ようは、開放されたばかりのやつを使うんじゃなくて
まずは、空きが他にあるならそっちからってことだと思われ。

>816
全部使われた後に全部開放されたら、その時の空きブロックリストは
軽く 8kb 越えてしまわない？結局、空きブロックを 1ビットで表せる
ビットマップ方式が一番メモリ消費も少なくて、かつ、速度も十分かと。
リストは速度は最速でもメモリ消費がかなり酷いことになりそうな悪寒。

>>817
空きﾌﾞﾛｯｸの表現をランレングス的に表現すれば…
[先頭ID + 長さ] で１つの管理体にすると。

そも32ビット環境で16をエミュレートするのにこのようなことをしても報われるような気がしない。

いったん65535をリニアに確保した方がエリアを利用する側にとって速いような。

>>811でいいんじゃないの?
ビットマップが嫌なくらいだから、あまり確保されないんでしょう?

SECDという、λ計算をする仮想機械をＣかJavaで設計したいのですが、
どこかにいい情報のあるサイトはないでしょうか？
あと設計上のヒントなど知っていたら教えてください。

作りたいのは以下の計算をするプログラムです。


S,E,C,Dの4つのスタックから構成されています。
Sはそれぞれの要素が式の評価の中間結果を保持するために使用される。
Eは展開中の式の環境を積み上げるスタック。
Cは制御用に各要素を保持。
Dはダンプ用のスタックとして、処理順を制御した場合に
　それぞれのスタックの要素を一時的に保持するために用いられる。

具体的な計算です。

1.Cが空、でDが(S',E',C',D')であるなら、現在の状態(S,E,C,D)は(Sの先頭:S',E',C',D')に置きかえられる。
2.Cが空でない時
1.Cの先頭がidentifierである時、
Sの先頭に、Cの先頭をEで評価した値を置く。
Cの先頭を消す。
2.Cの先頭が関数抽象Xの時
EとXからclosureをつくり、それをSの先頭に置く。
Cの先頭を消す。
3.Cの先頭がapの時
1.Sの先頭がE'とlmv.Mから構成されるclosureの場合
Sを空とする
Eに(v2ndS)を付け加える。
CをMで置きかえる。
Dを(Sの2番目以降,E,Cの先頭を除いたもの,D)で置きかえる。
2.Sの先頭がclosureではない時
Sに(Sの先頭Sの2番目)を先頭と2番目を取り除いた上で積む。
Cの先頭を消す。
4.Cの先頭が関数適用(MN)の時
Cの先頭にap,M,Nの順で積む。

SECDとは懐かしいのう。
↓から辿れ！
http://en.wikipedia.org/wiki/SECD_machine

>>824
あ、ありがとうございます。
けど、そこも含めてだいぶいろんなサイトを探し回ったんです・・。
プロログという初めて聞いた言語で作ったＳＥＣＤを見つけたのですが、
当然理解不能でした。
同じサイトのＣ言語版はまだ作成中でした。

おもろいｽﾚ見っけ。数値解析結構興味ある。
ルンゲ食ったほうを使って卒論に使う計算用のプログラム作ったんだが
実はいまだにあまり理論をよくわかっていないｗ

>>826
大学1年生でも知ってる。

まじで。数値計算法は卒論のときはじめて勉強したので。
てかそれまでプログラムしたこと無かった

>>826
つ「数値計算の常識」（伊理・藤野）

大学行ってないけどルンゲクッタは知ってた漏れが来ましたよ。
プログラム電卓で利用してたのは内緒。

アルゴリズムの宿題とかわからないのですが、どこかで教えてもらえませんかね〜？？

>>831
聞いてやるから質問してみろ。

宿題スレって言うのがあるよ。検索してみな。

Bスプラインからベジェに変換するのは分かりますが、逆はどうやるのか
分かりません。どこか参考になるサイトはありませんでしょうか。

そりゃ、片方は2次式、片方は３次なんだから逆は単純にはいかんわな

どうしてもやるなら分割してゆくしかないだろ

>>834
いってることが分からん

Bスプラインはベジエの完全上位互換だ
君の言ってることは逆としか思えん

サイトはあったら俺が教えてほしいぐらいだな
俺は会社で勉強しただけだし

>>835
どっちも、次数は任意（0以上なら可）かと

そりゃ次数を合わせるなら、数式も係数も同じものだ
悩みようがないから、
一般的にはBスプラインは2次、ベジェは３次だからそこで悩んでるんだろうと推量したんだが？

3次のベジエを2次のBスプラインにしたいってか？
そりゃ無理だ、近似しろ

単純にZ座標を無視して無理やり2次にしたらどんな惨状になるのか見てみたい

？

？？？

2次元, 3次元じゃなくて、2次式, 3次式のことだが・・・

>>833
アルゴリズムの宿題であって、決まった言語の宿題とは書いてないよ

>>835
その通りです。

>>838
その近似方法が知りたいのです。

答え書くのスゲー面倒だし
こういう面倒なのに答え書いても
経験上、感謝の一言も無いから
書くのイヤだ

最小自乗近似しろとだけ言っとく

これだけじゃあんまりだから、少し書くか・・・甘いな俺

Bスプライン関数をBs(x), ベジエ関数をBz(x)とし、
x = xs〜xeの範囲でBs(x)≒Bz(x)としたいとする

まずBs(x)の次数とノットベクターを決める
この辺は知らなかったら調べてくれ
教えるには面倒くさい

次数とノットベクターが決まると、
自動的にコントロールポイントの個数と基底関数が決まる
この辺も知らなかったら（以下略

コントロールポイントの個数をNとし、
各コントロールポイントをC1〜CNとする（コントロールポイントは未知）
基底関数も同じくN個あるからそれをB1(x)〜BN(x)とする（こっちは既知）

Bs(x) = �� Ci * Bi(x) （i = 1 .. N）だ、これは定義

行列を使って、以下のようにも書ける

Bs(x) = ( B1(x) B2(x) ... BN(x) ) ( C1 )
　　　　　　　　　　　　　　　　　　　　　( C2 )
　　　　　　　　　　　　　　　　　　　　　( ｜ )
　　　　　　　　　　　　　　　　　　　　　( CN )

次に近似に使うサンプル点を決める、xs〜xeを2Nで等分割とかが妥当か
サンプル点のxの値をx1〜xMと置き
Bs(x1)=Bz(x1), Bs(x2)=Bz(x2), ... Bs(xM)=Bz(xM)を最小自乗近似する
この式を行列を使って書いて

( Bs(x1) )　 ( B1(x1) B2(x1) ... BN(x1) 　)　( C1 )　 ( Bz(x1) )
( Bs(x2) ) = ( B1(x2) B2(x2) ... BN(x2) 　)　( C2 ) = ( Bz(x2) )
(　　｜　　)　 ( 　　　　　　　｜　　　　　　　 　) ( ｜ )　　(　　｜　　)
( Bs(xM) )　 ( B1(xM) B2(xM) ... BN(xM) ) ( CN )　 ( Bz(xM) )

( B1(x1) B2(x1) ... BN(x1) 　)　( C1 )　 ( Bz(x1) )
( B1(x2) B2(x2) ... BN(x2) 　)　( C2 ) = ( Bz(x2) )
( 　　　　　　　｜　　　　　　　 　) ( ｜ )　　(　　｜　　)
( B1(xM) B2(xM) ... BN(xM) ) ( CN )　 ( Bz(xM) )

↑の式は、A X = B という形の線形方程式になっている
未知数はN個あるコントロールポイント
A の転置行列を tA と置いて

A X ≒ B
　↓
tA A X ≒ tA B
　↓
inv(tA A) tA A X ≒ inv(tA A) tA B
　↓
X ≒ inv(tA A) tA B

とでもしとけ、invは逆行列
Bz(x)がベジエであるという事実を全く利用してないが、まあいいだろ

>>845-848
必死で読んで調べて勉強してみます。ありがとうございました。

意外に謙虚な奴だな

実際にやるとなると
基底関数を求めるトコで詰まるかもしれんな

まあ、Bスプラインを扱っている以上
基底関数はどこかで必ず求めるルーチンがあると思うが
簡単に利用できるとは限らんしな

そういう場合に、多分うまくいく方法が無いこともない

C1 = 1, C2〜CN = 0 となるBスプラインデータを無理やり作ると
Bs(x) = �� Ci * Bi(x) （i = 1 .. N）だから
そのデータでは、Bs(x) = B1(x)となるので、B1(x)の値が求められる
B2(x)なら、C1 = 0, C2 = 1, C3〜CN = 0だ

Bスプラインが多次元関数の場合は、
C1 = (1, 1, 1), C2〜CN = (0, 0, 0)といった具合にして
x,y,zどれかの成分の値をB1(x)として利用な
（どの成分も同じ値だから）

>>850
まだコーディングまで行っていないのであまり大きなことは言えませんが、
方針は何とか分かりそうな感じです。
わざわざ詰まりそうなところまで御指摘頂き本当に感謝します。

　単純にN分割して、誤差をチェックするのでいいと思うが？
　誤差が希望範囲を超えてたら分割数を増やすというので。

　分割した曲線を2次で表現すると
　パラメータは３点、そのうち2点は、分割点で拘束しないといけないから、残りは1個
　　残りの1個を
　　　　・さらに中点で拘束する
　　　　・中点の微分で拘束する
　　でどちらが良いかだろうな。

ダウンヒープが途中で止まることってないの？

Re:>9
帰れ。
http://tv6.2ch.net/ainotane/

Re:>10
ようやく話の出来そうな人が現れてくれた。
ちなみに、ビットマスクって何ですか？

>>854
ビット列のうち見る対象を絞るフィルターだよ

>>11

log関数のアルゴリズム(ｆｏｒｔｒａｎ)を教えてください。

>>857
http://piza2.2ch.net/tech/kako/997/997150743.html

２つのビット列の類似度を求める方法はありませんか？

ルイージ度だったら n%2==0の時

>>859
XOR　して１と０のビット数の比率を表示すればいいんじゃないの？

ビット数を数えるのはシフトとAND と加算した面白い例が、どっかのスレにもあるし
やねうらおさんの所にもあったように思うよ

>>859
XORを取って、bit反転して、bit数のカウント。

bit数のカウントは↓に速い方法が。
http://www.amazon.co.jp/exec/obidos/ASIN/4434046683/

>>861
ハミング距離じゃなくてAに何回演算をしたらBになるかみたいなことですが。

>>863
どういう演算？　その規定が無けりゃどうしようもないだろ。

どなたかクラフチック法のアルゴリズムについて教えていただけないでしょうか。

マジでｵﾚのほうが大仁田より根性も信念もあるね。
冷静な判断力や常識もｵﾚのほうがずっと優れてる。
大仁田、あんた議員辞めるべきだよ。
これ以上、生き恥晒すな。
腕っ節が強ければ己が通る時代はとっくの昔に去った。
いまだに勘違いしてるから困ったもんだ。

マジで漏れの方が>866より紺青も新年もあるね。
レスがあがれば己が通る時代はとっくの昔に去った。
いまだにスレ違いしてるから困ったもんだ。

アルゴリズムのクラスでプレゼンやらされるんですが
内容をよく読まずにハフマン符号選んだ俺の運命は一体どうなるんですか？

有名なの選んでよかったじゃん

関係ないけど誰かDoubleArrayについて解説してほしい。
なんとなく検索速いのはわかったけど、何してるのかわからんかった。

>>868
そんなの分からないようじゃ大学卒業する資格ないって。
図書館に行けば詳しく説明した本どれだけでもあるよ。

Double-Arry Trie?
http://linux.thai.net/~thep/datrie/datrie.html
読めば分かるでしょ?
Tripleも説明してあるから、doubleでの工夫も分かりやすい。

ハフマン符号なんて難しい話はないから中学生でも理解できるよ。
早い話が、全ての文字を同じビット数で表すのではなく、
値のうちよく使うものから順に少ないビット数による表し方を割り当てていく。

＞ 早い話が、全ての文字を同じビット数で表すのではなく、
＞ 値のうちよく使うものから順に少ないビット数による表し方を割り当てていく。
そりゃ、中学生レベルの理解だ。

ヒント：エントロピー

>>870
そこ知ってるサイトだったけど、
また２時間ぐらい眺めてみました。
が、やっぱりよくわかりませんでした。

簡単な擬似コードで示してくれるとありがたいんだけど。
midatrieはコード汚くて読む気なくなるし・・

あー、でもソース読むのがいいかなやっぱ・・
なんとなく全体像が見えてきた。
ディレクトリ深いの読むの苦手意識あるかも。

いきなりですが挿入ソートの計算量を教えてください。

気になるあの子へそーっと挿入

いや、変な想像はどっかいってやって。

最良、平均、最悪の計算量をお願いします。

宿題スレにいけ

O(N^2)

うわ〜、最小自乗でBSPLINE近似とか昔おれもやったわ。なつかしー。
しかしこんなところで部分的な説明するより書籍などを教えてやったほうが
基礎から学べて良いと思った。原理さえ分かれば色々な数式で近似できるしね。

>876 >879
その程度、コードをテメェで実装すりゃ一目瞭然だろうが。

球が瓶に何個入るか計算できないのは何故ですか？

つまんね

>>884
やってみないと判らないからさ。
この個数は間違いなく入るというのは計算出来るけどね。

仕事の見積もりなんかもそうだろ？
実際やってみないとホントの所は判らない。　

>>869
ども。一応教科書に載ってるのから選べ、ってことだったんで有名なのは確かだけど
実はもっと簡単なの(B-treeとか)でも良かったんだよね。

>>870
前回書き込んだときは教科書の内容さえも読む時間がなかったんだよね。
全部英語で書かれてるし。
今はいろんなサイトを見つけたから少し安心してる。

>>871
そうそう、モールス信号も同じ観点から創案された、と今読んだところ。
ハフマン賢い。当時の教授ファノンよりも賢い。しかも特許いらず。
結構良いトピック選んだかも。

B-treeは意外と難しいよ。
アイデアは簡単なんだけれど、
他の木構造と比べないと特徴がはっきりしない。(外部ソートということ以外は)
だから他の木構造についても調べることになる。
それから実装も結構手間がかかる。

ハフマン符号は自己完結的なトッピックだから、勉強しやすい。
上に出ているtrieにもつながっていくし。

ハフマン符号化は足し算さえできりゃ理解できるんじゃまいか

ハーフマン ＝ 半分男 うふぉ！

>>888
ありが�d。
確かにB-treeと他の木構造との比較となるとかなり('A`)ﾏﾝﾄﾞｸｾｰことになってたかも。
ますますハフマン符号選んどいて良かった。

>>889
何を隠そう、それが教科書の内容を読まずに図だけ見てハフマン符号に決めた理由だったりする。

>>890
昔「半分少女」っていうキョンキョンの曲があったね…って俺いくつだ？

このスレの内容程度だと10年位前のOh!MZとかOh!Xでやってたような気なするが気のせいか？

ハフマン符号化なんて、５０年以上前のものだしな。

算術符号の特許はもう切れたの?

>>892
君はジジイで頭も固くなってきているけれど、世の中には若い人もいるんだよ。

>>895
まあ、どっかでちょっとバックナンバーなり探してみ
あの本なぜかこういうのだけはやたらと解りやすく書いてあったから
正直、大学時代の物理の講義よりOh!Xの方が解りやすかった

Oh! X|MZ世代てことは少なくとも30以上だな
おっさんよ？
ちなみに全盛は10年以上前の気がするが

バックナンバー探すより、ぐぐった方が早い。

>892
＞気のせいか？
このへん耄碌してる感じが出ててサイコーに笑える。

Oh!Xで記事にされた内容はこのスレで語るな、と？

Oh!なんとか持ち出さなくてもCマガで毎年のように似た話題やってそうだが

「『Oh!X』 最高〜！」(ﾜﾗ

お前ら低レベルだな。
もうちょっとましな質問してくるやつはいないのか。
ム板から離れてもう5年経つが、話の程度が前と何も変わらないな。

>902
お前のその発言は、小学生に向かって
「俺様が小学校卒業して５年経つが、頭の程度が前と変わらんな」
つってるのと同じ。
住人が５年間も同じなわけねぇだろカス。
お前みたいな短絡的なバカが居るから、この業界後が育ちにくいんだよ。

>>903
わかったよ「俺が中学生のときに勉強してたのとおんなじ事やってるな。おまえら中学生か？」
これなら許してくれるか？

>>904
俺が小学生の頃言っていたことと同じ事言ってるな。お前小学生か？

でも、まあ、アレだ。

こういう業界って後から入ると、既にあるものばっかりで厳しいだろうね。
結果、創造的な部分はなくなるばかりで、労働的な部分の割合が増えるばかりと。

既に陳腐化したような部分はさっさと通過出来るような方法論も必要かな

>>906
いいや、既にあるものよりも無いものの方が多い。

>>903
2chは学校と違って、コミュニティなんだがなぁ。