トップページ⇒math
437コメント91KB

¶¶¶　数学と電子計算機　¶¶¶

■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん2006/05/27(土) 10:26:04
数学と電子計算機の関係は密接だ。
電子計算機でどんどん数学やろう！
0232１３２人目の素数さん2007/06/24(日) 00:58:20
つ http://sourceforge.net/project/showfiles.php?group_id=1355
0233エレガントな解答を求む2007/06/24(日) 06:01:44
>>231
(EXPT 3 960) is not a function name
と出てevaれないんですけど(;´Д`)
0234エレガントな解答を求む2007/06/24(日) 06:21:19
あ、出ました出ました
あー　なんかCでシコシココーディングするのが莫迦莫迦しくなってきた(;´Д`)
0235エレガントな解答を求む2007/06/24(日) 08:23:22
>>198　さん
ちょっと質問です

nについての方程式：(3^960-1)/4^n∈N　を解いて
解を全て列挙せよ

はどうやって解けばよろしいでしょうか？
0236orz 2182007/06/24(日) 09:20:40
>>218
>>223
式(3)(6),　b >= 1, d = 0 のときのみ、　最後の-V_p(d) は -V_p(b)-m
と書きかえる。(もともとは、-V_p(b p^m + d) という項で、こう書けば場合分けはいらなかった）

よく見直すと、その -V_p(b p^m+d) の項は d がゼロのときは出ない「おつり」であることが判明 orz

V_p( C(ap^m , bp^m+d) ) = m + V_p(C(a, b)) + V_p(a-b) - ((d>0) ? V_p(d) : 0)

? : は　Cの３項演算子です。これを(3)の修正版とします

>>235
4^t = 2^(2t) なんだから、あらためて解く必要はないのでは
（解くプログラムを作れという課題ならともかくとして）

なおロシア式はいまのところ割る数が素数 p （直上の議論で素数べき)にしか対応してません。
4 より　6 とかですかね

あと lisp で　log に誤差がでないかちょっと心配（中で底が 2 のときは別処理してるのかな。
とすると 2 を別の数 に変えた問題で使うときは要注意かも
0237間違い2007/06/24(日) 09:21:53
>>235
計算するまでも無く
n = 1, 2 だ！
0238間違い2007/06/24(日) 09:29:54
>>237
n = 1, 2, 3, 4
の間違い…
02391982007/06/24(日) 10:46:50
>>235
2 を 4 にするだけでいいんじゃない

>>236
> log に誤差
じゃあ素直にこんなのとか。有理数しか使ってないので安心。
(do ((x 0 (1+ x))
     (y (1- (expt 3 960)) (/ y 2)))
    ((not (integerp y)))
  (print x))
0240間違い2007/06/24(日) 11:04:23
>>239

(do ((x 0 (1+ x))
(y (1- (expt 3 966661)) (/ y 2)))
((not (integerp y)))
(print x))

でやってみて？
02411982007/06/24(日) 11:15:11
>>240
それ無理ｗｗ
0242218 2362007/06/24(日) 12:26:12
>>239 納得 EXPT も、もしやばければ同様、ですな
0243１３２人目の素数さん2007/06/24(日) 13:05:24
そもそも問題が大して面白く無い件
0244１３２人目の素数さん2007/06/24(日) 14:47:27
まあな。
0245１３２人目の素数さん2007/06/24(日) 14:52:56
>>240 m=0 でロシアの射程外だが mod 4 で考えて -1 の966661乗 -1 で -2 なので 2で割れる回数は 1 か。
0246エレガントな解答を求む2007/06/24(日) 16:26:09
あ、すいません
結局

問題
>>235

は解けたのでしょうか？
0247１３２人目の素数さん2007/06/24(日) 16:48:08
>>246 アンタいろんな意味で大物や
0248エレガントな解答を求む2007/06/24(日) 17:11:50
結局自分で解いてみました
Celron 2.8GHz Mem 1GB
で約2.5秒ほどでした
http://amezolog.hp.infoseek.co.jp/source/up6057.jpg
http://amezolog.hp.infoseek.co.jp/source/up6058.jpg

目標は、あるコンピュータを使って、0.2秒くらいにチューニングすることです
0249１３２人目の素数さん2007/06/24(日) 17:58:17
def a():
　　x=3**960-1
　　i=0
　　while x%2==0: x/=2; i+=1
　　return i
0250エレガントな解答を求む2007/06/24(日) 20:54:14
>>249
何語ですかぁ〜？

バグってるし
0251１３２人目の素数さん2007/06/24(日) 21:02:21
何という言語かは知らんが正しそうには見えるぞ
0252エレガントな解答を求む2007/06/24(日) 21:26:45
def a():
　　x=3**960-1
　　i=0
　　while( x%2==0){ x/=2; i+=1;}
　　return i

こんなかんじだったらわかるようなわからないような
眠い
0253エレガントな解答を求む2007/06/24(日) 22:09:10
def a():
　　x=3**960-1
　　i=0
　　while( x%2==0){
xx=x;
for(j = 0; j < i; j++, xx/=2){
if( xx%2 == 1){ printf("ATARI=%d\n", j); break;}
}
x/=2; i+=1;}
　　return i

こうですね

http://amezolog.hp.infoseek.co.jp/source/up6059.jpg

0.063 sec まで高速化？しました！？
0254エレガントな解答を求む2007/06/24(日) 22:12:03
インデントミス！！恥ずかしい

def a():
　　x=3**960-1
　　i=0
　　while( x%2==0){
　　　xx=x;
　　　for(j = 0; j < i; j++, xx/=2){
　　　　if( xx%2 == 1){ printf("ATARI=%d\n", j); break;}
　　　　}
　　　x/=2; i+=1;}
　　return i

こうですね

http://amezolog.hp.infoseek.co.jp/source/up6059.jpg

0.063 sec まで高速化？しました！？
0255ロシア2007/06/24(日) 22:17:12
>>254
x は本当のところどう計算したか興味あり
0256１３２人目の素数さん2007/06/24(日) 22:35:55
上のほうに並んでる数字の羅列、3^960 を4バイトごとに下から並べてるのかと思ったら違う？

こっちで計算したら下16バイトはこうなったんだけど
4082d184176febff4ef057ea089e1301
0257エレガントな解答を求む2007/06/24(日) 23:26:12
>>256
CPUなに使っておられますか？
当方Celron2.8G
0258エレガントな解答を求む2007/06/24(日) 23:30:58
>>255
はい　少々手抜きしております
http://amezolog.hp.infoseek.co.jp/source/up6061.jpg
0259１３２人目の素数さん2007/06/24(日) 23:35:22
Celeron だけど、こっちでやったことはCPU関係ないはず
3^960 を16進表示したら下32桁はどうなるかを計算した結果が >>256
0260エレガントな解答を求む2007/06/24(日) 23:49:40
>>259

print_bignumber(int i, BIGNUMBER *X){
　int j;
　printf("\n%d:", i);
　for(j=0;j < MAX_BIGNUMBER;j++){
　　printf("%08x", X->u[j]);
　}
}
0261エレガントな解答を求む2007/06/24(日) 23:50:46
printf("%16x", ...)
とやるんでしたっけ？
0262エレガントな解答を求む2007/06/24(日) 23:52:54
あ、octal でしたっけ？
だと
printf("%010x",..) ???
0263１３２人目の素数さん2007/06/25(月) 00:20:24
何を混乱してるのかわかんないんだけど
octal は8進数
0264１３２人目の素数さん2007/06/25(月) 00:31:51
8桁で、上は0で埋めるんだよね
%08x でいいんじゃね？
でも足し算の実装見ると最上位ビットはキャリーフラグ用になってる？
0265１３２人目の素数さん2007/06/25(月) 01:49:32
>>250
>>249はpythonという言語。x=3**960-1のところもそのまま動く。
0266エレガントな解答を求む2007/06/25(月) 06:35:02
>>264
int は32bit で32/4=8だから %08xでいいんですね。ラリってました

＞でも足し算の実装見ると最上位ビットはキャリーフラグ用になってる？
当たり　carry も見れたほうがデバッグ上安心だと思って

>>265
python て C のbreak; 制御語みたいの使える？あと switchとか
0267１３２人目の素数さん2007/06/25(月) 10:52:06
>>266
switchはないけど、breakならあるよ

>>249の同値な書き換え

def a():
　　x=3**960-1
　　i=0
　　while 1:
　　　　if x%2 != 0: break
　　　　x/=2
　　　　i+=1
　　return i
0268エレガントな解答を求む2007/06/25(月) 19:30:28
>>267
因みに計算時間はどのくらいかかりますか？63msより速いでしょうか
0269１３２人目の素数さん2007/06/25(月) 21:37:45
switchは嫌いだな。
0270エレガントな解答を求む2007/06/25(月) 21:45:57
switch構文こそエレガントなプログラムのエッセンスでは？
0271１３２人目の素数さん2007/06/26(火) 00:08:02
>>268
1000回平均で大体0.000053 〜 0.000054秒ぐらいらしい・・
一応pythonに似た言語のrubyでも計ってみたら、ほぼおんなじ関数で、平均0.000182 〜 0.000188秒くらい・・
02721982007/06/26(火) 00:35:53
そーか、複数回やって平均とればいいんだよな。
つーことで clisp にこれを評価してもらった。
(time (dotimes (a 10000)
        (do ((x 0 (1+ x))
             (y (1- (expt 3 960)) (/ y 2)))
            ((not (integerp y)))
          (print x))))

Real time: 1.953125 sec.
Run time: 1.953125 sec.
Space: 59506100 Bytes
GC: 113, GC time: 0.53125 sec.

ふむ。一回だとゴミはあまり出ないとして 0.14ms?
ちなみに print しなかったら 1.11 sec ぐらいだった。
あと出力はファイルにリダイレクトしないとえらいことになるかも。

>>270
そうなの？
0273エレガントな解答を求む2007/06/26(火) 06:46:26
>>272
漏れも１０回計算して平均とってみた　35ms 悔しい
でも　＞Space: 59506100 Bytes メモリ使い杉
時間*空間　で勝負したら負けないと思う

＞そうなの
今、perl で state machine 作ってるので
elsif elsif ・・・　でプログラムが汚い
0274エレガントな解答を求む2007/06/26(火) 07:12:18
あ、間違え　時間/空間
小せえな俺
02751982007/06/26(火) 09:23:47
>>273
elsif は汚いの？基準がよくわからん
0276エレガントな解答を求む2007/06/26(火) 19:00:01
>>275
lisper の方は　if( if( if( if()))))))) とかに美学を感じるのですか
0277１３２人目の素数さん2007/06/26(火) 19:35:54
switchはニューメリカルレシピで批判されてるね。

でも大掛かりなシステム組むんじゃないんだから、堅苦しいこといわないで、気軽に使えばいいと思う。
0278エレガントな解答を求む2007/06/26(火) 19:40:36
switch と enum の組み合わせでエレガントなプログラムになるとおもうんだけどな
確かに、大掛かりなシステムの場合はそれが、、、
0279１３２人目の素数さん2007/06/26(火) 19:43:06
switch文はif elseに比べて、実行速度が多少速くなる場合がある。
0280エレガントな解答を求む2007/06/26(火) 20:00:49
いや、やっぱり大規模なシステムでも switch 構文で書けるシンプルさが
必要なような、そうでないような、、、
02811982007/06/26(火) 20:27:49
>>276
いや、別にそうではないが。
というか大量の分岐を直接書くこと自体が好きじゃなくて、
可能ならばハッシュ表なり配列なりを参照して済ませたいなとか思う。
0282エレガントな解答を求む2007/06/26(火) 20:41:01
>>281
ハッシュも配列も複雑すぎる木がしますぅ
0283エレガントな解答を求む2007/06/26(火) 21:00:33
CPUが1MHzくらいしかなくて、メモリも1KB\3000くらいしてた青春時代
を過ごしたので貧乏性なんです
02841982007/06/26(火) 21:35:02
あーなるほど
なんとなくわかるかも
0285１３２人目の素数さん2007/06/26(火) 21:37:17
まあ　富豪的プログラミングといふのも　わからなくはないのですが
0286１３２人目の素数さん2007/06/27(水) 16:29:06
そういえば　＞大量の分岐
するようなプログラムなんて書いたことないや
0287１３２人目の素数さん2007/06/27(水) 18:27:48
300くらいに分岐なら書いたことあるが
「大量」ってのはどのくらいを指すんだろう？
02881982007/06/27(水) 21:20:33
分岐の数よりも全体の行数かも。
一画面に収まりきらないぐらいになると美しくないと感じる。
まあしょうがないことも多いんだけどね。パーサとか。
0289１３２人目の素数さん2007/06/28(木) 02:36:19
パーサなんかも関数のテーブルを参照するようにすれば
小さくまとめることも可能なんだが
そうするとかえって面倒なことになることもあるな。
02902862007/06/28(木) 20:47:15
昔クロスアセンブラ組んだ時、hashのお世話にはなりましたが
その後、lex,yaccに誘惑されて、、、、、、、、、、、、、、
結局今はSQLの勉強しています
0291１３２人目の素数さん2007/07/01(日) 19:20:10
AccessでＳＱＬ使えるの？
0292１３２人目の素数さん2007/07/02(月) 02:44:34
>>283
CPUが1MHzだったころにメモリ1k3000円で買えたっけ？
0293１３２人目の素数さん2007/07/06(金) 01:00:21
さあねえ・・・
0294１３２人目の素数さん2007/07/06(金) 01:29:13
8kで５万くらい出したおぼえがあるので
1k3000円ではちょっと無理かな‥
0295１３２人目の素数さん2007/07/06(金) 20:38:26
こんな話を聞くとコンピュータに金かけるのがあほらしくなってくるね。
0296１３２人目の素数さん2007/07/17(火) 21:46:45
さあ情報処理試験秋期申し込みが始まった！
02972972007/07/19(木) 22:26:01
2=9-7
02982982007/07/19(木) 22:39:55
2^√9=8
02992992007/07/19(木) 22:52:10
2=ceiling(log(9)+log(9))
0300１３２人目の素数さん2007/07/20(金) 21:44:26
情報処理試験出願しようかな？
0301デニス リッチー2007/07/21(土) 12:05:05
止めとけ
0302カーニハン2007/07/21(土) 12:49:49
いやいや、ぜひ出願しなさい
0303ニクラウス ヴィルス2007/07/21(土) 14:47:27
俺も仲間に混ぜてくれ。
0304１３２人目の素数さん2007/07/21(土) 21:20:23
いいけど、何か話題振ってよ。
0305ケン　トンプソン2007/07/21(土) 21:32:32
なになになになに？
0306石田晴久2007/07/21(土) 21:56:09
ベル研の皆さん、お元気ですか。
0307ビョ〜ン ストラウストラップ2007/07/21(土) 21:58:58
変な名前で悪かったな。大きなお世話だぜ、まったく。
0308１３２人目の素数さん2007/07/29(日) 00:16:55
情報処理技術者国試もソフ開あたりになるとわりと難しい数学でてこない？
0309名無しさん＠そうだ選挙に行こう2007/07/29(日) 03:20:13
国試ってなんだよ、というところはスルーして

算数しかありません、以上
0310１３２人目の素数さん2007/08/01(水) 01:15:49
情報処理技術者国試は難しかった・・・
３０歳でやっとこさ旧２種通った。
0311１３２人目の素数さん2007/08/01(水) 08:51:16
難しいのは数学的な所ではないけどな
0312１３２人目の素数さん2007/08/01(水) 19:19:18
情報処理技術者国試
制度が変わるようだな
0313１３２人目の素数さん2007/08/19(日) 19:09:52
情報処理技術者国試
今申し込んだ

さて、通るかな？
0314１３２人目の素数さん2007/08/19(日) 19:11:55
ＣＳでていないと欧米ではＳＥにもなれない。
0315１３２人目の素数さん2007/08/19(日) 21:45:38
ＣＳって？
0316１３２人目の素数さん2007/08/19(日) 21:53:48
かすたまーさーびす？
0317１３２人目の素数さん2007/08/19(日) 21:56:57
>>308
真面目にやるならそれなり鴨。
ただ、出題者も理論をさっぱり理解できていないのがこの世界。
バカでもまぐれでも答えさえ合えば良いんだよ！
0318１３２人目の素数さん2007/08/19(日) 23:53:29
情報処理技術者国試で必要な数学ってなんだろう？
２進数なんかの計算はとりあえず必要だな。
0319１３２人目の素数さん2007/08/20(月) 00:33:39
俺の知っている出題者、マージソートの計算量はしどろもどろだったよ。
つかクイックソートもバブルソートもｇｄｇｄ。
「とにかく覚えとけ」だってｗ
そんなレベル。
0320１３２人目の素数さん2007/08/20(月) 08:07:29
シェルソートの計算量について詳しく教えて下され。
0321１３２人目の素数さん2007/08/20(月) 10:02:18
>320
ソフ開の参考書にないかえ？
0322１３２人目の素数さん2007/08/21(火) 07:44:17
>>321
シェルソートのタイトな計算量評価は非常に難しいことが
知られている。常識だと思うんだが。
0323１３２人目の素数さん2007/08/30(木) 21:39:41
>>322
ぜひ教えて下され。
0324１３２人目の素数さん2007/08/31(金) 14:25:21
シェルソートについては、Ｄ・クヌースがいろいろと調べて本にまとめていた気がする。
0325１３２人目の素数さん2007/09/19(水) 22:38:50
高性能･大容量電子計算機でやるのにいいネタ探してます。
0326１３２人目の素数さん2007/09/20(木) 00:32:04
計算可能性理論
0327１３２人目の素数さん2007/10/02(火) 10:10:19
正方形の面積の計算。
0328１３２人目の素数さん2007/10/02(火) 11:07:08
チューリングマシンのシミュレーション
0329１３２人目の素数さん2007/10/07(日) 01:20:53
無限に長いテープか。
0330１３２人目の素数さん2007/10/30(火) 13:52:18
315
0331１３２人目の素数さん2008/01/04(金) 11:09:30
御目。
■ このスレッドは過去ログ倉庫に格納されています