プログラミングの為の数学と算数 vol.2

1 名前：デフォルトの名無しさん [04/09/05 16:22] プログラムに必要な数学、算数に関する話題について 語りましょう。TIPS/Q&Aスレです。 756 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 16:07:10 ] >>753 それは、　ズレを最小にする円があるかどうかの問題になるんじゃないのか？ 指定された円とのズレという量があればそれを最小にする半径、中心も求められるわけで・・・ それとも何か素晴らしいアイデアをお持ちで？ 757 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 16:33:07 ] >>756 だから「ズレている」を定義してくれと言ってるんだけどな。 一点に集中してても「ズレてない」とするなら残差自乗で十分だし、 そうでないならより輪郭線抽出などの手法が要るかもしれない。 758 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 16:37:32 ] 欠点はあるが 簡単な定義は>>752くらいしか無いだろう？ もう少しややこしくするなら、点同士がどれだけ中心からの角度で分散しているかの数値を入れるかい？ 759 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 16:44:25 ] なんとなく想像だけど、手書きの丸と円のずれ具合を定量化したいんじゃないのかな? だとすれば>750で充分だと思うのだけど。 #目的も判らずに数学的な意味を見出そうとしても虚しいばかりだ。 760 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 16:52:34 ] ドットを数えるってどうやるの？ 761 名前：ラジアンの比較で躓いてます mailto:sage [2007/03/29(木) 16:57:43 ] 別スレで pc11.2ch.net/test/read.cgi/tech/1175129517/9 の質問をして、最終的にこちらに誘導されてきました。 質問の回答として、以下のコードを教えてもらいました。 v1 … p1→p2 のベクトル v2 … p2→p3 のベクトル struct point { double x, y; }; bool isJustLeft(point v1, piont v2) { double corssProd = v1.x * v2.y - v1.y * v2.x; //外積 double norm1 = v1.x * v1.x + v1.y * v1.y; // |v1|^2 double norm2 = v2.x * v2.x + v2.y * v2.y; // |v2|^2 if( corssProd < 0.0 ) return false; // 時計回りはダメ if( crossProd * crossProd == norm1 * norm2 ) return true; // 直角判定 return false; } でも、ベクトルの外積って通常3次元のベクトルを返しますよね。上記だと > double corssProd = v1.x * v2.y - v1.y * v2.x; //外積 とスカラー値を返しているのですが、今一つやっている意味が判りません。 yuki.to/math_cgi/prybbs.html?log=3&mode=res&no=36824 ぐぐったらこんな掲示板見つけたけど、回答者の答えがイマイチ判りません。 コードを通して、ベクトルを理解したいのですが、誰か教えてもらえませんか？ 762 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 17:08:28 ] v1,v2の外積の結果は、その２つに直角な方向ですが、 v1,v2が平面上なのでZ成分のみとなります。　だから省略したのでしょう 763 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 17:24:43 ] 外積の定義って曖昧というか、人によって違うというか。 1つは、>>762 の言うように、3次元ベクトルの外積の考え方を使って、 (x1, y1, 0) × (x2, y2, 0) = (0, 0, x1 y2 - x2 y1) の z 成分のみを取ったもの。 もう1つは、n 次元のベクトルは、n - 1 本あれば、それらに垂直なベクトルが決まるので、 n - 1 本のベクトル → 1 本の n 次元ベクトルを求める演算を外積と呼ぶ。 こっちの流儀だち、2次元ベクトルの外積は1本→1本の演算になって、 「積」というとちょっと微妙。 まあ、x1 y2 - x2 y1 は、外積の値というか、 符号付面積、あるいは行列式よね。 3次元ベクトルの外積は、その絶対値が符号付面積になってるから、 その類推で、2次元ベクトル2本の貼る平行四辺形の符号付面積を外積と呼ぶのかも。 764 名前：ラジアンの比較で躓いてます mailto:sage [2007/03/29(木) 17:36:19 ] >762 なるほど・・・時計回りだとZ値が下方向 反時計回りだと上方向になる性質を利用して、 Z値だけで判断すればいいという事ですね！！ 765 名前：ラジアンの比較で躓いてます mailto:sage [2007/03/29(木) 17:39:31 ] もうひとつ質問ですが、ここは何をやっているのでしょうか？ double norm1 = v1.x * v1.x + v1.y * v1.y; // |v1|^2 double norm2 = v2.x * v2.x + v2.y * v2.y; // |v2|^2 766 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 17:47:02 ] >>765 え、えっと、変数名もnormだし、コメントもnormだし、normを計算しているんじゃないかなあ。 767 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 17:53:54 ] 直角であるかどうかは　内積x1*x2+y1*y2 が0になる事 (v1.x * v2.y - v1.y * v2.x)^2 -(v1.x * v1.x + v1.y * v1.y)*( v2.x * v2.x + v2.y * v2.y) を変形してくと・・・・ って内積計算した方が計算量少ないかもしれないが まあ、折角　外積計算したからって所じゃないのかな 768 名前：ラジアンの比較で躓いてます mailto:sage [2007/03/29(木) 18:03:57 ] >766 一瞬正規化？とか思っちゃいましたが、「ノルム」でしたか・・・orz 769 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 18:19:33 ] ＞「ノルム」 って日本語の数学では何だっけ？ 770 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 18:27:37 ] 世の中には日本語の数学と英語の数学があるらしい。 771 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 18:37:01 ] 定まった和訳は無く、日本語をあててる本も特に知らないなあ。 参考までに、中国語では「范数」と書くそうな。 772 名前：デフォルトの名無しさん mailto:sage [2007/03/29(木) 18:41:31 ] >>769 ノルムはノルムじゃない？ 数学用語としてじゃなくて、一般には基準とか模範って訳すけど。 ノルムに似たので（というか、絶対値の一般化）付値ってのがあるけど、 それは英語でも valuation。 773 名前：デフォルトの名無しさん mailto:sage [2007/03/30(金) 08:56:16 ] 則（のり）じゃなかったか？ 片方を９０度回転したベクトルで内積をとっても、時計回り判定はできる。 ９０度回転操作を (x, y) → (-y, x) とすると、外積とコメントされた式と同じになる。 好きな方で解釈するといい。 774 名前：デフォルトの名無しさん mailto:sage [2007/03/30(金) 09:20:27 ] 内積外積を使わなくてもこれは解ける 片方のベクトルが水平(y成分が0)になるように回転変換し、 もう一方のベクトルのx成分が0なら垂直で y成分の符号を見ればいい でも、それが内積と外積になっちゃうんだけどね 775 名前：デフォルトの名無しさん mailto:sage [2007/03/30(金) 11:56:04 ] プログラミングの学習を先にはじめて、その必要に迫られて その都度、数学の教養を身に着ける順序でも遅くなくねえ？ 問題集をひたすら解くだけの抽象的な数学の本ばかり読んで いると、生きることの意味がわからなくなってくるよ。 776 名前：デフォルトの名無しさん mailto:sage [2007/03/30(金) 11:57:48 ] 既出でしたら、ごめんなさい 半径１０センチの球表面の座標(XYZ)をファイルに出力したいと考えております 点の間隔は0.1センチぐらいでいいかな、と ファイルに落とす部分は、わかっているんですが 座標を算出するアルゴリズムが、さっぱりわからなくて お分かりになる方、御教授いただけると助かります 777 名前：デフォルトの名無しさん mailto:sage [2007/03/30(金) 12:20:47 ] >>755 それが許されればな。 >>756 3次元空間なら x^2 + y^2 + z^2 ＝ 半径^2 を満す実数だったと。 ざっぱになら x と y で for ループ回しながら z の値を算出すすとか。 もしくは 三次元空間の極座標 x = 半径 * sin(th1) * sin(th2) y = 半径 * sin(th1) * cos(th2) z = 半径 * cos(th1) 解説： hp.vector.co.jp/authors/VA030421/fdd06.htm で角度(th1, th2)でループまわすことも考えられる。 角度で回すのなら、球面三角法 ja.wikipedia.org/wiki/%E7%90%83%E9%9D%A2%E4%B8%89%E8%A7%92%E6%B3%95 も見おくべし。 778 名前：776 mailto:sage [2007/03/30(金) 12:56:17 ] >>>777 ありがとうございます。できたっぽいです たすかりました 779 名前：デフォルトの名無しさん mailto:sage [2007/03/30(金) 20:41:06 ] そのような極座標だと、目の細かい場所と粗い場所ができないか できてもさしつかえないならいいけど、もしさしつかえあるなら ユニバーサルメルカトル図法みたいな雰囲気で局所座標系を とったりするとよさそうな気が 780 名前：デフォルトの名無しさん mailto:sage [2007/03/31(土) 01:53:29 ] 等間隔にするならジオデシックスフィア（日本語でなんて言うのか知らん）の頂点として出すとか 781 名前：デフォルトの名無しさん mailto:sage [2007/03/31(土) 02:39:25 ] まあ、やっぱり極付近ほど密になるけど、↓みたいなのはある。 www.cubido.at/Blog/tabid/176/EntryID/86/Default.aspx ジオデシックドームの頂点求めるんだたら↓これ？ www2.tokai.or.jp/tomo-kun/readmeJ.html 782 名前：デフォルトの名無しさん mailto:sage [2007/03/31(土) 04:54:50 ] 正２０面体に重心細分を繰り返して得られる多面体とかではどうかね 783 名前：デフォルトの名無しさん [2007/04/11(水) 11:07:50 ] 自由な曲線（ベジェ曲線か、折れ線の点列）を円弧のあつまりで近似したいんですが、 ヒントはないでしょうか？ 784 名前：デフォルトの名無しさん mailto:sage [2007/04/11(水) 11:16:08 ] 円弧は半径が決まっているの？　つまりフライスのようなので削るというような場合？ 単純に円弧で近似したいのがどういう状況か判らないのだけど 曲線の場合は、微分が一致するように接続してゆけばいいのだけど 円弧の場合は２点と半径で求まってしまうので、 どうやっても接続点が尖がってしまう 785 名前：デフォルトの名無しさん mailto:sage [2007/04/12(木) 00:12:15 ] 円弧と線分ならどうにかそれっぽくなるかも 786 名前：デフォルトの名無しさん mailto:sage [2007/04/12(木) 08:40:07 ] 円弧の半径に制限無かったら、無限小の円弧になるだけだろ。 787 名前：デフォルトの名無しさん mailto:sage [2007/04/13(金) 04:39:53 ] 無限小の円弧の集合では曲線は近似できないのでは。 788 名前：784 mailto:sage [2007/04/13(金) 06:06:45 ] まてよ。 接続点で中心の方向が一致すればいいと解けば 接続点が尖らないように出来るか　 789 名前：デフォルトの名無しさん mailto:sage [2007/04/13(金) 06:16:25 ] >>788 　） （ 　） （ こういうこと？ 790 名前：デフォルトの名無しさん mailto:sage [2007/04/13(金) 13:54:27 ] 円弧も極小の長さで繋いでゆけばどんな曲線でも表現出来るし、 直線も半径を限りなく大きな値にすれば可能っぽいね。 適当に曲線から３点抽出して、３点を通る円を求めればいいんじゃね？ 必要精度に達していなければ間隔を短くし、足りてれば長くして情報量を落とせばいけそう。 791 名前：デフォルトの名無しさん mailto:sage [2007/04/13(金) 20:32:08 ] 半径無限大に飛ばせば曲率ゼロだしな。 792 名前：デフォルトの名無しさん mailto:sage [2007/04/14(土) 00:14:38 ] よくあるフォームの座標系を 0｜ ―＋―――→x 　｜ 　｜ 　↓ y を、 　 y 　 ↑ 　 ｜ 　 ｜ ―＋―――→x 　0 | に変換する行列教えてください。 793 名前：デフォルトの名無しさん mailto:sage [2007/04/14(土) 00:26:24 ] 1, 0; 0, -1 794 名前：デフォルトの名無しさん mailto:age [2007/04/14(土) 15:36:47 ] >「network.standard-url.escape-utf8」を「false」にしてください。 >about:configで「network.standard-url.encode-utf8」を「true」にします。 上記の設定で、無事、日本語になりました。 気になるのは、IE7では、『"』⇒『"』でしたが、 forum.mozilla.gr.jp/?mode=new&no=0&X='国際化' forum.mozilla.gr.jp/?mode=new&no=0&X="国際化" FireFox2では、『"』⇒『%22』になっていました、少々オシイです。 forum.mozilla.gr.jp/?mode=new&no=0&X='国際化' forum.mozilla.gr.jp/?mode=new&no=0&X=%22国際化%22 『%22』を『"』に戻す作業が残ってしまいます。 共通化としてOpera9の国際化URL設定も分かると良いと思います。 795 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 10:03:30 ] 数学的要素が少ないプログラムの分野は何ですか？ ゲームプログラムは数学的要素満載だと思うのですが。 796 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 10:46:25 ] 事務web系 797 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 13:57:03 ] >>795 どんな分野であっても、ｽﾚﾀｲが読める程度の日本語力は必要。 798 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 21:51:26 ] >>796 事務web系って何ですか？ 799 名前：デフォルトの名無しさん mailto:sage [2007/04/18(水) 22:46:08 ] 全国の支社から出退勤のデータを収集して給与を計算するとか ネット通販の注文を受け付けて倉庫に発送を指示するとか 800 名前：デフォルトの名無しさん mailto:sage [2007/04/19(木) 02:44:55 ] そういうのって地味だから長く働けそうですね。 801 名前：デフォルトの名無しさん [2007/04/19(木) 02:48:30 ] 追記 出来るだけ長く働ける分野が良いんです 802 名前：デフォルトの名無しさん [2007/04/19(木) 11:29:46 ] 息子が大学に行く直前まで働ける職種でおk？ 803 名前：デフォルトの名無しさん mailto:sage [2007/04/19(木) 11:38:45 ] 数学、算数はプログラムに必要か？ pc11.2ch.net/test/read.cgi/tech/1171457185/ を汚した奴だろ？ あちこち汚してゆくような奴が奴隷の待遇の上下を聞いたって嫌われるだけだろうに 804 名前：デフォルトの名無しさん mailto:sage [2007/04/19(木) 23:48:04 ] 就職先探すのとかは完全にすれ違い。帰れ。 805 名前：デフォルトの名無しさん mailto:sage [2007/04/21(土) 06:19:39 ] >>802 あなたの息子を舐め舐めしますよ 806 名前：デフォルトの名無しさん mailto:sage [2007/04/21(土) 09:01:30 ] 　これから数学の勉強始めてみようと思ってるんだが、プログラミングに役立つ 勉強方法が知りたい。大学受験レベルの数学問題をひたすら解くのがいいのか、 公式を理解しつつ大学レベルの数学を勉強するのがいいのか。 どんな風にすればいいか教えてください。。。。。 807 名前：デフォルトの名無しさん mailto:sage [2007/04/21(土) 09:31:49 ] 大学レベルの数学もいろいろあって、いまのあなたの プログラミング・数学の能力と、役立てようとしている 方面によって勉強すべきものは変わる。 目的に近いところを読んでから、不足してそうな部分を 適宜補うってのが順当なごく普通の勉強の仕方。 どんなのがやりたいか言ってくれれば本などは紹介するよ。 因みに受験レベルの数学は単純計算すら覚束ないなら 仕方が無いけれど、そうでなければやる必要なしと思う。 808 名前：デフォルトの名無しさん mailto:sage [2007/04/21(土) 16:00:13 ] > プログラミングに役立つ勉強方法が知りたい。 これは例えるなら「スポーツに役立つ練習方法を知りたい」と言ってるようなもの。 スポーツの種目によって練習方法が違うように、プログラミングの分野によって役立つ 数学の分野も違う。 # プログラミングで飯を食っていきたいなら、数学より簿記でもやった方が潰しがきくような気がしないでもない。 809 名前：806 mailto:sage [2007/04/22(日) 13:35:06 ] >>807-808 レスサンクス。 プログラミングはCの基本的な文法を理解している程度で、数学に関しては 高校レベルもｻﾊﾟｰﾘな状況です。 簿記の知識って業務系だとそんなに役に立つのか。。。。 それなら一応日商の簿記一級を持ってるんで、この知識を生かして業務系に 進んだほうがいいのかなと思ってるんだが、 「生涯現役でプログラマなんだぜ？」 な漏れとしては組込み系や制御系のほうがいいのかなと考えたり、、、 今現在はどの分野にいこうか迷ってるところです。 どうやらプログラミングに必要な数学は各分野ごとにまちまちで、漏れの やりたいこと自体もまだ定まってないので、とりあえず高校レベルの数学を 勉強する。そしてその時の勉強法としては大学受験を目指す感じのやり方 じゃなく、基本的な公式を理解する程度でよいってことでFA？ 810 名前：デフォルトの名無しさん mailto:sage [2007/04/22(日) 21:45:37 ] 人に分からないことは全く問題ないけど、 全部頼るのは良くない。 自分で決める、たぶんそれが一番大事だ。 811 名前：デフォルトの名無しさん mailto:sage [2007/04/22(日) 22:39:13 ] ＞人に分からないことは全く問題ないけど、 日本語でOK。 812 名前：デフォルトの名無しさん mailto:sage [2007/04/24(火) 00:45:08 ] 進路相談は完全に板違いなんでとっとと消えろな 毎年毎年現れる上に、人によって状況が違うし、いちいち答えてたらキリが無い 813 名前：全知全能者 [2007/04/25(水) 05:10:58 ] いつの世も物を言うのは「力」だ。 原始時代は「筋力」 江戸時代は「家柄」 そして現代は「金」 現代社会では金を持っている人間が強い。 革新的なパラダイムの転換が無い限りこの価値観は変わらない。 814 名前：デフォルトの名無しさん [2007/04/25(水) 15:49:14 ] そして、この先は『人柄』が力となる。 815 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 00:22:43 ] ピクセルのフェード計算についての質問をさせてください。 実行したいのは以下の式です。 // dst[0 〜 255]: 転送先ピクセルの色要素) // src[0 〜 255]: 転送元ピクセルの色要素) // rate[0 〜 255]; srcの比率 ) // (すべてbyte型です) // フェード式 　= (dst * (255 - rate) + src * rate) >> 8; 　~= dst + (((src - dst) * rate) >> 8); 　　(~= はﾆｱﾘｰｲｺｰﾙです) これを実現するために以下のような計算方法がよく使われています。 1) short tmp = (short)src - (short)dst; //< 符号付き２バイト数に拡張します 2) tmp = (short)(tmp * rate); //< 演算結果の下位２バイトを結果として受け取ります 3) tmp = (word)tmp >> 8; //< 無符号型としてシフト() 4) byte result = (byte)(dst + (byte)tmp); //< tmpの下位１バイトのみを足し込みます これだけ見ると変に複雑に見えますが、 実は計算にはmmxを使っていて４要素まとめて演算します。 そこで、１要素につき２バイトの範囲内で (src - dst){-255 〜 255} * rate{0 〜 255} の符号付き乗算をしないといけないため、このようなことになっています。 816 名前：815 mailto:sage [2007/04/29(日) 00:24:22 ] >>815の続きです^^ 例えば、src=0, dst=255, rate=255の場合、 結果としては０が期待されますが、実際に計算してみると 1) tmp = -255 = 0xff01 2) tmp = (short)(0xff01 * 0xff) = (short)0xfff01ff = 0x01ff 3) tmp = 0x01 4) result = (byte)(0xff + 0x01) = 0x00 となり正しい結果が得られます。 また、src=200, dst=225, rate=200の場合は、 204程度が望まれますが、実際に計算してみると 1) tmp = -25 = 0xffe7 2) tmp = (short)(0xffe7 * 0xc8) = (short)0xc7ec78 = 0xec78 3) tmp = 0xec 4) result = (byte)(0xe1 + 0xec) = 0xcd = 205 とほぼ正しい結果が得られます。 上の式は有名なライブラリで使われている式でもあり、 正しいことはほとんど保証されているのですが、 これがなぜ正しいのか証明できる方はいませんか？ 少なくとも自分には理解できないです。 文献でもいいです。よろしくお願いします。 817 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 00:48:54 ] >>815 どうしてもなにも、定義そのままの計算式じゃん。 > 1) short tmp = (short)src - (short)dst; //< 符号付き２バイト数に拡張します (src-dst) は、-255〜+255 なので、short に納まる。 > 2) tmp = (short)(tmp * rate); //< 演算結果の下位２バイトを結果として受け取ります (src-dst)*rate は、-65280〜+65280 なので、2の補数で17ビット必要→shortだと1bit足りない→後述 > 3) tmp = (word)tmp >> 8; //< 無符号型としてシフト() ((src-dst)*rate)>>8 は -255〜+255なので、2の補数で9ビット必要だが、2)の時点で9ビット目の情報は落ちている > 4) byte result = (byte)(dst + (byte)tmp); ここで、8ビット整数で計算するのだから、上記3)の所で、結果は8ビットあれば十分。9ビット目の値は要らない。 8ビットで演算するのに「-1(0xff)を足す」のも「255(0xff)を足す」のも、まったく同じ結果になることに気付けばOK。 3)の結果で、-255 が出てきたのを、+1 として処理してもまったく問題ない。 → -255〜-1 を +1〜+255 で処理しても結果は同じ。 818 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 14:31:47 ] >>817 おお！ ８ビットまで精度を保証すればうまくいくってことね^^ どうもありがとう 819 名前：デフォルトの名無しさん [2007/04/29(日) 18:19:52 ] 数学の知識はそりゃあった方が良いと思うけど、 一番大事なのは物事を合理的に考える事が出来るか。 820 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 19:08:45 ] 合理的に考えれば2chで質問するほど無駄なことは無い訳だが 821 名前：デフォルトの名無しさん [2007/04/29(日) 19:46:50 ] 自由な曲線（ベジェ曲線か、折れ線の点列）を円弧のあつまりで近似したいんですが、 ヒントはないでしょうか？ と、質問した者です。 点列が１個の円や直線にフィットするかどうかは、最小二乗法などで、 解決できると思います。 したがって、どういう風なグループで円弧や直線にすると、さらに最小になるか、 という問題になるような気がするのですが、そういう問題には、どのような考え方で臨めばよいでしょうか。 822 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 20:18:42 ] やりたい事が判らないから困ってしまうのだけど、 円は３点で決まるから、３点毎に円弧を描いても、近似と言い張れば近似になる。 823 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 20:40:03 ] ４点あるときにどの３点を選んで円弧にするかっていう話？ 824 名前：デフォルトの名無しさん mailto:sage [2007/04/30(月) 01:30:11 ] 円弧だけじゃなくて、適宜直線も使いたいってことかい？ 825 名前：デフォルトの名無しさん [2007/05/02(水) 18:06:14 ] たとえば、N点（３０００点とか）からなる折れ線の図形があったとして、人間は図をかけば、適度にこの部分は円弧だろうとか、直線だろうとか、あてはめることができます。 それを、精度をあたえることで、コンピュータに計算で円弧＋直線に解かせられないでしょうかね。 826 名前：デフォルトの名無しさん mailto:sage [2007/05/02(水) 18:27:41 ] 使う円弧の数に制限が無いのなら、>>822の方法で指定点での誤差ゼロで描ける 使う円弧の数を減らしたいという要求があるなら 単純に端から３点でフィッティングして、次の点が誤差の範囲内ならと処理してもいいし 最小２乗円を求めては、誤差の範囲が収まるならとやってもいいとおもう ただし、誤差だけでは、つなぎ目がガクガクに見えるという事になる だから、それが嫌なら、点との誤差が幾ら以内で、接続が滑らかであるというような条件を追加しないといけない 827 名前：デフォルトの名無しさん mailto:sage [2007/05/02(水) 19:42:29 ] >>825 用途を書いてくれればもう少し具体的なアドバイスが出てくると思われ 828 名前：デフォルトの名無しさん mailto:sage [2007/05/02(水) 20:19:07 ] >>825 滑らかじゃなくていいなら既に色々レスついてるからそれ参照。誤差ゼロ。 滑らかである必要があるなら、確かに精度(許容誤差)を与える必要はあるだろう。 滑らかって何とか言うならもっと勉強しなさい。 829 名前：デフォルトの名無しさん mailto:sage [2007/05/04(金) 00:50:19 ] ペゾルドにかいてなかったっけ？ 830 名前：デフォルトの名無しさん mailto:sage [2007/05/15(火) 23:20:02 ] ttp://www.emit.jp/prog/prog_div.html の高速除算なのですが、 どうしてこれで正しく計算できるのか分かる方いませんか？ あと、割られる数が負数のときでも上手くいくような つまり X / D = Q (Qは整数) のときに -X / D = -Q となるような高速除算の方法を知っている方はいますか？ 831 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 01:13:49 ] 830のリンク先はなーんか誤差が出そうなやり方だなー。 定数除算なら、誤差項を１ビット誤差以下に抑えればいいから、こういうことは出来るけど。 32bit同士の乗算がオーバーフローせずに使える場合。 X/3 = [X/3 + 2n/(3*2^32)] (∵ 2n/(3*2^32) < 1bit ) = [ (2^32 + 2)/3 * (n/2^32) ] = 1431655766 * n / 2^32 = 1431655766 * n >> 32 832 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 01:16:49 ] あ、途中でXがnになっちまった……。 nが負なら最後に１足してくんなまし。 833 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 07:36:56 ] >>830 Web上にある情報を、どれも正しいと思うな Q＝trunc(X/D +0.5) と計算したい筈なのに m = 2*n-------------------1) R = (2^m - 1) / D ---------2) Q = (R * X + 2^n) >> m ------3)　　から>>m を２のベキに変更して Q = (R * X + 2^n)/2^m　　　Rに代入して Q = ((2^m - 1) / D * X + 2^n)/2^m Q = (2^m - 1) /2^m * X/ D + 2^(n-m) 　　　~~~~~~~~~~~~~~~~　　　　　　~~~~~~~ (2^m-1)/2^m　は１ではない 2^(n-m)　は 0.5 ではない これは単に使いたかった範囲で巧くいっただけだろ 834 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 11:48:36 ] >>831,832 ありがとうございます。 一応、プログラムを組んで実験してみたのですが、 違う結果しか得られませんでした。 自分の理解が足りていないのかもしれません。 チェック用プログラムをアップしますので、確認していただければ幸いです。 kissho.xii.jp/1/src/1jyou6388.lzh >>833 整数における割り算なので、やりたいのは四捨五入ではなく切り捨て、 つまりQ＝trunc(X/D) です。 あと、使える値の範囲も>>830のページ上に書いてありますよ。 835 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 16:28:10 ] >>834 831に書いた方法は、 R=(2^32 + F)/Dのとき、F=D-1では、多くのDで誤差が出る。 大事なのはRが割り切れることと、F/2^32が1bitより小さい正の値になること。 これが満たされない場合は、 R=(2^33+F)/Dとか、R=(2^34+T)/D-2^32なんかを使う必要がある。 (おまけに最後の例は最後に2^32分の補正が必要) 以上のようにR の決定がそんなに単純じゃないんだー。 だから定数除算って書いた。 っていうかハッカーのたのしみって本を買えばこういうことが書いてある。 興味あるならオススメ。 836 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 17:04:05 ] >>830 swox.com/~tege/divcnst-pldi94.pdf > Division by Invariant Integers using Multiplication > > 4 Unsigned division > 5 Signed division, quotient rounded towards 0 > 6 Signed division, quotient rounded towards -∞ 837 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 18:06:56 ] ターゲットのチップにも寄るだろうけど、Intel系でって話なら普通に割り算命令使った方が速いんじゃね？ 838 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 18:13:07 ] >>837 実測してみないとなんともだけど割り算の結果を遅延評価するといいかもね。 839 名前：デフォルトの名無しさん mailto:sage [2007/05/16(水) 23:59:10 ] >>835 そうなんですか^^ ハッカーの教科書は持っていたのですがこんな話題があるとは知りませんでした。 ちょっと研究してみようと思います。 >>836 そのページを見てみたのですが、正確にやるのは結構大変なんですね^^ よく使う定数の除算のみを最適化して あとはテーブルなりなんなりで処理することにしました。 >>837 pc11.2ch.net/test/read.cgi/tech/1168399966/99- ↑を見て欲しいのですが、x86のdiv命令は おそらくもっとも効率化がめざましい命令の一種です。 最新の石ならばそのままが一番速いと思うのですが、 昔のCPUを考慮するとなかなかそういうわけにもいきません。 840 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 00:08:18 ] >>839 この手の高速化は高級言語で記述してもコンパイラが糞なら無意味だし、そもそも可読性が落ちるので歓迎されない。 そうなるとアセンブラでの記述に限定されるわけだが、肝心のターゲットが書かれていないので議論するだけ無駄。 というかそもそもこのスレ向きの話題じゃない。 841 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 00:55:37 ] なんでいまさら昔のPCのことを考慮する必要があるんだ 842 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 01:26:26 ] >>840 その理屈で行くとハッカーのたのしみや>>836の内容は まったく無意味ってことになりますね。 もちろんそんなことはなくて、 ビット演算やコンピュータ用数学(？)にはある程度の普遍性があります。 だから、ターゲットが明確に決まっていなくてもある程度は意味はあります。 （一応、特定アーキテクチャ専用の話題は避けたつもりなのですが、 div命令のレイテンシの話題はたしかにスレ違いですね^^） >>841 ここでいう「昔のCPU」とは、Pentium4やAthlonXPクラスの (多分)今一番普及しているCPUのことです。 さすがに考慮しないわけにはいかないです^^ 843 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 06:19:35 ] >>842 アセンブラ系スレなら有意義なんだろうが、それ以外の場所じゃ完全に無意味。 ＞ビット演算やコンピュータ用数学(？)にはある程度の普遍性があります。 これもない。現にシフト命令が異様に遅いコアが存在する。 ５年１０年前なら確かにその言い分は通用したが、複雑化したx86系CPUで 除算命令のような数クロックを稼ごうという時にターゲットも指定しないなんてありえないだろ？ 844 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 07:11:01 ] >>843 > アセンブラ系スレなら有意義なんだろうが、それ以外の場所じゃ完全に無意味。 んなことない。定数除算→乗算の最適化をやってくれない環境はあるし、自分 が仕事で使った RISC とかは加減シフトが実効 1 サイクル、乗算が 2 サイク ルに対して除算命令は 33 サイクル（中で何やってるかわかるな。しかも除算 命令実行中に割り込みが入ると割り込み終了後に再度除算命令を実行し直す）。 > 現にシフト命令が異様に遅いコアが存在する。 後学のために教えてくれ。 845 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 07:46:16 ] >>844 だから、それはアセンブラ系のスレでやってくれということでしょ 846 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 08:04:05 ] 負数での符号については423から、同じような事一度やってるからな。 速度だけの問題なら他でやって欲しい所。 847 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 09:09:48 ] >>843 自分がもともと質問していたことは、除算→乗算+シフトの変換方法です。 (このスレのおかげで定数除算の最適化という分野があることを知りましたし、 特定の除算の最適化もできそうな感じです。 その点は本当に感謝しています) 確かに石によって演算速度の違いがあることは事実なのですが、 そういったこともふまえて、対象となるCPUをつらつら挙げて CPU別の最適化方法をここで聞いた方がよかったのですか？ もちろん、自分的には大歓迎なのですが^^ >>846 収穫もあったことですし、自分はそろそろ去りたいと思います^^ 848 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 10:32:12 ] ＞CPU別の最適化方法をここで聞いた方がよかったのですか？ 最適化スレもあればアセンブラスレもあるのに? 849 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 10:51:11 ] 特定のMPUの話じゃなければ充分メタな話出来るだろ…。 そういう命令セットの定義とかも数学の範疇じゃないのか? 850 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 11:24:26 ] >>848 ＞CPU別の最適化方法をここで聞いた方がよかったのですか？ は>>843の ＞除算命令のような数クロックを稼ごうという時にターゲットも指定しないなんてありえないだろ？ に対するレスです。 当然、自分の考えは>>848さんと同じで「それはスレ違いでしょ？」です。 >>849 命令セットの定義が数学の範疇だというのははじめて聞きました。 そうなのかもしれないのですが、 自分は特定アーキテクチャの最適化の話はここでするべきでは無いと考えたのです。 851 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 11:45:33 ] 何がやりたいから判らなくなってるが、ようするに、 R>0 Xは正負のint 範囲で Q＝trunc(X/D) を Q= (int)(((long)X*(long)R + k) >> (long)m ) で計算したいが　適切な R と　m　を求むって事だろ？ 852 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 11:45:45 ] 使える命令とその計算コストを厳密に定義した上で最適な計算を 求める問題ってのは、特に並列計算の分野で見ることがある研究だね。 実際のCPUくらいのコストモデルでやるのはかなり大変だと思うけれど 853 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 11:46:45 ] ｳｻﾞ…スレ違いだって言われてんだから素直に移動しろや。 少なくともここはアセンブラの話題振るスレじゃねえことくらいは理解してんだろ？ 854 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 21:17:53 ] 離散的数の演算は数学だ。 ただ、その実装手段が大抵の場合アセンブラしかないだけ。 CPUの除算が遅いとか言い出したヤツが最初にスレ違い。 855 名前：デフォルトの名無しさん mailto:sage [2007/05/17(木) 23:01:21 ] 車のスピード違反みたいだなｗ 除算は多倍長文字列でやった事あるけど、 別と比べて極端に難しかった。 856 名前：デフォルトの名無しさん mailto:sage [2007/05/18(金) 01:50:28 ] 結局実装の話になると思うけどね。 ここがム板である限り。

---

---

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

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