計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 266 名前：BASIC mailto:fh [2006/01/09(月) 16:12:52 ] N人分のデータ（氏名、体重、身長、年齢）がＤＡＴＡ文で入力されているプログラムが ある。これを用いて次のプログラムをＢＡＳＩＣで作成しなさい 体重が６０ｋｇ以上で、身長が１５０ｃｍ未満の人の名前を表示する 267 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:34:00 ] 宿題は自分でやれ 268 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 17:54:08 ] BASICなんて記憶の彼方だな 269 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 18:15:01 ] 何ベーシックかは指定していないな。 VBとかでもいいとすれば随分アレだ 270 名前：デフォルトの名無しさん mailto:sage [2006/01/09(月) 19:08:23 ] >>266 www.sagami.ne.jp/tadaka/99Basic/ 271 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 03:29:11 ] ヤコビ行列の計算を効率良く行う工夫は何かあるでしょうか？ (n*m)回の微分演算という時間を喰う処理を少しでも短くしたいです もしくは優れたJacobianMatrixクラスの例をご存じであれば是非！ 272 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 06:49:10 ] Jacobian の成分が nm 個ある以上，本質的にそれよりオーダーが落ちることはありえない． 定数オーダーでの最適化は計算モデルに依存するので議論できん．そもそもおまいが微分をどう実装してるかもわからんし． O(nm) すら許せないなら，問題に応じてアドホックに解決するっきゃ無いと思うがなあ．どんな問題解いてるんだ？ 273 名前：デフォルトの名無しさん mailto:sage [2006/01/11(水) 10:57:45 ] >271 LZのスライド辞書みたいに、演算した組み合わせを辞書に登録しておいて、 次回以降は演算を省くってのはどうだろう？ 辞書の検索にかかる時間を何らかの方法（連想配列とか）で短縮する必要はあるだろうけど。 274 名前：271 mailto:sage [2006/01/12(木) 12:31:26 ] >>272-273 早いレスどうもです！ >>272 やはりO(nm)回は「本質的に」避けられないわけですよねー・・・ 微分の差分近似をループでnm回やるつまらない実装なんで、 工夫できないかなと思った次第だったのですが。 ちなみに問題は非線形関数の最小値探査みたいな感じです >>273 んー、いいアイディアなんですが今回は 適用できないような気がします、ゴメンナサイ ただ、そのうち他の問題で使えそうな気がするんで、 そのネタはもらって覚えておきます！　ありがとう！ 275 名前：デフォルトの名無しさん mailto:sage [2006/01/14(土) 00:48:34 ] >>274 最小化したい非線型関数になんか条件付けないと定数レベルの最適化もつらいような 276 名前：デフォルトの名無しさん [2006/01/31(火) 17:55:55 ] 最小二乗法のライブラリきぼんゅ。 277 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 03:14:47 ] >>276 ライブラリも何も、大した計算じゃないじゃん。 278 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 12:32:21 ] >>277 世の中に存在するアルゴリズムの中で複雑と言えるものがどれだけある？ 279 名前：276 [2006/02/01(水) 12:44:24 ] 最小二乗法おしえて欲しいぉ。 280 名前：デフォルトの名無しさん mailto:sage [2006/02/01(水) 13:38:16 ] 残差平方和が最小になるようにパラメータを決定するのです このスレでも簡単な例がいくつか >>178 >>182 >>196 非線形になってくるとちょっとめんどい en.wikipedia.org/wiki/Gauss-Newton_algorithm en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm ここら辺を参考に 281 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 02:20:31 ] >>278 FFTになると、ライブラリが欲しい程度には複雑だと思う。 282 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 08:51:05 ] >>281 どれだけある？という問いにＦＦＴ１個かよ。 283 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 09:25:21 ] >>282 世の中に存在するアルゴリズムがどれくらいあるのか教えてくれたら答えてあげるよ。 284 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 13:43:21 ] 行列計算もだいたい書く気がしないな．条件数が悪い場合とか考え出すと相当面倒くさい． 285 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 14:58:57 ] あとは圧縮＆展開と多倍長演算あたりかね？　汎用的なのは。 各分野毎にはいろいろとあるだろうけど。 画像エフェクト、サウンドエフェクト、3D系演算とか。 286 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 15:52:22 ] >>281 難しくはないが複雑ではあるよな。 287 名前：デフォルトの名無しさん mailto:sage [2006/02/02(木) 22:26:58 ] 各種関数なんかは、大概簡単なことをやっていても、実装は面倒だなぁ。 288 名前：デフォルトの名無しさん mailto:sage [2006/02/05(日) 09:27:32 ] 最小二乗法は 円に適用するだけでも、厄介だし、 直線に適用しようとしたって、実はけっこう難しいよ。 たとえば、2次元画像から直線部を取りたいとしたら、学校でやるようなXとかYでの偏微分じゃ、それこそ偏る。 　残差って何って所から取り掛からないとね。 そして、余程単純じゃないと、たいていは方程式1発で解けるという事にはならない。 数値解で求める事になるだろうな 289 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 07:09:38 ] >>288 ただの偏微分でしか説明しないのって，相当ひどい学校だと思う 290 名前：276 [2006/02/06(月) 10:04:37 ] >>288 じゃ、何を使うのさ？？？？？ >>289 詳しく！！！！！ 291 名前：デフォルトの名無しさん mailto:sage [2006/02/06(月) 14:14:46 ] >>288 最小二乗法はロバストでないのでそのあたりは考慮しないと。 例えば、y=x上に完全に点が並んでいる状態で、 たった一点(1,10000)が入ってきただけでy=2xとかになると困るわけだ。 292 名前：276 [2006/02/06(月) 14:22:51 ] 今回の開発では点の数に関しては、決めウチできます。 293 名前：288 mailto:sage [2006/02/07(火) 06:30:36 ] >>290 だから、最小2乗法を使うなら、何を最小にするのかって所が肝心って事さ 直線を求めるのにしたって、数表上と2次元データとは誤差の意味が違う 数表上なら結果の誤差を最小にしたいし 2次元なら直線からの誤差を最小にすると同時に回転変換で結果が変わらない必要がある 294 名前：デフォルトの名無しさん [2006/02/09(木) 11:57:07 ] 最小2乗法ｱｹﾞ 295 名前：sage mailto:sage [2006/02/09(木) 21:45:42 ] sage 296 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 17:31:27 ] n個の要素の2番目に小さい要素は最悪n+logn−2回の比較で求められることを証明しなさい。 順序統計量を使うのだと思うのですが、帰納法を使って証明するのかどうか分かりません。 どなかか説明してもらえないでしょうか？よろしくお願いします。 高校の時に教師が言っていたんだけど急に思い出して・・・・おねがいします。 297 名前：デフォルトの名無しさん [2006/02/11(土) 18:07:41 ] 　 ／￣￣￣￣＼ ／　　　　 ●　　 ●　 |Y　　Y　　　　　　　　 ＼ | |　　 | 　　　　　　　 ▼　| ﾊﾟｸｯ | ＼／　　　＿＿＿＿人__| |　　　　　　|∨∨∨∨∨　←296 ＼　　　　　＼∧∧　　　） 　｜ ｜　|＼　￣￣＼＼＼ 　｜ ｜　|　　￣￣￣ し し/ 　（_＿）＿） 298 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:33:39 ] 最悪 n - 1じゃないか? 何番目でも最悪 n - 1回でいけそうだ。 今適当に考えただけだから間違ってるかもしれないけど。 299 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:40:59 ] 違った、最悪 n回か。 300 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:45:05 ] >>298 いや、漏れが覚えている限りでは違うと思われ。 MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず 院試にでてたかも。 301 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 18:57:23 ] >>300 やっぱり違ってた。考え直したら、 nが偶数なら (3/2)*n - 2, 奇数なら (3/2)*n - 3/2 回だった。 302 名前：デフォルトの名無しさん mailto:sage [2006/02/11(土) 20:58:20 ] >>296 ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。 あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。 303 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 00:24:16 ] 証明になってないｗ 304 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 03:01:20 ] >>296 完全二分木でトーナメントを考えよう。 一番小さい要素を見つけるのにn-1回の比較が必要。 二番目に小さい要素は一番小さい要素の対戦相手のどれか。 木の高さはceil(log n)で木の一番上には対戦相手はいないから、 二番目に小さい要素の候補たりえるものはceil(log n)-1個 この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。 したがって比較回数は、 (n-1)+ceil(log n)-2<n+logn-2 ただし、ceil(x)はxの小数点以下切り上げの関数 305 名前：デフォルトの名無しさん mailto:sage [2006/02/13(月) 00:39:26 ] >>304 なるほど。 それは比較は少ないけどコピーがメモリが多く必要になりそうなんだけど どうなんだろう。 306 名前：デフォルトの名無しさん mailto:sage [2006/02/13(月) 06:11:40 ] ２分木にする必要性が感じられないってかなってないｗ 307 名前：デフォルトの名無しさん mailto:sage [2006/02/14(火) 10:30:15 ] >>305 実装の話はしてないんだよね。実際にこの比較回数で動くプログラムを作るのは 結構困難な気がするし、普通の 2n 回比較に定数倍で負けそう。 308 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 09:33:06 ] ３２ビットの符号無整数型で３２個のビットのうち N個をランダムに選んで１にするアルゴリズム。 （残りの３２−N個は０） 賢い人教えて。 309 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 11:33:45 ] >>308 そのサイズの乱数を一個生成するだけじゃいかんの？ C なら rand() とかで。 それとも乱数生成のアルゴリズム自体を聞いてるの？ 310 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:12:40 ] たぶん １）組み合わせの数の計算方法が判らない ２）乱数と、その全部の組み合わせを対応させる方法が判らない のだろうと思うんだけどね 311 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:28:33 ] 1U << (rand() & 31) とか、そういうことではないの？ 312 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:35:07 ] >>311 rand って完全にランダムじゃなくて、 下位ビットほど短い周期性持ってるから、 rand() & 31 はあんまりよくない。 (rand() >> 16) & 31 とか、何ビットかシフトするの推奨。 313 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:38:20 ] 分かってて書いてたつもりだけど…アルゴリズムの質問だし。 random()でもMTでも好きなの使えばいいんじゃない？ 314 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 12:41:56 ] >>313 まあそうだけどね。 >>308 がそんな判断できると思えなかったんで、一応補足のつもり。 315 名前：308 mailto:sage [2006/02/27(月) 13:09:41 ] MTとかで生成された乱数の立っているビットの数は １６本を中心にした正規分布になってると思うんだけど、 必ずN本になるようにしたい。 ３本とか３０本とかってのはたまにしか発生しないし。 N回ループで一度使った数は記憶させとくとかっていう 愚直なのは思いついたんだけど遅そうなので聞いてみた。 316 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 15:31:21 ] 32個の数字から N個取り出して順不同というのと　問題は同じでしょ 317 名前：デフォルトの名無しさん mailto:sage [2006/02/27(月) 20:50:08 ] >>316 ですね。 1〜32の間で離散一様乱数発生させたものをa_0、 1〜31の間の乱数をa_1、1〜30の間をa_2として、 初期値は0で左からa_0番目のビットを1にする。 以降左からa_k番目の0のビットを1にする。 　　　　　　　　　　　　　~~ 318 名前：308 mailto:sage [2006/02/28(火) 09:54:13 ] >>317 今はそれでやってます。 みなさん聞いてくれてありがとう。 319 名前：308 mailto:sage [2006/02/28(火) 09:58:33 ] あ、ついでに言っとくとNが17以上の場合は32-N個のビットを立てて反転してる。 連投ごめん。 320 名前：308 mailto:sage [2006/03/01(水) 16:40:57 ] やっぱりもっと速いのないかな。 321 名前：デフォルトの名無しさん mailto:sage [2006/03/01(水) 17:19:36 ] >>320 これ以上議論するなら，「速い」をきっちり定義してもらわないと． 特に乱数生成のコスト，各ビットを参照するコストなどが無いと， どっちが速いかなんて比較できんよ． 322 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 11:59:32 ] もっと早い方法は、全部の組み合わせのテーブルを作っておいて それの配列番号を乱数で選ぶ事だね 323 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 12:53:16 ] >>322 2^32 / 2 (0≤N≤16 だから半分) = 2G×4Byte = 8GB 何を使って動かすつもり？ 324 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 16:39:38 ] >>317 それは、順番を考慮した場合のアルゴリズムだから違うようだけど 結果はN個のビットだから、どの組み合わせも等確率で発生するから問題ないのか >>323 Nを固定すれば　最大の組合せ数は N=16の時で その1/4程度の容量だから最近のPCなら入るんじゃないの？ 組み合わせの数ってどの程度だろ？ 32!/N!/2^N では大きすぎるな 325 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 16:43:14 ] たとえば32個中3個が１の組み合わせを F(32,3) のように書くと 先頭ビットが0 なら 残りは F(31,3) 先頭ビットが1 なら 残りは F(31,2) という事で F(N,M)=F(N-1,M)+F(N-1,M-1) 326 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 17:23:15 ] >>324,325 高校数学の教科書読み直したら？ ttp://ja.wikibooks.org/wiki/%E9%AB%98%E7%AD%89%E5%AD%A6%E6%A0%A1%E6%95%B0%E5%AD%A6A_%E5%A0%B4%E5%90%88%E3%81%AE%E6%95%B0%E3%81%A8%E7%A2%BA%E7%8E%87#.E7.B5.84.E3.81.BF.E5.90.88.E3.82.8F.E3.81.9B 327 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 18:34:31 ] という事は 32 C 16 www.google.co.jp/search?q=32!/(16!*16!) 601 080 390 って事か Σ M C n =2^M って事になるんだな 328 名前：デフォルトの名無しさん mailto:sage [2006/03/02(木) 18:39:51 ] で 32個中16個の組み合わせ　は　32!/(16!*16!) なのに >>317の方法は　 順列　で　32!/16!　という事で、16! の重複があるから、なんか重そうに見えるという事？ 329 名前：デフォルトの名無しさん [2006/03/03(金) 07:29:43 ] 配列のソートではなく、上位2者と下位2者を高速にシークするアルゴリズムを教えて＞＜ 330 名前：デフォルトの名無しさん mailto:sage [2006/03/03(金) 07:50:10 ] var max1,max2 min1,min2; max1:=data[0]; max2:=data[1]; if max2> max1 then swap(max1,max2); min2:=max1; min1:=max2; for i:=low(data)+2 to High(data) do begin 　 if data[i] > max2 then begin 　 　if data[i] > max1 then max1:=data[i] else max2:=data[i]; 　 end; 　 if data[i] < min2 then begin 　 　if data[i] < min1 then min1:=data[i] else min2:=data[i]; 　 end; end; こんな感じでは？ 331 名前：デフォルトの名無しさん mailto:sage [2006/04/18(火) 07:42:35 ] いわゆる○×。ただし、ちょっと特殊。 ban(0) ban(1) ban(2) ban(3) ban(4) ban(5) ban(6) ban(7) ban(8) //盤面　位置関係はこんな感じ turn //ターン数　最初は1 プレイヤーＡのターン開始 ↓ Ａが指定しかつその場所に当たる変数（真ん中ならban(4)）が0であるならばそれに（turn×１０）＋プレイヤーの番号 （Ａは１、Ｂは２とする。）を代入。 ↓ turn>6ならば、次のことを行う。 　banの中で下１桁がプレイヤーの番号と等しいもののなかで、一番小さいものに0を代入 ↓ banに縦横斜めに自分の番号が並んでいるならば勝利 ↓ turnに１を足し、Ａのターンを終了、Ｂのターンになる。 で、できるだけ強いCOMのアルゴリズムを考えてほしいのです。 お願いします。 332 名前：デフォルトの名無しさん mailto:age [2006/04/18(火) 13:54:18 ] あぶらあげ 333 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 16:23:12 ] >>331 ゲーム木使って実際に解いてみたら。 EXPTIME完全か知らんが、3×3ぐらいなら解けるだろ。 終盤6個そろってからの場合の数は 9*8*7*6*5*4 = 60480 回転と対称で重なるものを除くと 60480/8 = 7560 リーチがかかってかつ自分の手番のような自明な場面を除けばもっと少なくなる。 自分の手番でダブルリーチをかけられる状態であれば勝ち。 双方最善を尽くしたとき、ループに陥れば引き分け。 334 名前：デフォルトの名無しさん mailto:sage [2006/04/22(土) 17:08:22 ] 消してから勝利判定だとダブルリーチにならないんじゃない？ 335 名前：デフォルトの名無しさん [2006/05/22(月) 17:26:54 ] 楕円近似ライブラリなんてありまつか？ 336 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 17:37:12 ] 楕円近似というのは　 １、点列を楕円の一部として近似する事 ２、楕円の周長を近似計算する事 どっち？１はとても難しい　円ならまだ方法があるが 337 名前：デフォルトの名無しさん [2006/05/22(月) 17:56:27 ] ＞１、点列を楕円の一部として近似する事 これをやりたいです。 338 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 18:20:03 ] 円なら　 ttp://www.tensyo.com/urame/prog/linealgo.htm ここの円弧推定が良い方法だと思える。 普通は、円との誤差を　ｓ＝√｛（ｘ−ｘ0）^2 ＋（ｙ−ｙ0）^2｝−ｒ 　と置くが これだと非線形で解かなければならない。 （ｘ−ｘ0）^2 ＋（ｙ−ｙ0）^2−r^2 とすれば数値解が簡単に求まるというものだ。 楕円の場合は、検索すれば出ると思うが、円よりさらに厄介だ 339 名前：AVL木 [2006/05/22(月) 20:52:10 ] 18,7,35,13,16,10,40,21,22,50,46,3,5　　を からっぽのAVL木に入れていくとどうなりますか？誰か教えてください。 340 名前：デフォルトの名無しさん mailto:sage [2006/05/22(月) 21:41:44 ] 教科書読め 341 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 18:54:44 ] 繰り返し二乗法のプログラムをご教授お願い出来ますでしょうか？ 342 名前：デフォルトの名無しさん mailto:sage [2006/05/25(木) 20:20:09 ] デジタル回路の閾値関数を考えたのですが、既知ですか？ f:=x->cos(PI/2*x)^2 f(f(f(x))), x=-0.5..1.5 343 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 01:36:13 ] >>335 Direct least-squares fitting of ellipses Andrew W. Fitzgibbon, Maurizio Pilu, and Robert B. Fisher IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5), 476--480, May 1999 research.microsoft.com/~awf/ellipse/ research.microsoft.com/~awf/ellipse/ellipse-pami.pdf 一応 Java 実装もあるけどコードがちょっと汚いかも。 344 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:01:36 ] fla板から来ました以下の解答お願いします。 プレーヤの歩いた軌跡が、あらかじめ引いてある直線にどれくらい近いかを数値化するにはどうしたらいいでしょうか？ (x,y)座標を取って計算をすればよいらしいっていうのはなんとなくわかるんですが 具体的にどういった計算をすればいいかご教授願います ちなみに最小二乗法だと、 ＼ ／ ＼ ／ このように蛇行した場合も直線に近似されてしまうのでダメですよね・・・ 345 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:26:48 ] >>344 軌跡が直線に近いってのは、どういうこと? 346 名前：デフォルトの名無しさん mailto:sage [2006/07/28(金) 23:37:46 ] >>344 最小二乗法で相関係数みりゃいいだろ。 347 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 00:13:17 ] >344 数値を求めたいんだろう？ 最後の行が意味不明だぞ 348 名前：344 mailto:sage [2006/07/29(土) 00:16:20 ] >>345 www.uploda.org/uporg461782.gif この画像のように、どれだけ直線に近い動きをしたか、ということを 直線との接触時間などからではなく、座標から軌跡と直線との近さを計算したいのです。 >>346 相関係数ですか、調べてみます ありがとうございます 349 名前：デフォルトの名無しさん mailto:sage [2006/07/29(土) 15:15:39 ] もしかして、344は「軌跡から最小自乗法で直線を求めて、与えられている直線と比較する」とか考えているのだろうか。 「軌跡と与えられた直線の距離の自乗を最小にする」でいいんじゃないの？ 350 名前：デフォルトの名無しさん mailto:sage [2006/08/10(木) 08:08:24 ] あらかじめ引いてある直線が X 軸に合うように回転させて Σ(Yi^2)/N とか 軌跡の2次モーメントとか 351 名前：デフォルトの名無しさん mailto:sage [2006/09/15(金) 13:37:19 ] 軌跡に沿って所与の直線との距離を積分すればいいじゃないの。 352 名前：デフォルトの名無しさん mailto:sage [2006/09/16(土) 00:36:41 ] 随分とまた遅い進行だな 353 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 22:34:05 ] ベクトルを正規化する式は float x, y, z;//元のベクトル float vx, vy, vz;//正規化したベクトル float s; s=sqrt(x*x+y*y+z*z); vx=x/s; vy=y/s; vz=z/s; で求まると思いますが、sqrtを使わずに正規化するにはどうすればいいのでしょうか？ どうしても速度が気になります。 自分でも考えてみましたが分かりませんでした。よろしく御願いします。 354 名前：age mailto:age [2006/10/18(水) 22:38:49 ] age 355 名前：デフォルトの名無しさん [2006/10/18(水) 23:04:16 ] f(u0,v0)= ΣΣf(uk,vl)C(uk-u0)C(vl-v0) k l ここで C(x)= 1-2|x|^2+|x|^3 (0<|x|<1) 4-8|x|+5|x|^2-|x|^3 (1<|x|<2) 0 (2<|x|) 3次補間法の計算式なのですが，どのようにプログラムで書いたら良いのでしょうか? 356 名前：デフォルトの名無しさん [2006/10/19(木) 00:02:01 ] >>353 >どうしても速度が気になります。 本当に気になる速度なのかどうか、まず実測してみたらどうでしょう。 sqrtを使わなければできないと思いますけど。 本当にsqrtが速度的にネックであれば、高速のsqrtを自前で作るとか。 ただし、精度を犠牲にしてのことですけど。 Newton法でのsqrtの近似の場合、ループは高々20回くらいです。（誤差1.0e-15で） まずは実測です。 357 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 00:08:31 ] 脳味噌ぶら〜んにでも行って速そうなの探してこいよ。 358 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 01:37:21 ] >353 まず環境晒そうや。 CPU、使用言語、必要精度、それらの情報も無しでアドバイスなんて出来ん。 359 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:20:45 ] >>356 精度にもよるけどせいぜい３−５回ぐらいじゃなかったか？ 20回もまわすか。 360 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:52:10 ] double sqrt(double x) { double a = 1.0; double eps = 1.0E-10; /* 精度 */ while (abs(a * a - x) > 1.0E-10) { a = 0.5 * (a + x / a); } return a; } 361 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 10:56:57 ] >>353 www.google.co.jp/search?q=fast%20sqrt 362 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 12:32:48 ] >>360 そのコードで３−５回 1.0E-15で9回ってところ 確かに20回もありえるけど、極端な言いぐさは信用されないな。 363 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 13:16:19 ] >>360 Intel系ならニュートン法使うより、素直に浮動小数点命令を使った方が速いだろ。 SSE乗ってるならaddss/mulss/rsqrtps辺りでまとめて計算できるし。 364 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 13:44:45 ] >>355 その計算式のままだと思うけど… アルゴリズムの入力と出力は理解できてる? (入力は格子状の標本点における f の値 (二次元の double 配列) と補間すべき点の座標 (u0, v0) で、出力は (u0, v0) における補間値) 365 名前：デフォルトの名無しさん [2006/10/19(木) 16:36:19 ] 式は分かってるんですがプログラムにできないんです・・・ 366 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 17:01:18 ] >>365 具体的なコードが欲しいなら 具体的な入力形式を指定した方がいいと思うよ。 (これは大学の宿題か何かですか?)

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef