05/05/31 20:12:29
>>205 2からPまでの全部の*素数の*積+1
だね。
211:デフォルトの名無しさん
05/05/31 20:13:01
あ、整数全部でももkか。
212:デフォルトの名無しさん
05/06/01 04:14:30
２からＰまでの積＋１がＰを整除するって？
213:デフォルトの名無しさん
05/06/02 05:35:26
>>207
原論は昔読んだ事があるんだが・・・
ごめん、あなたの方が正しい気がしてきた。もう一度勉強しなおしてくる。
214:デフォルトの名無しさん
05/06/06 09:52:30
PARIつかえ
215:デフォルトの名無しさん
05/06/06 09:57:55
ユークリッド(Euclid)による素数の無限性の証明の
話がでてるけど余談
エルデシュ(Erdoes) はこの証明を
"The BOOK" すなわち彼が信仰し存在することを
前提としている「究極のエレガントな証明集」の
代表例といっているそうだ
216:デフォルトの名無しさん
05/06/06 10:03:28
また余談
この証明，何かだまされたような気がする人がいるのは
背理法，もっというと排中律を暗黙の仮定としているからだろう．
実際にかつて，排中律を使わずに数学を構成しよう，
という立場の人があらわれた．
より詳しい話は数学の歴史の本を参照してください．
217:デフォルトの名無しさん
05/06/06 16:02:55
普通に高校数学やった人ならわかるっしょ。
218:デフォルトの名無しさん
05/06/06 20:05:18
背理法を使わずに証明できない
つまり廃中立を認めない立場では
素数は有限しかないことないのか
219:デフォルトの名無しさん
05/06/06 20:48:03
>218
背理法使わずに証明できるよ
220:デフォルトの名無しさん
05/06/06 21:19:05
うちの大学の計算機科学の演習が
ひたすら直観主義論理で算術を構成してくっていうやつで
その最後の問題が素数の非有限性だったな
俺は証明できなかったけど
221:デフォルトの名無しさん
05/06/06 23:22:03
数学的帰納法も騙されている漢字瓦斯
てゆーかあれで証明なのかどうか理解できにくい
222:デフォルトの名無しさん
05/06/06 23:56:45
>>221
あれは自然数の公理のうちに入ってる
223:デフォルトの名無しさん
05/06/07 22:46:31
>>222
それを公理に加えちまうってのが、
いかにも後付け的でインチキくせーってことでしょ。
224:デフォルトの名無しさん
05/06/07 23:32:50
>>223
まあ、無限集合を定義するのにどの道必要だし。
225:デフォルトの名無しさん
05/06/08 11:36:09
無限集合は、「自身の内部との一対一対応がある集合」として定義できるよ。
226:デフォルトの名無しさん
05/06/08 21:57:09
>>225
それはつまり、「実数全体からなる集合は、
自然数全体からなる集合と１対１対応が取れる」
ということですか？
227:デフォルトの名無しさん
05/06/08 22:15:03
「任意の内部」ではなくて「ある内部」でしょ
228:デフォルトの名無しさん
05/06/08 22:24:40
おお。濃度の話になっている。
流石にスレ違いのような
229:デフォルトの名無しさん
05/06/09 09:13:05
>>226
それはウソ
実数は可算ではないことが証明できる
有名な Cantor の対角線論法
230:デフォルトの名無しさん
05/06/09 09:17:40
公開問題：
可算の濃度と実数の濃度に間の
濃度を持つ集合は存在するか？
231:デフォルトの名無しさん
05/06/09 10:48:21
>>230
それは「どっちでもいい」で解決したはず
232:デフォルトの名無しさん
05/06/09 14:27:31
>230
上に同じ
233:デフォルトの名無しさん
05/06/10 00:02:39
>>231-232
正確には、ZFC公理系の範囲では否定も肯定もできない。
もうちょっと公理を足せば否定も肯定もできる。
234:デフォルトの名無しさん
05/06/14 10:17:37
公開問題：
ZF公理系の無矛盾性を証明せよ
235:デフォルトの名無しさん
05/06/14 20:52:41
>>230,234
ネタフリ乙！
URLﾘﾝｸ(ja.wikipedia.org)
236:デフォルトの名無しさん
05/06/15 00:34:45
(1)無矛盾でないと仮定する。
(2)仮定により矛盾が導かれる。
(3)故に仮定(1)は否定される。
237:デフォルトの名無しさん
05/07/16 12:47:12
保守
238:デフォルトの名無しさん
05/08/15 13:33:36
何か質問ある？ と保守
239:デフォルトの名無しさん
05/08/20 13:56:07
微分方程式って
まさに再帰アルゴリズムだよね。
240:デフォルトの名無しさん
05/08/20 13:59:47
存在することよりも存在しないことを示すほうが難しいんだから。
背理法
241:デフォルトの名無しさん
05/08/20 14:26:53
悪魔の証明
242:デフォルトの名無しさん
05/08/20 14:44:34
●緊急告知
Googleの「日本海」の表記が韓国からの抗議により「東海」に変更
↓↓↓詳しくはこちら↓↓↓
【日本海】（；＾ω＾）VIP vs VANKlt;`∀´*gt;part8【海戦】
ｽﾚﾘﾝｸ(news4vip板)l50
今日の17時、20時、23時に 何 か を 「 撃 ち 」 ま す 。
抗議メール等、ご協力お願いいたします。
~~
↑
重要
243:デフォルトの名無しさん
05/08/20 16:06:16
>>11
大学に入れば勝ち
それだけで
仕事で使えもしないのに
おおいばりできるからな
244:デフォルトの名無しさん
05/08/23 09:45:03
>>243
違うだろ
それでやっと「スタートライン」だろ
245:デフォルトの名無しさん
05/08/24 00:58:46
コンピュータの数学 グレアム著
URLﾘﾝｸ(www.amazon.co.jp)
一応、既出ではないよね？
コンピュータの名著１００にも選ばれた超定番。
スタンフォード大学で使われてる教科書だけど、
ハノイの塔とかイメージしやすいところから始まって高度なところまで
自然に導いてくれるから、思ったほど敷居は高くない。
日本の教科書みたいにトップダウン式の記述ではなくかなり親切に書かれてるから、
腰をすえて読めばきっと満足できるはず。
値段的にアレだけど…。
246:デフォルトの名無しさん
05/08/24 09:43:17
>>245
URL長すぎ
もっと短くしる
247:デフォルトの名無しさん
05/08/24 12:35:21
amazonのURLのexec/obidosの部分は略記が可能で、
URLﾘﾝｸ(www.amazon.co.jp)
と出来る。
まだ長い?
248:デフォルトの名無しさん
05/08/24 12:48:08
URLﾘﾝｸ(www.amazon.co.jp)
こう？
249:デフォルトの名無しさん
05/08/24 16:24:06
スキームもいらんな。
www.amazon.co.jp/o/ASIN/4320026683
250:デフォルトの名無しさん
05/08/24 16:29:12
いっそ
">>245"
251:デフォルトの名無しさん
05/08/24 22:57:50
↑
252:デフォルトの名無しさん
05/08/25 10:14:14
>>245
> コンピュータの数学 グレアム著
この本はマジでいいよ
値段がアレだけど
Knuth の例の The Art... から
おいしいとこだけもってきて
きれいに系統だてたかんじ
TeX による組版のできもいい
数式は普通はイタリックを使うのが慣例だけど
別の書体を使ってるのがおもしろい
そもそもイタリックを使うのは普通の文章の
ローマンと区別するためのもので
区別させつけば数式がイタリックである必然性はない
253:デフォルトの名無しさん
05/08/25 16:13:28
値段もアレだが、大きさもアレだよな。
俺は洋書で買って、すぐ単元ごとに切り分けてしまったよ。
定評あるコンピュータ本って豪華な装丁だったり、
ページ数が膨大だったりするから、ホントはいつでも気軽に参照したいのに
（気持ち的に）アクセスが重いってことがある。
自分の血肉とするためには、本の体裁など気にせず
とことん自分仕様に改良するのがよい。
同じ本の違うページを同時に開いて見れるしね。
254:デフォルトの名無しさん
05/08/26 21:52:02
>>253
わかった！
さっそく切り刻んでくる！
255:デフォルトの名無しさん
05/08/26 23:03:01
でも、古本に売れなくなるぞ
256:デフォルトの名無しさん
05/08/30 01:26:45
豪華装丁本をバラすのはなかなか勇気がいりますなぁ…。
257:デフォルトの名無しさん
05/08/30 09:44:39
もう後戻りは出来ない
258:デフォルトの名無しさん
05/08/30 13:08:36
21 名前：名無しさん＠６周年[] 投稿日：2005/08/30(火) 10:31:13 ID:oAGcvdqV0
>>6
イタリア語で85000（8500だったかな・・）は
「 オッタッタチンコミーレ ！」
259:デフォルトの名無しさん
05/08/30 22:30:49
ヤコビ法
URLﾘﾝｸ(www.geocities.jp)
b配列に代入されている初期値の意味は何ですか？
260:デフォルトの名無しさん
05/08/30 22:50:21
3.0*x + -6.0*y + 9.0*z = 6.0
2.0*x + 5.0*y + -8.0*z = 8.0
1.0*x + -4.0*y + 7.0*z = 2.0
を解くプログラムで、a[n][n]が左辺の係数、b[n]が右辺ではないかい。
261:デフォルトの名無しさん
05/08/31 01:42:08
>>260
すばらしいぃ！！
疑問が晴れました。ありがとうございます。
262:デフォルトの名無しさん
05/09/13 01:54:25
結城さんの「プログラマの数学」は、
>>245 の「コンピュータの数学」グレアム著、
の初歩を紹介した感じの内容だね。
なんつーか、この人わかりやすい比喩を考えるのがうまい。
www.amazon.co.jp/o/ASIN/4797329734/
263:デフォルトの名無しさん
05/10/02 01:33:08
伝熱解析に関して
非定常の差分方程式を解くプログラムをCで作りたいのですが
おすすめの参考書とかありますか？
Tm+1 + Tm-1 + 2Tm / ⊿x^2 ＝ 1/α δTp/δt
の方程式です
264:デフォルトの名無しさん
05/10/05 11:38:18
数値解析+差分方程式 で google したら？
265:デフォルトの名無しさん
05/10/05 11:56:16
ワイルは晩年、直感主義数学を主張してたらしい
本当に基礎的な証明でも膨大な時間をかけて講義してたらしい
266:デフォルトの名無しさん
05/10/05 12:11:37
>>263
そのレベルなら、俺が師匠の手伝いしておごってもらった時に書いた本でも作ったな
てか、初歩の数値解析関係で、差分方程式のサンプルにまず100%含まれてる
後は、境界条件と制約条件をどうするかだけしかないな
267:デフォルトの名無しさん
05/10/09 02:17:46
263です
例で書いた数式１次元ですね。すいません
んー、３次元の非定常のプログラムがなかなかなくて・・・
参考書はほとんど二次元で終わってまして
268:デフォルトの名無しさん
05/10/12 17:21:19
楕円方程式で、
x^2/a^2 + y^2/b^2 = 1とネットで調べると出てくるのですが、
円の中心(本来はそういわないかもしれない)が(0,0)で
ない場合の式は、この式じゃないような気がするんですが。
269:デフォルトの名無しさん
05/10/12 17:26:54
それは標準形という奴だからでは？
270:デフォルトの名無しさん
05/10/12 17:34:17
つまり、その式は原点が中心の円を縦・横に引き伸ばした場合の式
さら平行移動させたり、回転させたりすると、当然複雑になるけど、複雑にしてもメリットないでしょ？
実際に楕円描く時はその式では不便で、sin/cosの媒介変数型使うだろうし
・・・・いや、実際に楕円描く場合はベジェ曲線で近似するだろうな
271:デフォルトの名無しさん
05/10/12 18:28:16
>>268
応用が効かない言い方をするならば、
中心(c,d)なら(x-c)^2/a^2+(y-d)/b^2=1と考えていい。
272:デフォルトの名無しさん
05/10/12 19:36:15
というか
曲線f(x,y)=0を x軸方向に+a, y軸方向に+b したら f(x-a,y-b)=0
x=f(t), y=g(t) だったら x=f(t)+a, y=g(t)+b だし
273:デフォルトの名無しさん
05/10/12 21:49:37
だから応用の効かないと言ったんだが
274:デフォルトの名無しさん
05/10/15 20:36:14
天文物理をやっていると焦点と離心率で楕円を書きたくなる罠。
275:デフォルトの名無しさん
05/10/16 22:27:04
紐と画鋲と鉛筆で描くみたいな感じ。
276:デフォルトの名無しさん
05/10/19 23:05:17
>>268
一応言っておくと「楕円方程式」と「楕円の方程式」は別物ですよ
ここで言ってるのは前者ですね
277:デフォルトの名無しさん
05/10/19 23:06:43
違った後者だ
278:デフォルトの名無しさん
05/10/21 20:14:16
いや、実は前者。俺の言うことを信じろ。
279:デフォルトの名無しさん
05/10/21 23:53:52
皆だまされるな！正しくはもちろん後者だ。
280:デフォルトの名無しさん
05/10/22 00:56:25
俺の言うことだけが本物だ。信じろ。
前者に決まっとる。
281:デフォルトの名無しさん
05/10/22 03:32:24
本当の事言うと。
どっちもどっちｗ
282:デフォルトの名無しさん
05/10/24 13:41:54
真実は闇の中…。
283:デフォルトの名無しさん
05/10/24 21:16:45
問：>>276-282のなかで嘘つきを断定せよ。
参考：>>268
284:デフォルトの名無しさん
05/10/26 14:03:53
今だから真実を告白したい…>>283こそが嘘つき。
285:デフォルトの名無しさん
05/10/26 23:53:36
>>284
嘘つきになる要素が・・・
286:デフォルトの名無しさん
05/10/27 13:49:13
俺こそが嘘つき。
287:デフォルトの名無しさん
05/10/27 14:31:05
この中に1人、明らかな矛盾を述べたものが居るっ！！！
288:デフォルトの名無しさん
05/10/27 15:00:16
>>287 お前やろ？
289:デフォルトの名無しさん
05/10/27 22:38:31
ヴルルル、自分は絶対嘘なんかついてますねん。
290:デフォルトの名無しさん
05/10/28 00:58:51
バカっていったやつがバカ
291:デフォルトの名無しさん
05/10/28 01:04:29
>>289 お前やー！！
292:291
05/10/28 01:05:14
…決め台詞で割り込まれた orz
293:デフォルトの名無しさん
05/10/28 01:10:03
おまえら落ち着け…
素数を生成するコードを書いて落ち着くんだ…
294:デフォルトの名無しさん
05/10/28 01:21:54
10 N=1
20 N = N + 1
30 K=2
40 IF N = K THEN LPRINT N
50 IF N MOD K = 0 THEN GOTO 20
60 K = K + 1
70 GOTO 40
295:デフォルトの名無しさん
05/10/28 10:58:22
やれやれだぜ…
296:デフォルトの名無しさん
05/11/04 02:06:55
だぜ、って懐かしいよな。
297:デフォルトの名無しさん
05/11/04 22:23:21
>>296
「だぜ」に突っ込むか・・・。
「やれやれだぜ」自体が漫画の台詞。
ジョジョ。
298:デフォルトの名無しさん
05/11/04 23:27:22
「だぜ」って「学校に行こう」に出てたﾔｼだろ？
299:判定
05/11/08 14:02:29
>>297-298
どっちも知る人ぞ知るってな話題だが>>298の方がよりマイナーと思われ。
300:& ◆BSGaog1Z0Q
05/11/08 14:18:52
#include<iostream>
//>>294
std::ostream& dumpPrimes(std::ostream& os, int max) {
for(int n=2; n <= max; ++n){
for(int k=2; ; ++k){
if(n==k) {
os << n << "\n";
}
if(n % k == 0) {
break;
}
}
}
return(os);
}
301:デフォルトの名無しさん
05/11/08 14:36:01
std::ostream& testDiv(std::ostream& os, int n, int k){
if(n==k){
os << n << "\n";
}
return((n % k == 0)? os: testDiv(os, n, k+1));
}
std::ostream& testNum(std::ostream& os, int max, int n){
return((n > max)? os: testNum(testDiv(os, n, 2), max, n+1));
}
std::ostream& dumpPrimes(std::ostream& os, int max) {
return(testNum(os, max, 2));
}
302:デフォルトの名無しさん
05/11/16 22:10:39
>URLﾘﾝｸ(ja.wikipedia.org)
> 素数は無限に存在する。
>
> エウクレイデスによる証明
> 背理法による。
> 素数が有限個しかないと仮定し、それらを次のようにおく。
>
> pi, i <= n
> ただし n は定数。
>
> q = p1p2p3．．．ｐｎ + 1
>
> を考えよう。q は合成数であるか素数であるかのいずれかである。
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
> 素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
> Q.E.D.
この証明変だよね。
303:デフォルトの名無しさん
05/11/16 22:18:18
>>302
どこで引っかかった？何が変？
304:デフォルトの名無しさん
05/11/16 22:22:32
「素数は無限に存在する」ことの証明だから、
「qが合成数」も「素数が有限」も否定していいんだよ。
305:302
05/11/16 22:29:52
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。
そうとは限らない
2 + 1 =
3 is a prime.
2 x 3 + 1 =
7 is a prime.
2 x 3 x 5 + 1 =
31 is a prime.
2 x 3 x 5 x 7 + 1 =
211 is a prime.
2 x 3 x 5 x 7 x 11 + 1 =
2311 is a prime.
2 x 3 x 5 x 7 x 11 x 13 + 1 =
30031 is 509 x 59
2 x 3 x 5 x 7 x 11 x 13 x 17 + 1 =
510511 is 97 x 5263
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 =
9699691 is 27953 x 347
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 + 1 =
223092871 is 703763 x 317
306:デフォルトの名無しさん
05/11/16 22:37:59
>そうとは限らない
> 2 + 1 =
>3 is a prime.
2<3
> 2 x 3 + 1 =
>7 is a prime.
3<7
> 2 x 3 x 5 + 1 =
>31 is a prime.
5<31
> 2 x 3 x 5 x 7 + 1 =
>211 is a prime.
7<211
> 2 x 3 x 5 x 7 x 11 + 1 =
>2311 is a prime.
11<2311
> 2 x 3 x 5 x 7 x 11 x 13 + 1 =
>30031 is 509 x 59
13<59
> 2 x 3 x 5 x 7 x 11 x 13 x 17 + 1 =
>510511 is 97 x 5263
17<97
> 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 =
>9699691 is 27953 x 347
19<347
> 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 + 1 =
>223092871 is 703763 x 317
23<317
論外なところから値を引っ張ってきて論じようとしている。
23が「最大」の素数であれば、317は素数でも合成数でもないのでどちらにしても矛盾がしょうじる。
307:デフォルトの名無しさん
05/11/16 22:41:27
>>305
この推論は「素数が有限個しかない」という偽の前提があるから、反例を持ち出してもしょうがない。
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。
これは、「合成数は有限個の素数の積で表される」という定理と「素数はpiしかない」からの帰結。
308:302
05/11/16 22:49:50
素数が有限個しかないとは思ってませんが、
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである
そうでない場合もあるとは思いませんか?
そして、その場合についても論ずるべきでは?
309:デフォルトの名無しさん
05/11/16 22:57:11
>>308
だから、>>307に書いたように、
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである
は「素数がpiしかない」という仮定の下で証明できる。
証明できるからには、これが偽である可能性を検討する必要はない。
310:302
05/11/16 23:37:43
では、エウクレイデスによる証明は、
>「合成数は有限個の素数の積で表される」という定理
を前提としているわけですか?
311:デフォルトの名無しさん
05/11/16 23:45:05
>>310
群論か環論の本を読んでくださいな、素元、既約元のあたりです。あとできれば背理法についてもね。
312:デフォルトの名無しさん
05/11/16 23:57:48
>>310
細かい違いはあるかも知れない（例えば、その定理の代わりに「合成数は素因数を持つ」でも十分）けど、
基本的にはその通りだと思う。
313:302
05/11/17 00:16:30
じゃあこの部分を
> を考えよう。q は合成数であるか素数であるかのいずれかである。
> q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
> 素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
こう変えてもいいですか?
を考えよう。q は合成数であるか素数であるかのいずれかである。
q が合成数だとすると q は pi のいずれかを用いて積の形に表されるとき、q は pi のいずれで割っても 1 があまり、矛盾する。
また q は pi のいずれかを用いて積の形に表されないとき、q は pi を超える素数を持ち、矛盾する。
素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
314:デフォルトの名無しさん
05/11/17 00:19:56
おまいらプログラマらしく素因数分解のアルゴリズムでも考えよう
128bit暗号を解読できるくらいのを
315:デフォルトの名無しさん
05/11/17 00:31:12
>>313
ちょっとおかしいところ(「piを超える素数」じゃなくて「pi以外の素因数」というべき)があるけど、大筋としてはそれでもいい。
でも、そう書き換えたところで推論の構造はほとんど変わっていないし、
「合成数は素因数をもつ」ことに依存しているのも変わらない。
316:302
05/11/17 00:46:27
そうですか。
自分なりに納得できて助かりました。
ありがとうございました。
317:デフォルトの名無しさん
05/11/17 01:16:31
代数学か。懐かしいな。
318:デフォルトの名無しさん
05/11/17 11:36:57
>>311
いや、真っ先に背理法を理解すべきでは？
319:デフォルトの名無しさん
05/11/17 12:27:31
大きくなれよ
320:デフォルトの名無しさん
05/11/17 13:05:04
背理 背理 振れ 背理法～
321:302
05/11/17 16:06:10
たびたびすみません。
素数を順番にかけるとint型では、23までしかいけなかったので
double型でやったら、途中からおかしな答えになりました。
下から2番目なんですが、答えが1大きくなりました。
なんでなんでしょう？
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 + 1 =
6469693231 is 331 x 19545901
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 + 1 =
200560490131 is a prime.
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 + 1 =
7420738134811 is 181 x 40998553231
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 + 1 =
304250263527211 is 61 x 4987709238151
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 + 1 =
13082761331670032 is 2 x 6541380665835016
2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x 29 x 31 x 37 x 41 x 43 x 47 + 1 =
614889782588491390 is 2 x 307444891294245700
322:デフォルトの名無しさん
05/11/17 16:08:50
2進数で表すと分かるかも。doubleの内部ビット表現を調べてみな。
323:デフォルトの名無しさん
05/11/17 17:01:31
>>321
浮動小数点表現の仮数部が 52 ビットのとき、精度は 15.6 桁。
…って、計算機の初歩の初歩だろうに。
324:302
05/11/17 17:11:45
>>322
レスありがとうございます。
2進数の表し方がわからなかったので、
16進数で見てますが、所々おかしなところがあり、
手直ししています。
>>323
そうでしたか、出直してきます。
325:デフォルトの名無しさん
05/11/17 21:07:29
SA（シミュレーテッド・アニーリング）法で
巡回セールスマン問題解くプログラム作ってるんですけど
このスレでいいっすか？
それとも数学板に行ったほうがいいですかね？
URLﾘﾝｸ(www.watanabe.nuie.nagoya-u.ac.jp)
↑でとりあえず理屈はわかったんだけど
摂動行列の決め方がわからん。
ていうか
あるルート候補から次のステップのルート候補作るときに
全部シャッフルしたらさすがに効率悪そうだし
隣同士入れ替えただけだともろ局所解に引っかかりそうだし。
なんか巡回セールスマン向けのうまい方法
（あるルートXnからX(n+1)を作るアルゴリズム）
だれかしらないですか？
326:デフォルトの名無しさん
05/11/17 22:09:18
>>325
アニーリング関数が適当なら、その隣同士とかでやったとして
局所的なくぼ地にはまってしまうような場合であっても
少ない確率ではあるけどそのくぼ地を乗りこえることかできるから
結局それなりにうまくいくんじゃないのかな
327:デフォルトの名無しさん
05/11/18 00:37:31
>>321
つ[long long]
328:デフォルトの名無しさん
05/11/19 09:22:25
>321
つ[多倍長演算]
329:デフォルトの名無しさん
05/11/19 10:35:17
読みって「たばいちょう」？
330:デフォルトの名無しさん
05/11/19 11:18:12
>>329
OK!
331:デフォルトの名無しさん
05/11/19 11:26:32
束井町の塩山では今年も岩塩の収穫の時期になりました
332:デフォルトの名無しさん
05/11/19 11:29:02
えっ？どこっ？なに？誤爆？束胃腸・・・？
333:デフォルトの名無しさん
05/11/19 13:23:14
>>330
サンクス。
変換しても出てこないので違うのかなと思っていた。
334:デフォルトの名無しさん
05/11/19 13:51:31
>>333
かな漢字変換辞書が全ての技術語を網羅しているわけがないだろう。
それともあれか、藻前は「へんかんできないからそんな字ない」とか言っちゃう小学生か?
335:デフォルトの名無しさん
05/11/19 19:32:31
つーか他の読みをしようにもたばいちょうとしか読めん
336:デフォルトの名無しさん
05/11/19 20:10:17
>>334
そんなにキツく言わんでも・・。
337:デフォルトの名無しさん
05/11/20 22:49:35
今 1 から N までの N 個の異なる自然数からなる順序付きタプルを入力に受け，
そのタプルが大きさ N の全順列中において辞書順で何番目かを返すアルゴリズムを
実装したいんですが，どういうアルゴリズムが考えられますか？
例えば， {1, 2, 0} を与えたら 4 を返すような感じのアルゴリズムです．
338:デフォルトの名無しさん
05/11/20 22:53:59
タプルって何だっけ？
339:デフォルトの名無しさん
05/11/20 23:01:25
>>338
tuple
【名】 組、《コ》タプル
340:デフォルトの名無しさん
05/11/20 23:08:44
>>337
それの例のまま、 {1, 2, 0} で考えると、
最初が 1 → このタプルより前には {0, *, *} がある → 前に 2! 個 ＝ 2個 ある
次が 2 → でも1は出てる → これより前で、{0, *, *} 以外のものは {1, 0, *} → 1個
だから、{1, 2, 0} より前には3個のタプルがあるから、
{1, 2, 0} は4番目。って感じ？
1つ数字増やして {2, 3, 1, 0} とかでいくと、
最初、{0, *, *, *} と {1, *, *, *} 数えて、 3! ＝ 6個
次、{2, 0, *, *} と {2, 1, * *} で 2×2! ＝ 4個
次、{2, 3, 0, *} があるから 1個
計11個前にあるから {2, 3, 1, 0} は12番目。
341:デフォルトの名無しさん
05/11/20 23:10:03
Nがわかったら、順列を順に生成する関数に渡せば良いんじゃね？（N,{0,1,2}を渡す）
で、マッチングをとる。
342:デフォルトの名無しさん
05/11/20 23:17:15
あっ、340 の {2, 3, 1, 0} の例、最初は 3! じゃなくて 2×3! ＝12、
最後の結果も18だわ。
>>341
それだと順列生成自体が糞重たいし、コーディング結構難しくない？
343:デフォルトの名無しさん
05/11/21 00:32:41
魔法陣って4×4で出来ますか？
344:デフォルトの名無しさん
05/11/21 01:58:19
できます
345:デフォルトの名無しさん
05/11/21 11:28:06
>>340 の考え方で C++ 使うと
std::vector<int> src, arr;
src.push_back(1);
src.push_back(2);
src.push_back(0);
arr = src;
size_t ct = 0;
do {
#ifdef _DEBUG
std::cout << "{";
for (int i=0; i<arr.size(); i++)
std::cout << (i? ", ": "") << arr[i];
std::cout << "}" << std::endl;
#endif // _DEBUG
} while (ct++, std::prev_permutation(arr.begin(), arr.end()));
std::cout << ct << std::endl;
結果:
{1, 2, 0}
{1, 0, 2}
{0, 2, 1}
{0, 1, 2}
4
346:デフォルトの名無しさん
05/11/21 15:45:08
>>337
素直に説明を読むと、
「1からNまでのN個の順列組み合わせを辞書式順序で並べたとき
各組合わせは何番目？」
という問だと思うのだが、いきなり組の要素に0があったりするのはなぜ？
347:337
05/11/21 18:58:04
>>340
素直にやるなら，前から順に読んでいって現れた数字を記録しないとならないですよね．
前から順に読んで現れた数字より大きい数字を全てデクリメントしていくやり方も
あるのかな？参考になります．
>>345
これって 340 さんの考え方じゃなくてむしろ 341 さんの考え方ですよね？
>>346
すいません．最初，説明を「0 から N-1」と書いてて後で直したんですが
例を書き直すのを忘れてました．337 の正しい例は {2, 3, 1} です．
348:デフォルトの名無しさん
05/11/22 04:02:57
＞前から順に読んで現れた数字より大きい数字を全てデクリメントしていくやり方
それでいいんでね？
(1)result=0で初期化
*ここで、1～Nの整数が、適当に並べ替えられて並んでいたとして、
(2)N=1ならresult+1を返し終了。
(3)左端の数aに対し (a-1)*(N-1)! を計算し、resultに加算。
(4)列の中で、aより大きい要素は全て1だけ減らす(小さい要素はいじらない)。
(5)先頭のaを切り落とし(N=N-1)、残った列に対し*に戻る。
349:340
05/11/22 12:02:43
>>348
それ見てて思ったけど、
(3)（階乗計算）とか(4)の計算に掛かる時間を考えると、
>>345 のコードよりも計算量大きくなるかも。
>>345 だと標準ライブラリの機能そのまま使っててコード量的にも少ないし。
順列生成のアルゴリズムって、>>345 の結果見てる感じ、
バブルソートを1ステップずつやるようなものなのね。
350:デフォルトの名無しさん
05/11/22 16:31:37
似たような問題で、よく出るのが、
1 から N までの N 個の異なる自然数による順序付タブル をランダムに出力せよ
351:デフォルトの名無しさん
05/11/22 18:36:00
タブル
352:337
05/11/23 22:03:52
>>349
345 さんのコードだと平均・最悪で O(N!) な一方で
348 さんのだと平均・最悪で（階乗計算も含めて） O(N^2) ですから，
特別な事情がなければ 348 さんのを選択するのが良いと思います．
というか 348 さんのアルゴリズムで実装できました．ありがとうございました．
353:デフォルトの名無しさん
05/11/28 23:10:17
新スレたてました！
フーリエ変換が趣味です。
ｽﾚﾘﾝｸ(hobby板)
354:デフォルトの名無しさん
05/11/29 19:35:47
『任意の微分方程式を与えられたとき、それを解くプログラムを記述せよ。ただし、す
べての方程式を解くことは困難なので、そのプログラムで解ける範囲を指定し記述せよ。』
この問題のアルゴリズムと、ソースを書いてくれませんか？
ここで悩んでいるので是非とも力を貸してください!!お願いします。
355:デフォルトの名無しさん
05/11/29 19:36:39
師ね
356:デフォルトの名無しさん
05/11/29 19:36:55
×力を貸してください
○答え教えろ
357:デフォルトの名無しさん
05/11/29 20:08:28
＞すべての方程式を解くことは困難なので、そのプログラムで解ける範囲を指定し記述せよ。』
とりあえずオイラー法を用意して、それで解ける範囲を明示しておけばレポート通るんじゃね？
358:デフォルトの名無しさん
05/11/30 01:23:23
あからさまに宿題をそのまま出されるとな・・・
359:デフォルトの名無しさん
05/12/07 23:46:24
URLﾘﾝｸ(www-ise2.ise.eng.osaka-u.ac.jp)
上記のサイトで、Sinをテイラー展開で求めているようですが、
sin(0.00) = NaN (非数値)
sin(0.01) = NaN (非数値)
sin(0.02) = NaN (非数値)
・
・
となってしまいます。どこが間違っているのでしょうか？
360:デフォルトの名無しさん
05/12/08 00:11:24
0で割りゃあ、非数になるわなｗ
double Sin(double x)
{
double xx = -x * x;
double fact = 1;
double sin = x;
for(int i=1; i<100; )
{
fact *= ++i; fact *= ++i;
x *= xx;
sin += x / fact;
}
return sin;
}
361:デフォルトの名無しさん
05/12/08 00:16:08
っつーかおまいら、2ch にさらす暇あったら作者に報告入れろって。
362:359
05/12/08 00:39:53
>>360
なるほど！ 数学関連の話で、何が合っていてどこから手をつけていいものか
困り果てているところでした。非常にお早いレス感服いたします。
ありがとうございました。
>>361
すみません。いくつか間違いがみられ、一応メールアドレスを探してみた
のですがわかりやすい位置になかったので、すぐに断念してしまいました。
363:デフォルトの名無しさん
05/12/08 00:42:21
i=100から順に計算した方が精度が上がると思う
364:デフォルトの名無しさん
05/12/08 01:32:54
数学的に正しくてもプログラム的にどうなのかは別問題なのす
365:340
05/12/08 11:29:34
>>362
トップページたどれって。
全ページに連絡先入れといた方がいいのか？
>>363
それいいだすとさ、
π/2 の範囲に収まるように mod 2π とか三角関数の公式使って変換して、
sin と cos のどちらか選んで計算するとか、凝りだすときりない。
餅は餅屋と言う奴で、そういうのは数値計算屋さんにお任せしないと。
366:デフォルトの名無しさん
05/12/08 22:43:03
>>365
ウェブページの作り方的な話なら、
全ページにaddress要素は入れるのが基本
address要素内には連絡先として通常メールアドレスが入る
367:デフォルトの名無しさん
05/12/08 23:13:51
>>366
それ、確かに推奨はされてるけど、
ボットにアドレス収集されるのが嫌で、実際やってる人いなくない？
368:デフォルトの名無しさん
05/12/08 23:25:27
>>367
俺はやってるよ
あるいは自働収集が嫌って言って
画像を使ったり余計な文字をはさんだりしてる人もいる
要は形式上の問題じゃなくて、
>>362みたいな状況にならないようにっていうのが
目的なんだし。
369: 【凶】 【308円】
06/01/01 07:54:11
あけましておめでとう。 求む 質問・疑問
370: 【だん吉】 !otoshidama
06/01/01 08:40:35
さっきやったら大凶が出たぞ！
371:デフォルトの名無しさん
06/01/09 00:38:04
答えが来るかわからんけど
マージソートについて勉強してます
マージソートの配列の分割についてなんですけど
例えば8だけの場合は
4 4
2 2 2 2
1 1 1 1 1 1 1 1
とだけ分割できると思います。
ですが例えば要素が34の場合
17 17
と一回だけ分割すると素数になってしまいます。
更に極端にしますと
7や23などの要素の個数の場合はどう分割するのでしょうか・・
まだ勉強初めて1日だけなんでアレですが参考のページでもあると嬉しいです
372:デフォルトの名無しさん
06/01/09 00:49:45
>>371
そりゃ、8と9に割ればいいじゃん。
373:デフォルトの名無しさん
06/01/09 00:54:24
>>372
しかしその場合併合(マージ)しようとするとどんな風になるのでしょうか
グーグル先生のイメージ検索はエレメントの個数が偶数ばかりのもので・・
勉強してきます(´･ω･`)
374:デフォルトの名無しさん
06/01/09 00:56:37
どんな感じってソートするだけだろ。
375:デフォルトの名無しさん
06/01/09 03:02:59
>>373
べつに偶数のときとかわらん。
違う数に分割されたからといって
コードの何処も変える必要なんかない。
そんな必要があったら
そもそもマージソートじゃない
376:デフォルトの名無しさん
06/01/09 10:30:58
>371
例えば9の場合、
4, 5
(2, 2), (2, 3)
((1, 1), (1, 1)), ((1, 1), (1, 2))
((1, 1), (1, 1)), ((1, 1), (1, (1, 1)))
と分割すればいい。
てか図解すると並列に見えるけど、実際の処理は再帰的に行われるから、
部分的に階層が深くなっても問題ない。
URLﾘﾝｸ(oku.edu.mie-u.ac.jp)
の mergsort.c 読めば解るよ。
377:デフォルトの名無しさん
06/01/09 13:56:17
>>373
つーか、聞く前に一度自分で実際にやってみ。
マージって全然個数の違う2つの列相手にもできるから。
例えば極端な話 1, 16 とかで分けてもマージできる。
378:マイク ◆yrBrqfF1Ew
06/01/23 00:20:53
シュレーディンガーの猫というのは簡単に言うとあれだろ
堀江由衣の処女
379:デフォルトの名無しさん
06/01/23 04:26:20
,,-‐----‐､ , -'"`￣￣"`''-,__, --‐‐-..,
/ 、ﾞヽ､ ‐-'´ ヽ‐- / / ヽ
,/´ .., ヽ,,l_),' '､,ﾄ/ / ヽ
/ ヽ,r' l .,､z:ｭ､,_. ,､=,ﾞ.-〈__r,'､ ヽ_
_.l ヽ」 , l. ´ ,r'ャ､`' i'rｬ;| ﾞ‐ヽ､＿,, /l
,l l| －'´ll ,ll ヽ. ''｀¨¨´ ヽ | .,//ﾞl //＼
l｀l| l|ヽ ヽ 入 ,ィ _. ', l |l // }
ｌ ＼ l| ,l ヽ_. ' `'ﾞ`'‐'iﾞ ,' |,l // l ﾊﾞｶｼﾞｬﾈｰﾉ
/ '＼ l|｀l l ヽ`'. ,∠.ニﾌ / l ヽ // |
,l '＼ l| .lヽ＿l ` ､ ､ い.... ,' /＿__／ | ∨/ ,}
| ヽl | ,| .ヽ', .ヽ`二ﾌ.,' ヽ ,| ,l
| l ,l ' .､,＿｀,.ィ l ＼ /
ヽ | ＼. ヽ/ l ヽ ／j
＼ / ヽ ヽ | l /
ﾞl＼.. / ヽ ヽj | , /
ヽﾞ ヽ ヽ ヽ / ,l
ヽ、 ヽ l } / ,r
ヽ ヽ | /′ ,,...''
｀'':..､ ___ ＿__,.．-.. |, ,l , :..-‐'"´
￣ /lr‐‐‐'--､_..... ｌ_,.．-'''""'- "
380:デフォルトの名無しさん
06/01/30 23:54:04
原点(0,0)を中心とした半径Rの円がある
中心点から角度θの軸を考え、横2W縦2Hの長方形の中心がこの軸を移動するとして
長方形の頂点が円周上にくる点の座標は？
381:380
06/01/30 23:55:32
>>380書き忘れ
長方形は円の内側にあるものとする
382:デフォルトの名無しさん
06/01/31 00:41:23
>380-381
人にモノ聞く態度じゃねぇな。
出直して来い。
383:デフォルトの名無しさん
06/01/31 09:44:41
それになんか問の内容も何がいいたいかよーわからん。
もしかして日本語が不自由な方なんでわ？
384:デフォルトの名無しさん
06/01/31 10:41:19
ここは宿題スレじゃないんじゃね？
385:デフォルトの名無しさん
06/01/31 18:07:46
正方形じゃねーのかな・・・
386:デフォルトの名無しさん
06/01/31 18:42:49
プログラムじゃなくて普通に算数（三角比を使うにしても数学ってほどじゃない）だなぁ。とりあえず解いたんで書く。
r=-(Wcosθ+Hsinθ)+√(R^2-(Wsinθ-Hcosθ)^2) として
(rcosθ+W, rsinθ+H) …(1)
θの範囲は0≦θ<π/2だけどね。他の範囲は(1)式にある符号が変化するだけのはず。
387:デフォルトの名無しさん
06/02/01 08:22:33
>>386
それだと、 W = H = 0 の時にしか、長方形の頂点が円周上にこないんじゃない？
「点の座標」ってのが長方形の中心だとしても頂点だとしても。
多分やつは問題を理解できてないんだろうなあ。
2Dゲーム作ってて、円形フィールドからはみ出さないようにしたい、と推測したがどうか。
388:デフォルトの名無しさん
06/02/01 17:20:04
>>387
それだと浮動小数点でやってる場合、
点の座標を求めて＝で判別したらイタイ目見そうだ。
（丁度等しくならなかった時に判定をスリ抜ける。）
不等式で「内側」の度合い評価できる基準を見つけないと。
389:デフォルトの名無しさん
06/02/01 17:29:09
2Dゲームの判定に使う程度なら
たぶん長方形の外接円で判定してごまかすのが楽なんじゃないかなぁ。
中心点同士の距離と半径だけで判定できる。
2乗ノルムでやれば平方根もいらないし。
もし精密にやりたければ上記の方法で簡易判定して明らかに接触しない事例を除いた上で
拙速するかもしれないケースだけ長方形を構成する線分が交差するかどうかを判定すれば
いいのかな。
390:デフォルトの名無しさん
06/02/01 17:31:22
で、この場合長方形の軌道は無視して一般化できて
軌道は具体的に長方形の位置を計算する以外は無関係だね。
391:マイク ◆yrBrqfF1Ew
06/02/04 00:33:27
log(2)(x-1) + log(1/2)(3-x) <= 0 //logの真ん中の()は底
を満たすxの値の範囲は
a < x <= b
このaとbと導かれる過程がわからん。
包茎じゃなくて東京六大学に在学中か卒業した人だけ答えてくださーい。
392:デフォルトの名無しさん
06/02/04 11:10:14
ヒント： a<x の部分は真数条件から
393:デフォルトの名無しさん
06/02/05 13:36:53
＿＿＿ ＿
|￣| ／> ＿ ＿ / ＿| ｜ | ／>
| |／／ ＼ ＼ __ ／ ／ ＼ ＼. | |／／
| ＼ ＼ ＼／ ＼／ ／ 〉 ヽ. | ＼
| |＼ ＼ ＼ ／＼ ／ |￣￣ ﾉ | |＼ ＼
／::::/'" ￣ヾi ／ ￣￣ ＼ ／::::/'"￣￣ヾi ／ ￣ ヽ
|:::::::| ,,,,,_ ,,,,,,| | ^ ^ | |:::::::| ,,,,,_ ,,,,,,| | ^ ^ |
|r-==（ ｡);（ ｡) | >ﾉ(､_, )ヽ､.| |r-==（ ｡);（ ｡) | >ﾉ(､_, )ヽ､.｜
( ヽ :::__)..:: } ! ! -=ﾆ=- ﾉ ! ( ヽ :::__)..:: } ! ! -=ﾆ=- ﾉ !
ヽ ー== ; ＼ ｀ﾆﾆ´ ／ ヽ ー== ; ＼ ｀ﾆﾆ´ ／
＼＿＿_ ! ￣￣ ＼＿＿_ ! ￣￣￣
394:デフォルトの名無しさん
06/02/06 04:30:36
東京六大学ってスポーツリーグだろ？
あんなかでまともな偏差値誇ってんのは
東京 慶應 早稲田 だけだろ
あとの三つは……やめた。
395:デフォルトの名無しさん
06/02/06 11:34:15
>391
名大出のしがない漏れは
頑張って答えようとしたりせずにニヤニヤしてれば好いわけね？
396:デフォルトの名無しさん
06/02/06 19:59:06
包茎云々は法政のことかいのう・・・
397:デフォルトの名無しさん
06/02/07 22:59:21
法経学部？
しかし>391ってまるっきり高校レベルじゃないか
398:デフォルトの名無しさん
06/02/08 12:53:00
>>397
シッ！ 皆わかっててニヤ(・∀・)ニヤしてるんだから！
399:マイク ◆yrBrqfF1Ew
06/02/08 18:49:12
高卒･大卒なのにセンター試験の問題すら答えられないんだね;)
400:デフォルトの名無しさん
06/02/09 10:40:54
>>399
イヤー、オヂサン参ったな。ナント院卒だが答えられないぞ。
>391が出した問題の最後に示された条件：
> 包茎じゃなくて東京六大学に在学中か卒業した人
を満たすことができないからなー。何せ漏れは重度の冠頭包茎だし、
名古屋生まれの名古屋育ちで大学も院も名古屋大学だからな。
漏れがこの問題に答えるためには
東京6大学（慶応、上智、東京、明治、立教、早稲田）のどっかに入らないと
イカンわけだろ？
いやー回答者の資格に制限がある問題は難しいわ、ホント難しい、
全然答えられそうにないよｗｗｗ
最近のセンター試験ってこんな答えるのが難しい問題出すの？（・∀・）
401:デフォルトの名無しさん
06/02/09 10:43:17
解らないっつってた本人が捨て台詞。
相変わらず莫迦なコテだな。
402:400
06/02/09 11:08:11
あ、書き忘れてたけど漏れが問題に答えるためには
My包皮も切らないとイカンのかー。やっぱ難しいわ。
漏れ包皮ついてるほうが好きだし、
臆病者だから体の一部切るなんてコワいしなー。
403:マイク ◆yrBrqfF1Ew
06/02/09 17:15:47
>>401
エセ学歴な上にノータリンですか?(▽
>>400
名古屋はもういいよ。
404:400
06/02/09 17:45:26
ま、>>391には皮肉も通じないようなんでマジレスに切り替えるけどね。
思うんだが学歴を今後も問題の条件に入れ続ける気なら
学歴板でも行ったらどうかと思う。
ここはプログラム板の数学スレだから学歴は関係ない。
そしてプログラムに関係ないセンター試験の問題について
受験生向け解説依頼を受け付けるスレでもない。
受験生ならオトナシク受験板でも行ってたほうがいいんじゃない？
大学受験板
URLﾘﾝｸ(etc4.2ch.net)
学歴板
URLﾘﾝｸ(tmp6.2ch.net)
405:マイク ◆yrBrqfF1Ew
06/02/09 18:10:56
答えたくなければいいんですよ。
答えなくなければね;)
406:デフォルトの名無しさん
06/02/09 18:16:13
実際答えたくねーし。
407:デフォルトの名無しさん
06/02/09 18:39:45
プログラムに関係ない受験数学の質問する厨な荒しは
今後スルーが相応と思うがどうか？
408:デフォルトの名無しさん
06/02/09 19:39:20
すべて水に流して 心機一転
ー 再開 ー
409:マイク ◆yrBrqfF1Ew
06/02/09 21:36:08
>今後スルーが相応と思うがどうか？
毎度スルースルーと言ってる割には毎度我慢できなくなってレスしちゃうんだね。
子供?;)
410:デフォルトの名無しさん
06/02/10 00:01:50
ここはム板なんだから、やっぱプログラム的に
近似的に解くべきだなｗ
411:デフォルトの名無しさん
06/02/10 02:34:30
>>409
えーと、どこで笑えばいいのかな？
412:デフォルトの名無しさん
06/02/10 16:15:10
>>410
じゃぁ、両端を探すために二分探索でもするか？
413:デフォルトの名無しさん
06/03/01 22:02:54
>>411
m9（^Д^）
じゃなくて
;)
を無理して使うとこ
414:デフォルトの名無しさん
06/03/03 14:58:11
自分の趣味としては;)よりは;-)
415:デフォルトの名無しさん
06/03/09 09:58:52
僕的には :-P
とかがかわいくて好きでつ
416:デフォルトの名無しさん
06/03/09 11:39:33
ここは顔文字スレになりました。よろしくね ;-P
417:デフォルトの名無しさん
06/03/09 11:56:57
問題だ
1＋1＝
418:デフォルトの名無しさん
06/03/09 12:14:22
11
419:デフォルトの名無しさん
06/03/09 12:24:33
10説も提唱するか。
420:デフォルトの名無しさん
06/03/09 12:34:32
Error: '=' の左が左辺値ではありません
421:デフォルトの名無しさん
06/03/09 13:24:56
Error: '=' で式が終わっています
422:デフォルトの名無しさん
06/03/09 23:36:01
Error : 予期せぬ問題が出題されました
423:デフォルトの名無しさん
06/03/10 00:06:04
符号付整数除算で四捨五入の処理について質問があります。
a÷b の結果を四捨五入して ret に取得する処理を以下のようにしました。
[バージョンA]
// 除数と被除数の符号チェック
if ((a ^ b) < 0) {
// a, bが異符号
// ret = (a / b) - (1 / 2)
ret = (2 * a - b) / (2 * b);
}
else {
// a, bが同符号
// ret = (a / b) + (1 / 2)
ret = (2 * a + b) / (2 * b)
}
この方法だと正の場合0.5→1、負の場合-0.5→-1となり
数値0に対して正負の結果が対称になります。
(続く・・・)
424:423
06/03/10 00:07:03
今、実装したいと考えているのは
除算結果の整数部: n、小数部: s (s >= 0) としたとき
四捨五入後の結果
・s < 0.5 のとき n
・s >= 0.5 のとき n + 1
[実例]
・-0.6 = -1 + 0.4 = -1 + 0 = -1
・-0.5 = -1 + 0.5 = -1 + 1 = 0
・-0.4 = -1 + 0.6 = -1 + 1 = 0
・0.4 = 0 + 0.4 = 0 + 0 = 0
・0.5 = 0 + 0.5 = 0 + 1 = 1
としたいのですが、上手い方法が見つかりません。
一応、自分なりに考えて以下のように実装したら上手くいきました。
[バージョンB]
if ((a ^ b) < 0) {
// 正数にして計算を行う
a = abs(a); b = abs(b);
// ・整数除算の結果を -1 したもの
// ・小数部を割合化したもの(？)である (b - (a % b)) / b + (1 / 2) を四捨五入したもの
// を加えて求める。
ret = -(a + b) / b + (2 * (b - (a % b)) + b) / (2 * b);
}
else {
ret = (2 * a + b) / (2 * b);
}
除数、被除数の符号チェックをしたりしてスマートではないので
もっとシンプルにできる整数演算での上手い方法はあるのでしょうか？
よろしくお願いします。
425:デフォルトの名無しさん
06/03/10 00:11:33
0.5足して切り捨てしちゃ駄目？
426:423
06/03/10 01:16:10
>>425
画像処理で使用するため浮動小数点は、できるだけ使用しないようにしています。
ちなみにバージョンA,Bともに四捨五入をするときは
ret = (a / b) + 0.5
= (a / b) + (1 / 2)
= (2 * a + b) / (2 * b) ←通分(だったっけ？)
のように0.5を足すようにしています。
427:423
06/03/10 01:32:01
ちょっと言葉足らずだったので補足を・・・
単純に0.5を足して切り捨てると除算結果が負数の場合に問題があるのです。
(たとえば、結果が-2のときは -2.0+0.5 → -1.5 → -1になってしまう)
そのためにバージョンAでは、除算の結果が正負で場合わけをして
+0.5か-0.5を切り分けることにしました。
428:デフォルトの名無しさん
06/03/10 02:46:54
＞画像処理で使用するため浮動小数点は、できるだけ使用しないように
そもそもここに間違いがあると思うだけどな
429:デフォルトの名無しさん
06/03/10 11:44:35
>424
方法はそれしかない。可搬性を確保したい場合符号チェックは必然。
挙げられた例題は結果の精度として整数値しか必要でない
(小数点以下0ビットの精度)場合の固定小数点演算と看做すことができる。
固定小数点演算とは例えば小数点以下に2ビットの精度が必要な場合に
3ビット下駄を履かせて1→8、0.5→4とするなどして整数演算によって
一定精度の実数演算を行う方法だ。
その場合結局四捨五入の処理も必要になる。
最下位ビットが0か1かを決めるために剰余を使うのもまさに例題と同じだ。
（固定小数点演算という枠組みで考える理由は精度が異なる場合も
同じ考え方で統一的に考えられるというだけだ。）
そして符号の処理も結局必要になる。
ただ、符号付整数除算のハードウェア仕様としてはAもBもありえて、
ハードウェアの仕様を調べてそれに依存するなら処理を省略できる可能性はある。
通常の整数は2の補数表示をすることで正数に対する処理を転用して
負数を扱っているで0に対して表現が元々対称でない。
だからBバージョンが目当てなら見込みは割とある。
ハードウェアに依存しちゃうけどね。
430:デフォルトの名無しさん
06/03/10 11:58:45
訂正
2ビットの精度が必要な場合→3ビットの精度が必要な場合
精度は悪化するけど2bitの精度が必要な場合に3bit取って
剰余は見ないで最下位ビットだけ見て四捨五入って手はあるけどね。
431:423
06/03/10 14:08:49
色々とありがとうございます。
やはり、符号チェックは必要なのですね・・・
浮動小数を使いたくないというのは、参考にしているライブラリの処理速度を計測したところ
その結果から浮動少数は使っていないと思われるためです。
ちなみに、そのライブラリは Win32API のウィンドウとビューポート間の座標変換処理で
比較対照としているものは LPtoDP() という関数です。
こいつが結構くせもので、整数部を n 、小数部を s としたとき
だいたい s >= 0.47 で四捨五入して n + s → n + 1 としているのです。
（負数の場合も -1.53 = -2.0 + 0.47 = -1 [入]、-1.54 = -2.0 + 0.46 = -2 [捨]）
上記のように、四捨五入の仕様は>>424のバージョンBと同じです。
整数演算で 0.47 くらいで四捨五入なんて特殊なことをしているので
何か整数演算独自の四捨五入の方式があるのかと思い質問させていただきました。
個人的にはバージョンBの除数、被除数の符号が異なる場合に
除算を2回行うというのに満足できないので、もう少し紙とペンで色々と考えてみます。
432:デフォルトの名無しさん
06/03/10 15:50:22
サンプルを少数表記じゃなくて整数比で示してくれないか？
その方が解析しやすい。
433:デフォルトの名無しさん
06/03/10 15:55:04
知ってるかどうか知らないが、
小数点以下の数を10進表記するとそれだけで誤差が含まれる。
だからこの場合、実数に換算しないで考えたほうがよい。
つまり計算させてる事例に関わる整数の比がないと
何が行われているか正確なことはわからない。
LPtoDP()ってことは窓の大きさとディスプレイの解像度が絡むんだろ？
434:デフォルトの名無しさん
06/03/10 16:18:42
固定少数点で負数の時だけ処理するのを条件判断を使わずにやりたいなら、
ret = (2 * a + b*sgn) / (2 * b);
として sgn を 1か-1にすればいい
あるいは
ret = (2 * a + b*(sgn+1)-b) / (2 * b);
とすれば sgn+1 は 0か2なので 0か-1の変数fを使い
ret = (2 * a-b + 2*b&f) / (2 * b);
xor結果の最上位で fを-1か0にすればいい
・右へのビット幅だけシフト
・インラインアセンブラを使って符号拡張命令
して、符号ビットを埋めて ゴチャゴチャやる方法があるけど、そんなの使いたい？
435:デフォルトの名無しさん
06/03/10 16:27:53
他に
ret = (2 * a + (b^t)) / (2 * b);
として tを 0か-1とする方法もある
でもたぶん
ret = ( a + ((b^t)>>1) ) / b;
あたりでやってんじゃないかな
436:423
06/03/10 18:01:03
みなさん、どうもありがとうございます。
>>432 >>433
座標変換のための設定は以下の通りです。
// マッピングモード設定
::SetMapMode(hDc, MM_ANISOTROPIC);
// ウィンドウ領域 (0, 0) - (1000, 1000)
::SetWindowExtEx(hDc, 1000, 1000, NULL);
::SetWindowOrgEx(hDc, 0, 0, NULL);
// ビューポート設定 (0, 0) - (10, 10)
::SetViewportExtEx(hDc, 10, 10, NULL);
::SetViewportOrgEx(hDc, 0, 0, NULL);
単純にウィンドウからビューポートへ(1/100)倍する変換です。
ウィンドウ、ビューポートのx座標をそれぞれ wx, vx として
-1000 <= wx <= 1000 の範囲で変換してます。
変換式は憶測ですが
vx = wx * (10 / 1000)
で求めていると思われます。
四捨五入の「入」、「捨」の境界は以下のとおり 0.46～0.47 です。
(これ以外の146, 246, ...、-154, -254, ... でも同様の結果です)
wx = -54 → vx = -1 (-54/100 → -0.54 → -1 + 0.46 → -1)
wx = -53 → vx = 0 (-53/100 → -0.53 → -1 + 0.47 → 0)
wx = 46 → vx = 0 (46/100 → 0.46 → 0 + 0.46 → 0)
wx = 47 → vx = 1 (47/100 → 0.47 → 0 + 0.47 → 1)
>>434
その方法だと>>423のバージョンAと同じになってしまうんです。
今は>>424のバージョンB方式の四捨五入の実装方法で迷ってるんです。
437:423
06/03/10 18:03:48
追加情報で、ウィンドウ領域とビュー領域の数値は32bit(int型)で設定可能なのですが
MSDNで調べたところウィンドウ領域は32bitを保証してビューポートは27bitしか保証しないと
明記されてます。
残り5bitを小数部とした固定小数点で計算とかをしているんですかね？
438:434
06/03/10 18:21:37
>>436
折角書いてやったんだから、ちゃんと読め！
いいか その>>424のバージョンB ってのは a/bの符号によって
符号負 ret = (2 * a - b) / (2 * b);
符号正 ret = (2 * a + b) / (2 * b)
としたいわけだろ？
符号を sgn +1/-1 なら
ret = (2 * a - b*sgn) / (2 * b);
だろが！
439:デフォルトの名無しさん
06/03/10 18:57:40
>>438
論外
ポイントになるのは、0.1刻みとして(-2.5～-1.6), (-1.5～-0.6), (-0.5～0.4), (0.5～1.4)
をどうやって同じグループにするかということ
440:デフォルトの名無しさん
06/03/10 19:21:54
素直に floor(val + 0.5) いっとく？
441:434
06/03/10 19:27:10
ああ、そりゃ悪かったな。 しかし多少修正すりゃいいことじゃないか
単に >>435の符号を入替えて
int div(int x,int y){
int sgn=x^y;
sgn=sgn>>31;
return (x-((-y^sgn)>>1))/y;
}
x/y = div(x,y)
-20/10= -2
-19/10= -2
-18/10= -2
-17/10= -2
-16/10= -2
-15/10= -1 -5/10= 0 5/10= 1 15/10= 2
-14/10= -1 -4/10= 0 6/10= 1 16/10= 2
-13/10= -1 -3/10= 0 7/10= 1 17/10= 2
-12/10= -1 -2/10= 0 8/10= 1 18/10= 2
-11/10= -1 -1/10= 0 9/10= 1 19/10= 2
-10/10= -1 0/10= 0 10/10= 1 20/10= 2
-9/10= -1 1/10= 0 11/10= 1
-8/10= -1 2/10= 0 12/10= 1
-7/10= -1 3/10= 0 13/10= 1
-6/10= -1 4/10= 0 14/10= 1
これでいいんだろ？
442:434
06/03/10 19:32:15
たぶん、
ホントは四捨五入でret = (2 * a + (b^t)) / (2 * b) を使いたかったけど2つある2倍が嫌なんで
ret = ( a + ((b^t)>>1) ) / b; としたら、プラス側が6で変化したんで
ret = ( a - ((-b^t)>>1) ) / b; として、まあマイナス側に-6で変化したっていいやで 計算量優先にしたんだろ
443:434
06/03/10 19:59:13
いや、もしかして
abs(x) の代わりに (x>>31)^x のようなのを使ってて出た誤差かな
444:デフォルトの名無しさん
06/03/10 20:05:54
(2*a + 2*a*a*b - b) / (2*b) + 1 - a*a
445:デフォルトの名無しさん
06/03/10 20:28:42
>>423
またおまえか。
446:423
06/03/10 21:07:51
みなさん、ありがとうございます。
とても参考になりました。
特に>>434さんの方法には脱帽しました。
異符号の場合に -1 と XOR して1の補数を用いるなんて思いもつきませんでした。
と言っても、まだ完全には理解できてはいないのですが
先にお礼を言っておきたかったので。
本当にありがとうございました。
447:434
06/03/10 21:28:04
ごめん。 変な方法使うより
#include <stdlib.h> に div という関数がある 除算とあまりを出す関数だ
div_t d=div(x+y/2,y);
if(d.rem<0) d.quot--; で d.quot を使えばいい
条件判断を無くしたいなら d.quot+d.rem>>31 でいい
たぶんコレが正解だろう
448:434
06/03/10 21:30:52
ようするに、結果見ると、変な四捨五入じゃなくて
普通の四捨五入をやりたいって事にやっと気付いた。 すまんな。
449:434
06/03/10 21:40:25
ちなみに試したコード
#include <stdlib.h>
int divd(int x,int y){
div_t d=div(x+y/2,y);
return d.quot+(d.rem>>31);
}
int divd(int x,int y){
div_t d=div(x*2+y,y*2);
return d.quot+(d.rem>>31);
}
結果はどっちも >>441 と y=10では同じになる
450:434
06/03/10 22:11:31
言い訳すると >>427 で
＞単純に0.5を足して切り捨てると除算結果が負数の場合に問題があるのです
に騙されてしまった。
単純に0.5を足して切り捨てるのをやりたかったのだろう。
ただ、X86では除算の結果が負数になる場合は余りも負数になる。
a/b＝ n余りsなら
a = n*b + s = s+b+(n-1)*b となる修正をすればいい
アセンブラで書けば、
cdq
idiv
sqr edx,#31
add eax,edx
と4命令
451:デフォルトの名無しさん
06/03/10 22:13:38
>>441は xが正でyが負のときおかしい。
かけ算はいってるけど
int func(int a, int b){
int absa = (a >> 31) ^ a;
return (a + absa*b + (b>>1)) / b - absa;
}
452:434
06/03/10 22:18:43
>>451
そうだね。他に y=1の時も >>441は変になるだろう >>449なら大丈夫な筈だ
453:434
06/03/10 22:21:39
アセンブラの sqr は sarのタイプミスだ >>950
アセンブラだと４行なのに
使わないと除算とmodを別に計算するか div 関数を使う必要があるのが面倒な所
div関数だと結果も構造体渡しだからメモリアクセスが入って遅くなる
454:デフォルトの名無しさん
06/03/10 22:27:09
今一状況がわかんないんだけど、divの定義見た?
あんなの使う気にならないんだけど。
455:434
06/03/10 22:34:07
>>454
だったらインラインアセンブラでやるといいよ。
cだけで書くなら
x+=y/2;
int r=x/y;
if( (x % y)<0) r--;
return r;
456:434
06/03/10 22:54:48
>>451
原理としては、 余りが負数にならないように巧くオフセットを加えてるわけだよね
巧い方法だけど、 a b が大きい時にオーバフローの問題が起きるね。
abs*a ではなくて
aよりも少しだけ大きい bの倍数 を計算させた方がいいのでは？
この場合 >>436 のように座標計算に使うのだから、 マッピングモード設定 時に予め計算させておけばいい
457:434
06/03/10 22:56:56
ああボケてるな マッピングモード設定 時にはaが判らないのだから予め計算出来る筈がない
458:デフォルトの名無しさん
06/03/10 23:12:33
学校の宿題なのですが、
廊下にたっていて、向かい側の壁にはたくさんの開くドア又は開かないドアA,B,C。。。。が無限にあって、
それを開くかどうか確認したい。
スタートはAとーAの間にいる。
。。。｜D｜C｜B｜A｜－A｜－B｜ーC｜－D｜。。。っとドアが続く
最初に地点から一番近い、開くドアを見つけたいが、動く距離をｘとして、
距離の総和がO(x)ペースになるように探したい。
例えば、A,－A,B,－B,C,ーCの順番で探していくと、
動く距離が、１、２、３、４、５,...nとなり、距離の総和は1/2*(n)*(n-1)となり、
O(X^2)のペースになるから駄目である。
っていう問題なのですが、何か良い探し法、アルゴリズムありますかね？
459:434
06/03/10 23:13:40
aよりも少しだけ大きい bの倍数 だけど
( abs(a/b)+1)*b でどうだろ？
除算が遅いなら | b|をシフトしていって |a| を超えた所でもいいか
460:434
06/03/10 23:21:43
>>458
で、開いてるか開いていないかの確率はどの程度なの？
というか確率を仮定して
右方に N1内で調べてみてなければ右側にN2個調べて 見つかる確率を求めてみたら？
右側で M番目に開けば左側でM番目まで調べ調べればいいでしょ
461:デフォルトの名無しさん
06/03/10 23:29:11
確率は問題には確定されてないです。
それも考えたのですが、例えば、3つずつの固まりで調べていくとして、
C,B,A,-C,-B,-A,
F,E,D,－F,－E,－D
距離を考えていくと、
（３＋１＋１）＋（３＋１＋１）＋
（６＋１＋１）＋（９＋１＋１）＋、、、
となって、総和はどうなるのでしょう。。。
462:デフォルトの名無しさん
06/03/10 23:40:17
初期位置より右側を線形探索形に (-A,-B,-C,...) するようにして
初期位置より左側を A , C , E と２個おきに移動 して末端 n で（奇数個偶数個で微調整か？）
.... F D B と戻ってくれば O(x) っぽくならない？
463:434
06/03/10 23:47:52
だいたいこういうのは2倍づつ調べるのを増やすんだろうけどなあ
464:デフォルトの名無しさん
06/03/10 23:51:11
>>458
左の方を一つ探す「A」
右の方を二つ探す「-A, -B」
左の方を四つ探す「B, C, D, E」
右の方を八つ探す「-C, -D, -E, -F, -G, -H, -I, -J」
この要領でいけないかな。
465:デフォルトの名無しさん
06/03/10 23:55:52
>>458
＞A,－A,B,－B,C,ーCの順番で探していくと、
＞動く距離が、１、２、３、４、５,...nとなり、距離の総和は1/2*(n)*(n-1)となり、
＞O(X^2)のペースになるから駄目である。
「調べないけど移動してる」に オーダーのコストかかってる？
466:デフォルトの名無しさん
06/03/11 00:06:37
＞＞４６４
そうすると、kブロックに区切って、
(1)+(1+1)+(3+1+1+1)+(7+1+1+1+1+1+1+1)+(15+1+1+1+1+1+...)+
= 1+1*2+3*2+7*2+15*2+....+?
467:デフォルトの名無しさん
06/03/11 00:08:01
立ち止まる＝調べる、
動く距離＝そこで調べるの意味だと思います。
468:デフォルトの名無しさん
06/03/11 00:31:55
>>464で、x番目に調べるまでの距離の総和をf(x)とすると、
f(2^n-1)
= 2*Σ{i=1..(n-1)}(2^i-1)
= 2*((2^n-2)-(n-1))
<= 2*2^n
2^(n-1) <= x <= 2^n-1のとき、
f(x) <= f(2^n-1)
<= 2*2^n
= 4*2^(n-1)
<= 4*x
よってO(x)
469:デフォルトの名無しさん
06/03/11 01:10:36
＞＞４６８
なるほど。
助かりました。
ありがとうございました。
470:デフォルトの名無しさん
06/03/14 22:27:00
(0,1)における実数の集合が、可算無限集合ではないことを背理法と対角線論法を使って証明するやつだけど、
いまいち何やってるか分からないんだよね。
分かった気にはなるけど、どうもしっくりこないっつうかなんつうか。
他に証明方法とかあるのかね？
471:デフォルトの名無しさん
06/03/14 22:38:27
>>470
有理数列と実数の部分集合に1対1の対応が作れる
有理数列は自然数→有理数の写像とみなせる
自然数→有理数の写像の濃度は アレフ0^アレフ0 ＝ 2^アレフ0
アレフ0 ＜ 2^アレフ0
（ある集合の濃度が N のとき、その冪集合の濃度は 2^N、
ある集合とその冪集合の間にはどうやっても全単写が作れない）
なので、可算濃度＜実数の濃度
472:デフォルトの名無しさん
06/03/16 13:32:51
冪集合がわからんヒトがいると見た。
473:デフォルトの名無しさん
06/03/18 08:50:19
数学板から誘導されて来ました。
QRを解析するプログラムを作ろうと思っているのですが、
誤り訂正複合のリード・ソロモン符号の複合の仕方が分かりません。
R=(r0,r1,r2,r3...,r25)
R(x)=(r0+r1x+r2x^2+...+r25x^25)
ここにri(i=0～25)は、GF(2^8)の元とする。
とあり、r0-r25に間違っていないデータ（0-255）を代入しているのですが、次のシンドロームを求める式でシンドロームが0になってくれません。
シンドロームSiを求める式
S0=R(1)=r0+r1+r2....+r25
S1=R(a)=r0+r1a+r2a^2....+r25a^25
データをr0-r25に代入して、それらをGF(2^8)の法100011101（a^8+a^4+a^3+a^2+1）で割っているのですが0になりません。
もう数日煮詰まっています。お願いします。何方かご教授して下さい。
474:デフォルトの名無しさん
06/03/18 09:42:13
>>473
誰かのコードを参考にするといいよ
例：
URLﾘﾝｸ(isw3.kankyo-u.ac.jp)
475:デフォルトの名無しさん
06/03/18 11:04:44
>>474さん、ありがとうございます。
ありがたく拝見させてもらいましたが、残念ながら書き込みの処理しか載っていませんでした。
（書き忘れて申し訳ございませんが、473で書いた部分はQRを読み取る部分の処理です）
他にもあるかもと思って「誤り訂正 QR」などで検索を掛けてみましたが、書き込みに関する部分ばかりで、
読み取り解析に関するサイトは見つかりませんでした。
JISの企画書もシンドロームを求めるとしか書いてありませんし、もう、完全に行き詰っています。
どんな些細な事でも結構ですので、アドバイスを頂けないでしょうか。
お願いします。
476:デフォルトの名無しさん
06/03/18 11:27:53
>>475
その部分のコード晒してみて、
+ は XORの事とか 掛算は足算の事とか、そこらへんは判ってるんだよね？
477:デフォルトの名無しさん
06/03/18 11:37:40
>>475
じゃあココのは見たの？ オレは中身はみてないけど
URLﾘﾝｸ(sourceforge.jp)
478:デフォルトの名無しさん
06/03/18 12:37:08
>>476さん、ありがとうございます。
＋は足し算で、掛け算は掛け算で計算していたので、直してみましたが、やはり０になってくれません。
コードはこのようになっています。
//求められたデータ語
int[]Data={
32, 65, 205, 69, 41, 220, 46, 128, 236, 42, 159, 74, 221,
244 ,169, 239, 150, 138, 70, 237, 85, 224, 96, 74, 219, 61 };
//a指数→整数
int[] a_int={1,2,4…（以下続いています）};
public void Syndrome(){
//求めるシンドロームの数を決定
int[]S=new int[8];
for(int i=0;i<S.length;i++){
for(int d=0;d<Data.length;d++){
S[i]=S[i]^(Data[d]+a_int[(d*i)%255]);
}
}
}
>>477さん、
このプログラムは知りませんでした。早速今から落として見て見たいと思います。
ありがとうございます。
479:デフォルトの名無しさん
06/03/18 13:24:07
>>478 やっぱり計算式が違うよ >>474のcalculate.javaをよく見てみて
480:http://www.vector.co.jp/soft/win95/util/se072729.html
06/03/18 19:44:49
TextSS のWindowsXP(Professional)64bit化おながいします
もしくは64bitにネイティブ対応したテキスト置換ソフトありますか？
481:デフォルトの名無しさん
06/03/19 23:37:58
ラジアンをぶつかった壁に対して面対称で
XだけYだけ90°ひっくり返すにはどうすればいいの？
482:デフォルトの名無しさん
06/03/19 23:56:28
いや言ってる意味が良くわかりませんから
483:デフォルトの名無しさん
06/03/20 00:24:24
ビリヤードか
484:デフォルトの名無しさん
06/03/20 00:45:38
vy = -vy;
vx = vx + 90/180*PI
485:デフォルトの名無しさん
06/03/20 11:03:21
>>483 ビリヤードなら90度というのがどこから来るのか・・・・
486:デフォルトの名無しさん
06/03/20 16:05:35
必ず90度で跳ね返るPONGでも作ってみるか
487:デフォルトの名無しさん
06/03/20 16:42:10
その場合、速度はどうなるのん？
488:デフォルトの名無しさん
06/03/20 17:22:36
必ず180で反射するコーナーリフレクターは実在するけど
必ず90度ってどうやるんだ？
489:デフォルトの名無しさん
06/03/20 17:24:03
三角関数？簡単なブロック崩しだったらそんなの使わんぞ
つーか、玉の軌道をＸ軸かY軸で反転すれば問題なし。
490:デフォルトの名無しさん
06/03/20 18:44:58
さて、ここで唐突に「三角関数」とか出てきたわけだが
491:デフォルトの名無しさん
06/03/20 18:52:43
「プログラマが今まで「これはすげえ」と思ったｹﾞｰﾑ」
の149からの流れがここに？
ｽﾚﾘﾝｸ(prog板:149-番)
492:デフォルトの名無しさん
06/03/20 19:24:06
URLﾘﾝｸ(www.dango-itimi.com)
斜面への衝突判定と反射1
493:デフォルトの名無しさん
06/03/23 07:46:12
学校の宿題なのですが・・・。
HはHASH関数で、p は(p-1)/2も素数であるような素数。
aは、1<a<p-1も満たす整数。
g=a^2(mod p)
H(x,y,z,t)=g^(xy+zt) (mod p)
このとき、Hはone-way関数であるが、collision-free関数ではないことを示せ。
なのですが、どなたか分かる方、助けてください。
494:デフォルトの名無しさん
06/03/23 12:28:39
定義は知らんがアバウトに考えて、
剰余が絡んでる段階で多対一関数だから1方向だろうし
collision-freeではなさそうだわな。
証明は2つの値が実際に1個の値になる例を計算すればいいんじゃね？
495:494
06/03/24 16:59:01
エエカゲンに書いたのに誰も突っ込まない…。
ほ、放置プレイ？
496:デフォルトの名無しさん
06/03/24 18:30:11
定義がないのでなんともはや
497:デフォルトの名無しさん
06/03/28 08:18:12
sin(x)/x
Ｑ１ って関数に名前を付けたいけど適切な名前は？
Ｑ２ 浮動小数点なので計算方法は単純に
abs（x)<0.0001 の時は1-x*x/6 でなければ そのまま計算でいいよね？
498:デフォルトの名無しさん
06/03/28 08:53:02
キャラの座標は
左上と真ん中
どちらのポイントを保持して使うべきですか
499:デフォルトの名無しさん
06/03/28 08:55:22
>>497
sine_x_per_x()
500:デフォルトの名無しさん
06/03/28 09:01:48
>>498
いまどきどこでもいい。
処理によって必要な座標は違う。例えばサイドビューのジャンプアクションなら足元座標も使う。
必要な座標を計算するメソッドがあればそれでよい。
数学関係ない。
501:デフォルトの名無しさん
06/03/28 12:19:04
>>497
それは一般的にsinc関数と呼ばれている。
502:497
06/03/28 12:41:21
>>501 ありがとう
503:デフォルトの名無しさん
06/03/28 17:19:04
>>498
RPGの座標には、マップ上の座標と表示する座標があるが、
マップ上の座標で保存する。
表示する時には、表示する座標に変換して表示する。
504:デフォルトの名無しさん
06/03/28 17:58:28
>>503
キャラといえばRPGしか連想できないゲーマーですか?
505:デフォルトの名無しさん
06/03/28 23:55:29
すまん。
でも数ピクセル単位で動かす事になるとおもうから、
その動かせる単位の位置を保存して、
表示する位置に変換するって感じで使えるかも。
506:デフォルトの名無しさん
06/03/29 10:10:24
座標は数学でしょ
507:デフォルトの名無しさん
06/03/29 17:34:46
２Ｄゲームを作っているのですが、
640×480の画面に32×32の画像をしきつめようとすると、
右端と下端がきれいにそろわず、ちょっとはみだしたりしまいます。
これって例えば何が原因で起こるのでしょうか。
508:デフォルトの名無しさん
06/03/29 17:45:27
■■■■■■■■■■■■■■■■■■■■ どういう状況なの？
■■■■■■■■■■■■■■■■■■■■ 20x15 で普通に敷き詰められるよね？
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■
509:デフォルトの名無しさん
06/03/29 18:10:03
>507
まさか浮動小数点演算が介在してたりせんだろうな？
510:デフォルトの名無しさん
06/03/29 18:33:53
>>507
>例えば何が原因で
・計算間違い
・勘違い
・お門違い
511:デフォルトの名無しさん
06/03/29 18:39:10
基地（ｒｙ
512:デフォルトの名無しさん
06/03/29 20:09:24
>>507
右端は揃うんじゃﾏｲｶ？
マジレスすると、敷き詰める画像のサイズが640と480の公約数である必要がある。
513:デフォルトの名無しさん
06/03/29 20:17:27
どうしても正方形が好きならね。
514:デフォルトの名無しさん
06/03/29 22:22:06
480って32で……あれぇ？うぅー？
515:デフォルトの名無しさん
06/03/29 23:42:36
勘でいうとAdjustWindowRectしてないから
516:デフォルトの名無しさん
06/03/30 09:24:33
テクスチャで貼っててピクセルがずれている悪寒。
517:デフォルトの名無しさん
06/03/31 01:31:23
>>498
>>507
お前さ
いい加減あちこちにマルチポストするの止めろよ
もしくは解決したなら解決したと全てのスレに書いて回れ
518:デフォルトの名無しさん
06/03/31 23:45:54
地球の下側は反対に回っているってどういう意味ですか？
上も下も繋がっているんだから回る方向は同じじゃないの？
519:デフォルトの名無しさん
06/03/32 02:22:08
>>518
オーストラリアの世界地図 でググってみるといいかも
方向という単語の意味の問題だから、ここはスレ違いかも
520:デフォルトの名無しさん
06/03/32 03:18:09
北半球の人間はオーストラリアが下だろと認識している
南半球の人間はロシアが下だろと認識している
521:デフォルトの名無しさん
06/03/32 04:01:57
南半球では西から日が昇るんだよね?
522:デフォルトの名無しさん
06/03/32 11:13:29
右からだよ
523:デフォルトの名無しさん
06/04/02 08:07:38
ラグナロクみたいなオンラインゲームでステータスを表示したり、
所持アイテムを表示したりする、ウィンドウについて。
これって、どうやって実装してるんでしょうか？
ただ単に固定されてるウィンドウをつくるなら、ウィンドウのテクスチャ描いて、
それを張って、座標が決まっているのでそこに文字やらなんやら表示すれば良いと
思うんですけど、
オンラインゲームに存在するウィンドウって、windowsのウィンドウみたいに
マウスでクリックすると自由に動かすことができますよね？
これって、APIで一つ一つ子ウィンドウを作って、そこに表示させてるんでしょうか？
もしくは、他に方法とかあるんでしょうか、助言をよろしくお願いします。
524:デフォルトの名無しさん
06/04/02 08:27:33
ｽﾚﾘﾝｸ(gamedev板:543番)
525:デフォルトの名無しさん
06/04/02 08:28:25
>>523
つ[DirectX]
後スレ違い。
526:デフォルトの名無しさん
06/04/02 14:00:59
DirectXは直接的にはかんけいないだろ
527:デフォルトの名無しさん
06/04/03 04:30:12
>>523
>>517
528:デフォルトの名無しさん
06/04/07 13:54:31
>526
「数学と算数」よりは関係あるけどな。
529:デフォルトの名無しさん
06/04/24 11:15:56
>528
そうか？
530:デフォルトの名無しさん
06/04/24 13:10:28
>>528
クリッピングや論理演算は数学の範疇だと思うんだけどな
531:デフォルトの名無しさん
06/04/25 12:28:25
ﾊｧ?
DirectXはスレ違いだし、クリッピングの話なんてどこにも出てないが？
532:デフォルトの名無しさん
06/04/25 14:21:17
DirectX 描画者たち
窓の中の昴～♪
533:ルカ
06/04/26 16:58:08
sgn←これなんて読むの？だれかがシグネーチャー？って読んでたんだけどそれでオッケイなんですか？
てかこれどういう意味？符号関数ってなんですか・・・
すいませんここはプログラムとかそういうサイトっぽいけどたぶんここしか頼れる所がないので・・・
大学の数学で出てきたんですけどもしよろしければ誰か教えてください（＞＿＜）
534:デフォルトの名無しさん
06/04/26 17:02:02
もうシグネチャーでいいと思うよ。
まあ、マジレスすると、符号関数でぐぐればいくらでも説明出てくる。
535:デフォルトの名無しさん
06/04/26 18:13:04
現在、固有値および固有ベクトルを求めるプログラムを作成しているのですが
固有ベクトルの求め方で質問させていただきたいことがあります。
固有値はハウスホルダー変換と２分法で求めました。
その後、逆反復法を用いようと思っているのですが、
初期ベクトルの決め方と、繰り返し回数がわからず困っています。
どなたか教えていただけないでしょうか？
536:デフォルトの名無しさん
06/04/26 20:23:48
sgnと関数でぐぐるだけでも出てきそうなもんだが試した訳ではない。
537:デフォルトの名無しさん
06/04/27 01:34:48
sgnでググってみたら一番上がFortranの(だと思う)sgn関数の説明だった。
sgnの読み方はともかく、意味は分かるだろう。符号関数とも書いてるから
探しているものという確認も取れるし。
そしてシグネーチャーでオッケイかを知りたければシグネーチャから思いつく
綴りを全部辞書で調べろ。
538:デフォルトの名無しさん
06/04/27 02:01:54
>>535
初期ベクトルは、求めたい固有ベクトルの成分がゼロ、
もしくは、よほどゼロに近くない限りなんでもいいんじゃない？
ランダムなベクトルにするとか。
例え、偶然にも求めたい固有ベクトルの成分がゼロの初期ベクトルを
選んでしまったとしても、なんだかんだで誤差が出てくるので、なんとかなるかも。
収束は遅くなるだろうけど。
繰り返し回数は、求めたい精度に達するまでやればいいと思う。
Aを行列、aを固有値、xを求めた固有ベクトル、として、
(x,Ax)/(x,x)を計算すれば、固有値aの近似値が求まるから、
その精度を、既に求まっている固有値aと比較するとか。
539:535
06/04/27 11:26:58
なるほど、ありがとうございました。
参考にさせていただきます。
540:デフォルトの名無しさん
06/05/03 12:47:46
行列を使って非斉次の連立方程式を解くんだが、
行列の成分の
90%が0
8%が1
2%がその他
という行列を解くには
どんなアルゴリズムを使えば高速に解ける？
こういう行列に限り高速にできるとか
そんなアルゴリズムないかなと思ったんだが。
541:デフォルトの名無しさん
06/05/03 14:35:25
どこが非ゼロなのか、という情報がないとなんともいえない。
非ゼロの位置に特徴が無い場合は、行列をリスト表現して計算するくらいしか。
542:デフォルトの名無しさん
06/05/03 17:01:03
>>541
サンクス
非ゼロの位置に規則性はないわ。
あきらめとく。
543:デフォルトの名無しさん
06/05/03 18:30:42
"sparse matrix"でｸﾞｸﾞれば英語ばかりだが参考になりそうなサイトが出てくる
544:デフォルトの名無しさん
06/05/05 01:27:02
1:30～
たけしのコマネチ大学数学科
ｽﾚﾘﾝｸ(livecx板)
545:デフォルトの名無しさん
06/05/07 17:26:16
>542
非零が疎な行列だと反復法系のアルゴリズムが案外早いぞ。
546:デフォルトの名無しさん
06/05/23 08:07:13
朝倉から「コンピュータ代数ハンドブック」、定評のあるModern Computer Algebra 2nd ed.の
待望の翻訳!!、なる案内がきたが、定評と待望についてよろしく。
しかし\31,500とはずいぶんだな。
547:デフォルトの名無しさん
06/06/15 10:42:40
保守
548:デフォルトの名無しさん
06/07/16 09:13:35
保守
549:マイク ◆yrBrqfF1Ew
06/07/19 14:31:54
おい以下の問題がわからないので中卒の俺でもわかるようにPerlのコードをまじえて教えろ。
n個の区間Ii = [ai, bi](i=1,2,...,n)が与えられる時重なりを持つ区間の対を
全て列挙したい。なお[ai, bi]は実数の集合{x∈R | ai <= x <= bi}を表し、
二つの区間IiとIjが重なりを持つとは[ai, bi]∩[aj, bj]が空集合でないことを
意味する。全てのi = 1,2,..,nに対してaiとbiは整数でai<=biを満たし、
また任意のiとj(i != j)に対してai != ajを仮定する。区間のデータは
端の値aiとbiが配列で与えられており2つの数の大小比較や四則演算などの基本操作は
全てO(1)時間で可能とする。
(i) 区間対全てに対してそれぞれ重なりの有無を調べて
該当するものを列挙する方法が要する時間量を述べよ。
(ii) 重なりを持つ区間対の総数をkとする時、そのような区間対を列挙する
O(nlogn+k)時間のアルゴリズムを与えよ。
(iii) 重なりを持つ区間対を列挙するのではなく、その総数kのみを出力する
O(nlogn)時間のアルゴリズムを与えよ。
550:デフォルトの名無しさん
06/07/19 15:07:18
Perl 以外でもいいですか？
551:デフォルトの名無しさん
06/07/19 15:23:21
>550
>549に代わってお願いします。
ぜひC++で（ry
552:デフォルトの名無しさん
06/07/19 15:23:34
>>糞ｺﾃ
そういう態度だから何処へ行っても嫌われる。
553:デフォルトの名無しさん
06/07/19 21:59:50
>549
死に晒せｳﾞｫｹ
554:デフォルトの名無しさん
06/07/20 07:11:30
550 じゃないが
>>551
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
方針は以下：
(1) は自明．
(2) はソートして左から数える．ソートしたおかげで単調性が得られ，
一度交わらなくなったらそれより先を調べる必要がなくなる．
(3) は (2) でどこまで調べないといけないかを二分探索を行う．
555:デフォルトの名無しさん
06/07/20 08:09:59
拙いPerlですが。
URLﾘﾝｸ(sourcepost.sytes.net)
(i) 区間対の個数はO(nn)、重なりの有無の判定はO(1)だから、全体でO(nn)。
(ii) >>554に同じ。
(iii) 与えられた区間の始点と終点を列挙し、ソートし、各点に何個の始点・終点が重なっているか調べる。
区間のネストの数を把握しながらこの列を走査して重なりの総数を得る。
実際のコードでは始点・終点の個数の計算と最後の操作を一つのループで行っている。
556:マイク ◆yrBrqfF1Ew
06/07/20 19:23:08
>>554-555
･･･
２ｃｈネラにこんなことを言うのもあれだが
お前らすげーな。
どこの金子勇的風貌の京大院生だ？
557:デフォルトの名無しさん
06/07/20 22:30:46
大学で情報やれば大体やるぞ。
今からでも勉強してみたらどうでい。
558:デフォルトの名無しさん
06/07/30 08:15:10
二次元上の多角形の面積を求めるには外積で一発ですが、
三次元上の多面体の体積を求めるには何か方法はありませんか？
559:デフォルトの名無しさん
06/07/30 10:47:51
O = (0,0,0), A = (ax,ay,az), B = (bx,by,bz), C = (cx,cy,cz)
４面体OABCの体積は
1/6( ax by cz + ay bz cx + az bx cy - az by cx - ax bz cy - ay bx cz )
560:デフォルトの名無しさん
06/07/30 10:49:24
外積っていうより行列式に見える……。外積と行列式って関係あったっけ？
561:デフォルトの名無しさん
06/07/30 11:00:04
そりゃあるさ
562:デフォルトの名無しさん
06/07/30 12:06:07
>>558
外積
563:デフォルトの名無しさん
06/07/30 16:12:50
n次元体積を求めるにはベクトル出して行列式で一発じゃないのか？
564:デフォルトの名無しさん
06/07/30 16:14:36
3次元なら体積は (a×b)・c = det(a b c)だし
565:デフォルトの名無しさん
06/07/30 18:27:31
精度や対応できる形状をどこまでの範囲にするか決めないとな
体積を求めたい多面体が凸でない場合は４面体の和に分割するところが面倒かもよ
凸多面体でも分け方によって誤差が変わってくるからそんなに簡単ではないかもよ
566:デフォルトの名無しさん
06/08/06 16:49:43
おのおのの面に対して、原点とその面でつくられる錐体の符号付体積を足せばいいんでないの？
567:デフォルトの名無しさん
06/08/06 18:06:17
向き付けはどうすんのよ？
568:デフォルトの名無しさん
06/08/06 20:54:07
>566
対象が凸多面体で原点を多面体の内部か表面にとればそれは正しい
569:デフォルトの名無しさん
06/08/06 21:45:34
>>568
符号付き、というのはたぶん
原点から見て裏面が見えてるときはマイナスの体積、ということだろうから
そうすると原点に関して星状であるという条件はいらなくなるよ
Ａが星状というのは原点とＡの任意の点とを結ぶ線分がＡに含まれることね
570:デフォルトの名無しさん
06/08/06 23:55:55
あ、ほんとだ
571:デフォルトの名無しさん
06/08/07 12:48:29
NURBS曲面同士の衝突判定がしたいんだけど
便利なライブラリ or 公式とかある？
もしもなかったら、
衝突判定がしやすい曲面の表現方法教えてもらえませんか。
572:デフォルトの名無しさん
06/08/07 21:29:19
どんなものを表現したいのかね
573:デフォルトの名無しさん
06/08/07 21:41:17
NURBSやベジェのように、制御点を移動することで
形状を簡単に変えることができるものであればいいんですが、
球も表現したかったのでNURBSを考えていました。
574:デフォルトの名無しさん
06/08/08 11:21:05
>>571
NURBS曲面かどうか調べてないが、Newtonとか言うGAME向けの物理演算ライブラリがある
575:デフォルトの名無しさん
06/10/01 18:50:02
当選小計率 （数．数％） ＝ 当選小計 ÷ 販売額 × １００倍％
当選口指数 ｛数．数｝ ＝ 当選口数 ÷ 販売口数 × １００万倍
URLﾘﾝｸ(sea.advenbbs.net)
576:デフォルトの名無しさん
06/10/04 20:30:01
中学あたりからの学習要綱を網羅した数学ドリルサイトみたいなのないですか？
577:デフォルトの名無しさん
06/10/12 11:02:11
サンプルコードが理解出来ないレベルなら、素直に諦めて勉強し直した方がいい。
578:デフォルトの名無しさん
06/10/12 11:02:53
ｺﾞﾊﾞｰｸ
579:デフォルトの名無しさん
06/11/03 10:21:15
正射影について教えてください。
マウス（2次元）座標をゲーム画面（3次元）の座標に
変換したいんだけれど、
やり方がわからないです。
[やりたいこと]
大航海時代Onlineのように、
「キャタクターの行先（目的地）」を「地面をマウスクリックする」ことにより
指定し、その後、キャラクターが動き出す。
ということをやりたいと考えています。
580:デフォルトの名無しさん
06/11/03 10:29:29
>>579
DirectXを使っているならDirectX隔離スレへ。
その他3D表示ライブラリを使っているならそれらのスレへ。
そうでないなら自分で勝手に計算汁。
581:579
06/11/03 10:37:51
>>580
スレ違いスマソ。
DirectX隔離スレ逝ってきます。
582:デフォルトの名無しさん
06/11/23 14:10:24
グレゴリウスの定義を用いて入力した日が何曜日であるか、を表示するプログラムのアルゴリズムってどんな感じになるかわかりますか？
ちなみに
・グレゴリウスの定義
・西暦１年１月１日は月曜日
・１年３６５日だが、閏年は３６６日
・４または４００で割り切れる年は閏年
・１００で割り切れるのは閏年ではない
もしわかった方いましたらお願いします
583:デフォルトの名無しさん
06/11/23 14:15:04
>>582
C++の擬似コードだと、こんな感じかなぁ・・・
main(){Youbi 曜日; カレンダーを見る(新聞の日付, &曜日);
if (時計の時間<新聞配達時間) 曜日.進める;
return 曜日;}
584:デフォルトの名無しさん
06/11/23 15:01:22
>>582
普通はAPIを使う。
こんな所で質問してる奴が組んだ物は怖くて信用おけないから。
関係無いけど、ANSI C準拠のtime()関数系の1970/01/01 00:00:00からの通算秒で
有効桁31bitの場合は、全部閏年で換算しておｋ。
585:デフォルトの名無しさん
06/11/23 15:06:49
int zeller(int year, int month, int day)
{
if (month < 3) {
year--; month += 12;
}
return (year + year / 4 - year / 100 + year / 400 + (13 * month + 8) / 5 + day) % 7;
}
586:デフォルトの名無しさん
06/12/10 12:20:07
URLﾘﾝｸ(bal4u.dip.jp)
にあるprime-test()で多倍長整数の場合、最初に判定を間違える数って何？
587:デフォルトの名無しさん
06/12/10 13:01:52
>>582
マジレスすると西暦1年1月1日にはまだグレゴリオ暦は発明されていなかった罠。
588:デフォルトの名無しさん
06/12/10 15:35:33
>>587
遡及的に定義できる。
589:デフォルトの名無しさん
06/12/10 17:39:40
>>586
ミラーラビンテストでぐぐったら強擬素数ってのが出てきた。
あとは頑張れ。
590:デフォルトの名無しさん
06/12/10 20:48:11
>>586 底を何にするかで変わるから、一般的にパッと見つける方法はない。なので一つ一つ調べなさい。
>>589 強擬素数はフェルマーテスト
591:デフォルトの名無しさん
06/12/11 02:24:03
フェルマーテストで誤判定される数は、擬素数とかカーマイケル数。
適当いったらだめなんじゃね。
592:デフォルトの名無しさん
06/12/17 00:24:50
すいません、スレ違いかも知れませんが
他に適当なスレが見つからなくて。
私は会社の事務員なのですが、
手間のかかる手作業がありまして、パソコンにやらせたいのです。
職場の人員のスキル的に見て、自分でやるしかない状況です。
エクセルのVBAで何度かプログラムを組んだことのあるレベルです。
以下が問題の概要です。
1から100までの整数の並びがある。
そのうちランダムに20個程度の数が欠番となっている。
この状態から、残った数を並べ替え、
隣り合う数同士の差の絶対値が全体でなるべく等しくなるように、
つまり等間隔に並ぶようにしたい。
ここ一ヶ月くらい悩んでみましたが、アイディアが浮かびません。
何か既存のアルゴリズムで、応用できそうなものを紹介してもらえませんか。
593:デフォルトの名無しさん
06/12/17 00:31:57
>>592
判りにくいな。例えば、1, 2, 90, 91があったら1, 90, 2, 91に並べ替えるってことか?
#前者は隣同士の差が1, 88, 1で、後者は89, -88, 89だから後者の方が差の絶対値はほぼ均等になる。
594:デフォルトの名無しさん
06/12/17 00:39:09
>>592
総当りで調べるとかかなぁ。
「隣同士の差」の分散辺りを評価基準にして、全部の組み合わせ試して一番分散の小さいのを選ぶ。
595:592
06/12/17 00:52:03
>>593
わかりにくくてすみません。
実例を出すべきでした。
まさに、その後者のように並べたいのです。
今は人間がエクセル上で手作業であれこれと
数値を入れ替えし、納得いく結果になるまで
３日はかかってしまいます。
>>594
分散、とは統計学の用語ですか。
調べてみます。
596:デフォルトの名無しさん
06/12/17 06:08:03
80の総当りだと約10^119通り、３日じゃ終わらん。
単純に、小さい値と大きい値で２つに分けて、ソート後交互に配置じゃだめなん？
597:デフォルトの名無しさん
06/12/17 08:18:01
インターリーブ決定みたいなもんかな。
>596でよさそうだけど。
598:デフォルトの名無しさん
06/12/17 12:29:10
たとえば
1, 22, 23, 24, 25, 26, ..., 99, 100
というデータに対して>>596をすると
1, 61, 22, 62, 23, 63, 24, 64, ..., 59, 99, 60, 100
となって、「隣同士の差」のレンジは20にもなってしまう
しかしたとえば
1, 22, 42, 23, 43, 24, 44, 25, 45, ..., 39, 59, 40, 60, 41, 61,
81, 100, 80, 99, 79, 98, 78, 97, ..., 64, 84, 63, 83, 62, 82
というほうほうならレンジは2
599:デフォルトの名無しさん
06/12/17 16:18:54
>596
それならソートしただけのデータでもｲﾝｼﾞｬﾈ?
相対的な距離に関する最適解は総当りじゃないと求まらないんじゃない？
しかも「分散の小さい物」という条件だから足切りも出来ない。
600:デフォルトの名無しさん
06/12/17 22:37:12
判定関数を>>598のいうようなレンジとかにすれば枝切りもできるようになるね
601:デフォルトの名無しさん
06/12/21 21:47:49
RSA暗号を実装しようとしてて、2048ビットの鍵長の元に暗号化・復号を行っています。
整数乗算についてなんですが、2048ビット程度だと、fftかまして乗算しても恩恵はない。
と聞きました。実際のところはどうなんでしょうか？どなたか検証サイトなどご存知ではありませんか？
602:デフォルトの名無しさん
06/12/22 01:05:13
FFTの計算量評価の式から実際に求めるしかないね。
乗算が加算よりどれだけ遅いかも評価に入れなきゃいけないだろうし。
603:デフォルトの名無しさん
06/12/22 01:45:31
FFTの時間は実装レベル次第だから、実際に組んで比較するのが一番。
604:デフォルトの名無しさん
06/12/22 12:31:04
>>601
RSA の乗算＋剰余演算の場合、FFT による方法じゃなくて、
Montgomery multiplication っていう高速化手法があるよ。
検証したことはないけど、2048 ビット程度では FFT の効果はない
あるいは逆効果ってのはそうだと思う。
せめて1万ワードくらいの長さはないと。
605:デフォルトの名無しさん
06/12/22 12:37:35
ああ、あと、ワード長が2のべきになってる場合、
上位・下位半分ずつ、再帰的に計算することで
乗算回数減らす方法もある。
下位桁の乗算結果使って、上位桁の乗算をサボる。
昔、RSA のプログラムの最適化の仕事したことあるけど、
「単純に畳み込みで乗算 ＆ 引き放し法的な剰余」を
「再帰乗算 ＆ Montgomery 乗算法」に変えたら
鍵長256bitでも動作速度を250倍以上速くできた。