[過去ﾛｸﾞ]
プログラミングのお題スレ Part13 (1002ﾚｽ)
プログラミングのお題スレ Part13 http://mevius.5ch.net/test/read.cgi/tech/1549160513/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
11: デフォルトの名無しさん [sage] 2019/02/03(日) 21:02:27.70 ID:Hf9VDUPT >>9 だったらそういう問題の出し方にしないと。 例えば、1から1億までの間の数字で平方根数は何個あるか。 かかった時間と、PC 環境を示せ また、処理できる最大に近い数字を示せ。 とかかな。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/11
12: デフォルトの名無しさん [sage] 2019/02/03(日) 21:37:11.53 ID:MY6f7I+S なんか変なのいるね http://mevius.5ch.net/test/read.cgi/tech/1549160513/12
13: デフォルトの名無しさん [sage] 2019/02/03(日) 21:40:28.27 ID:v4AFDwkt 浮動小数経由する実装だと整数部が53bit超えると判定出来ない(つまり64bit整数以上だと不適切) だから自前で浮動小数を経由せずに平方根の整数部分を求めることを考えるわけだけどナイーブにやると計算量が線型になるから二分探索やNewton(-Raphson)法で計算量減らすことを考えるわけだ http://mevius.5ch.net/test/read.cgi/tech/1549160513/13
14: デフォルトの名無しさん [] 2019/02/03(日) 22:02:19.65 ID:I0qputsI >>13 >>7で64ビット以上の数も判定出来てるけど。。。 (0が偶数ならTrue、奇数ならFalse) 小数点以下が0か(n.0かn.41421356みたいな形か)どうか見てるだけだし。 この辺はsqrt関数の性能に依存するだろうけど。 n = 100000000000000000000 m = 10000000000000000000 print(isSqr(n)) print(isSqr(m)) 出力 True False http://mevius.5ch.net/test/read.cgi/tech/1549160513/14
15: デフォルトの名無しさん [sage] 2019/02/03(日) 23:09:07.55 ID:CD+d7Abc >>14 100000000000000000001がtrueになったりはしない？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/15
16: デフォルトの名無しさん [sage] 2019/02/03(日) 23:21:43.21 ID:CD+d7Abc >>14 https://ideone.com/IntAcn http://mevius.5ch.net/test/read.cgi/tech/1549160513/16
17: デフォルトの名無しさん [sage] 2019/02/03(日) 23:32:49.30 ID:J7OBWIJA >>14 何言ってんのおまえ http://mevius.5ch.net/test/read.cgi/tech/1549160513/17
18: デフォルトの名無しさん [sage] 2019/02/03(日) 23:38:52.32 ID:v4AFDwkt >>14 無能 たまたま判定出来るケースだけ抽出してるだけじゃねぇか http://mevius.5ch.net/test/read.cgi/tech/1549160513/18
19: デフォルトの名無しさん [] 2019/02/03(日) 23:57:14.35 ID:Hf9VDUPT >>13 それもわかる。 だったら解き方の最初にこういう目的で解いたとか書かないとね。 だから、解ける最大数値も書いたら良いと書いたんだが。 ちなみに、>>1 の1億までの数字は、iPhoneで28秒だった。 >>15 False になるよ。iphone のpythonista また、言われたようにバイナリサーチ法や、巨大数のバイナリー検索も試してみたが、単純検索よりずっと時間がかかった。 ま、これは言語にもよると思うから何とも言えないが。 スクリプト系はステップ数が短
い方が効率は良さそうだな。 >>18 だからさ、どこまでやるか条件を出せよ。 そしてサンプルを示してみたら？ 実行時間も入れて。 プログラムと言うのは、使う現場で目的が違うんだから目的がわからなければ良い悪いなんて言えないだろ。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/19
20: デフォルトの名無しさん [sage] 2019/02/04(月) 01:09:58.80 ID:tmXRmKR0 このお客さんはどこから来たんだ http://mevius.5ch.net/test/read.cgi/tech/1549160513/20
21: デフォルトの名無しさん [sage] 2019/02/04(月) 01:42:54.31 ID:8qZo3rbs アホ過ぎて話になんねー 線型探索と二分探索のどっちが速いかが言語によるとか頭腐ってんのか 線型探索: ttps://ideone.com/De3SOQ 二分探索: ttps://ideone.com/v9Twjx http://mevius.5ch.net/test/read.cgi/tech/1549160513/21
22: デフォルトの名無しさん [] 2019/02/04(月) 06:56:02.27 ID:eX/1kX5o >>19 寝てる間にフォローありがとう。 >>15 こっちはiPhoneのモバイルC内蔵のPythonだが、trueなった。 Haskellは63ビットだからかもう少し早い段階でなる。 ただ、>>19 の言う通り実用上問題無いのでは。 (階乗と違って入力より巨大な数が帰るわけじゃないし、Cとかだと十分実用かと) 64ビットまでの数では効率的なバージョンと、それ以上の数も対応するバージョンという感じではどうか。 sqrtも、n乗根は似た作りになるし。 # n√x def sqrtn(n,x):
return (x ** (1/n)) http://mevius.5ch.net/test/read.cgi/tech/1549160513/22
23: デフォルトの名無しさん [] 2019/02/04(月) 07:03:50.35 ID:eX/1kX5o どちらかと言うと**演算子(Cで言うpower関数)の実装に興味あるな。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/23
24: デフォルトの名無しさん [sage] 2019/02/04(月) 07:23:18.46 ID:958Z8DnZ CRC 16bit 左送り 初期値 0x0000 生成多項式0x11021 テーブル使用せず演算でなるべくスマートに http://mevius.5ch.net/test/read.cgi/tech/1549160513/24
25: デフォルトの名無しさん [] 2019/02/04(月) 08:07:18.20 ID:jp+X9sqK 指数関数，正弦関数，余弦関数のベキ級数展開（マクローリン展開） http://www.synchronature.com/Science/Resources/e-s-c.jpg http://www.synchronature.com/Science/Euler.html http://mevius.5ch.net/test/read.cgi/tech/1549160513/25
26: デフォルトの名無しさん [sage] 2019/02/04(月) 10:14:05.68 ID:AyF9PYpz 平方数 64ビット以上の巨大数 pythonista iPhone XS Max def chk2(v1,v2): c = 0 for i in range(v1, v2+1): if i == (i**0.5) **2: c += 1 return c v = 100000000000000000000 r = 10000000 v1= v-r v2= v+r start_time=time.clock() c = chk2(v1,v2) end_time=time.clock() print('#結果',end_time-start_time,'秒','count=',c) print('#範囲 ',v1,v2) #結果 5.777779999999893 秒 count= 525 #範囲 99999999999990000000 100000000000010000000 http
://mevius.5ch.net/test/read.cgi/tech/1549160513/26
27: デフォルトの名無しさん [sage] 2019/02/04(月) 10:28:47.91 ID:AyF9PYpz >>26 同じ条件でバイナリサーチをやってみると若干だけ早かったが、誤差の範囲 #結果 5.770102000000406 秒 count= 525 #範囲 99999999999990000000 100000000000010000000 http://mevius.5ch.net/test/read.cgi/tech/1549160513/27
28: デフォルトの名無しさん [sage] 2019/02/04(月) 11:40:45.86 ID:GcH+yasd >>26-27 99,999,999,999,990,000,000~100,000,000,000,010,000,000の範囲には10,000,000,000しかないんだからcount=525ってのは演算誤差が出てるってことだよな？ 99,999,999,980,000,000,001 (9,999,999,999^2) 100,000,000,020,000,000,001 (10,000,000,001^2) http://mevius.5ch.net/test/read.cgi/tech/1549160513/28
29: デフォルトの名無しさん [sage] 2019/02/04(月) 11:43:01.09 ID:GcH+yasd いや、intにしてないからそれを調べてるってわけじゃないのか http://mevius.5ch.net/test/read.cgi/tech/1549160513/29
30: デフォルトの名無しさん [sage] 2019/02/04(月) 14:12:20.36 ID:NdPuZxEw >>28 言われてみればフロートまでカウントするのはおかしいから判定を変えた。 for i in range(v1, v2+1): if (i**0.5).is_integer(): c += 1 return c Core i3 3.2GHz Windows10 python3.7 #結果 8.15625 秒 count= 49151 #範囲 99999999999990000000 100000000000010000000 iPhoneの方が倍くらい早いかな。 #結果 4.180858 秒 count= 49151 Core i7のマシンもあるが大して期待できなさそうだな。 検算の意味で、1から1000までをカウントして31だっ
たから正しいだろう。 なお、Python3の整数int型に最大値はない（上限なし）からどんな数でも扱える。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/30
31: デフォルトの名無しさん [sage] 2019/02/04(月) 14:13:11.15 ID:fIIhQCXR もういいからお前 http://mevius.5ch.net/test/read.cgi/tech/1549160513/31
32: デフォルトの名無しさん [sage] 2019/02/04(月) 14:20:39.50 ID:GcH+yasd >>30 いや、誤差出てるやん http://mevius.5ch.net/test/read.cgi/tech/1549160513/32
33: デフォルトの名無しさん [sage] 2019/02/04(月) 14:55:46.83 ID:GcH+yasd >>30 これ(count=49151)って99999999999999975424から100000000000000024575 (64bit浮動小数点数の16進表記で0x4415AF1D78B58C3Fから0x4415AF1D78B58C41)の平方根が、 10000000000 (64bit浮動小数点数の16進表記で0x4202A05F20000000)になって全部Trueになってるってことだろ http://mevius.5ch.net/test/read.cgi/tech/1549160513/33
34: デフォルトの名無しさん [sage] 2019/02/04(月) 15:39:51.36 ID:8qZo3rbs 99,999,999,980,000,000,001 = 999,999,999^2 100,000,000,000,000,000,000 = 10,000,000,000^2 100,000,000,020,000,000,001 = 10,000,000,001^2 なんだから[99'999'999'999'990'000'000, 100'000'000'000'010'000'000]の区間に入る平方数はただ一つ100,000,000,000,000,000,000しかない 「32bit符号なし整数にしか対応してません」っつうなら分かるがまともに判定出来てないのに「判定出来てる」主張する無能 やれ前提書けだの環境書けだの時間書けだのクソみてぇな御
託並べる前に自分の頭の悪さを自覚しろ http://mevius.5ch.net/test/read.cgi/tech/1549160513/34
35: デフォルトの名無しさん [sage] 2019/02/04(月) 18:19:40.08 ID:TMO26aZK >>34 申し訳ない。 2〜3日前にpython をiPhoneに入れて使い始めてただただ練習のためにお題を使わせてもらってた。 整数と、浮動小数の最大値にまで頭が回らなかった。 今日初めてWindowsにpythonを入れた状態で本当に気が回らなかった。 本当に申し訳ない。 バイナリサーチの方は1個と出るが、時間が膨大にかかる。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/35
36: デフォルトの名無しさん [] 2019/02/04(月) 20:37:21.99 ID:WZY4HG/d 自然数の割り算関数mydivと余り関数mymodを作れ。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/36
37: ◆QZaw55cn4c [sage] 2019/02/04(月) 20:41:26.02 ID:CLpqTC7n >>36 C++ 多桁長演算（加減乗除）の一環として、mpz_class との互換を目指していました https://mevius.5ch.net/test/read.cgi/tech/1434079972/51 http://mevius.5ch.net/test/read.cgi/tech/1549160513/37
38: デフォルトの名無しさん [sage] 2019/02/04(月) 20:50:12.06 ID:Ly7rB5Pz >>36 これでいいの？javascript const myDiv = (a, b) => ~~(a / b) const myMod = (a, b) => a % b http://mevius.5ch.net/test/read.cgi/tech/1549160513/38
39: デフォルトの名無しさん [] 2019/02/04(月) 21:00:40.83 ID:mK0I6q3a modをみる nが平方数なら、n=x^2 だが、n=x^2 (mod m)でもある 逆にmod で平方数でなければ、元々も平方数ではない mod 3だと0 1 は平方数だが、2はちがう。3i + 2 は平方数にはならない http://mevius.5ch.net/test/read.cgi/tech/1549160513/39
40: デフォルトの名無しさん [] 2019/02/04(月) 22:02:57.78 ID:eX/1kX5o >>38 元は小学生にプログラミングを通じて、割り算への理解を深めてもらえないかと考えたんで、単純に演算子を置き換えて欲しくないかも。。。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/40
41: デフォルトの名無しさん [] 2019/02/05(火) 10:18:54.39 ID:ij/1zyvC 小学生の時テストで0点をもらった間違った割り算の やり方をプログラムにしてみた。 --Lua function myDivMod(a, b) local r = 0 while a > 0 do a = a - b r = r + 1 end return r, -a end print(myDivMod(10,3)) 実行結果 4 2 http://mevius.5ch.net/test/read.cgi/tech/1549160513/41
42: デフォルトの名無しさん [sage] 2019/02/05(火) 12:28:40.98 ID:aE6b0ZPr >>35 結局 整数のsqrt を作って、範囲の中に納まる最小最大の整数のsqrt を取り出し、その差（+1）がその範囲の中にある平方数の個数と言う作りにした。 ポイントとなった整数のsqrt が秀逸だったのでここに書いておく。 どんなに巨大な数字でも数回のシフト操作だけで終わるから極端にスピードが速い。 ソースは、gist.github.com/bnlucas/5879594 # integer square root def isqrt_2(n): if n < 0: raise ValueError('Square root is not defined for
negative numbers.') x = int(n) if x == 0: return 0 a, b = divmod(x.bit_length(), 2) #divmod(a, b)は(a // b, a % b)のタプルを返す。 #平方数は半分のビット数以下だからそれを最大値で計算開始 n = 2 ** (a + b) while True: y = (n + x // n) >> 1 #1bit右にシフト if y >= n: return n n = y ----------------- #結果 0.0 秒 count= 1000000000 #範囲 999999999000000000000000000000000000 1000000001000000000000000000000000000 #入力bit_length()=120 入力bit_length()=120 平方数範
囲 999999999500000000 1000000000499999999 上の二乗 999999999000000000250000000000000000 1000000000999999998249999999000000001 http://mevius.5ch.net/test/read.cgi/tech/1549160513/42
43: デフォルトの名無しさん [] 2019/02/05(火) 12:33:09.36 ID:NCwCR2JI >>41 おしいなw http://mevius.5ch.net/test/read.cgi/tech/1549160513/43
44: デフォルトの名無しさん [sage] 2019/02/05(火) 13:45:18.58 ID:jFne2R1T 掛け算は簡単だけど除算は結構面倒 ttps://ideone.com/EheeYM http://mevius.5ch.net/test/read.cgi/tech/1549160513/44
45: デフォルトの名無しさん [sage] 2019/02/05(火) 18:45:08.63 ID:63VtM8MC >>42 の isqrt_2 を使ったパフォーマンステスト。 次のようなのを継ぎ足してテストした。 例によってインデント部は全角空白に変換してるから、逆変換しないと動かない。 def isSqrt(n): return n == isqrt_2(n)**2 v0 = 12345678901234567890 v = v0**2 # 整数平方される対象の数値 loopc = 100000 # をこの回数繰り返す。 isqr=0 start =time.process_time() for i in range(loopc): isqr=isqrt_2(v) end =time.process_time() print('#整数平方(v)の結
果',end-start,'秒') print(' 繰返し数の回数',loopc),print(),print('#v0 ',v0) print('#v=v0**2=',v), print('#isqrt(v)',isqr) print('#上の**2',isqr**2) print('対象数vのビット数',v.bit_length(),'bit') print('vが平方数かどうかの判定',isSqrt(v)) ----- #整数平方(v)の結果 0.22398700000002236 秒 繰返し数の回数 100000 #v0 12345678901234567890 #v=v0**2= 152415787532388367501905199875019052100 #isqrt(v) 12345678901234567890 #上の**2 152415787532388367501905199875019052100 対象数vのビット数 127 bit vが平方数
かどうかの判定 True http://mevius.5ch.net/test/read.cgi/tech/1549160513/45
46: デフォルトの名無しさん [sage] 2019/02/06(水) 11:48:35.22 ID:Cmz9AyOj >>45 同じ条件で2分探索法でやると 5.5秒かかった。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/46
47: デフォルトの名無しさん [sage] 2019/02/06(水) 16:53:02.43 ID:XOfzhWu4 Wikipediaに Integer square root https://en.wikipedia.org/wiki/Integer_square_root があり、その中の 2.1 Using bitwise operations の二つを試してみたが、 最初のrecursive call を使った方が 1.65秒 次の方が 2.05秒 早いことは早いが、>>42 >>45 のビットシフト法の方がかなり早い。 0.22秒 gmpのisqrt は早そうだが Pythonistaでは使えないので試していない。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/47
48: デフォルトの名無しさん [sage] 2019/02/09(土) 01:16:57.63 ID:VrkeVQvn >>4 そう言う記述を度々見るんだが、具体的なプログラムを提示してくれない？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/48
49: デフォルトの名無しさん [sage] 2019/02/09(土) 05:46:19.68 ID:ZuP9aKcb >>48 前スレでもGMPだって紹介されてたし https://gmplib.org/manual/Perfect-Square-Algorithm.html https://gmplib.org/repo/gmp/file/tip/mpn/generic/perfsqr.c 実際に使われる法はビルド時生成(https://gmplib.org/repo/gmp/file/tip/gen-psqr.c)だけど大抵の32/64bitシステムの場合は書いてある通り http://mevius.5ch.net/test/read.cgi/tech/1549160513/49
50: デフォルトの名無しさん [] 2019/02/09(土) 06:52:32.52 ID:y7fm8J5o なんでも放題にすればいい お題 平方数は 256で割るとあまりの パターンが44種類になるという。 この44種類を求める。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/50
51: デフォルトの名無しさん [] 2019/02/09(土) 08:05:29.21 ID:y7fm8J5o 放題は、お題の間違い http://mevius.5ch.net/test/read.cgi/tech/1549160513/51
52: デフォルトの名無しさん [sage] 2019/02/09(土) 08:30:22.91 ID:IKLi4q/e python {(x**2) % 256 for x in range(0,256)} http://mevius.5ch.net/test/read.cgi/tech/1549160513/52
53: デフォルトの名無しさん [sage] 2019/02/09(土) 10:10:19.89 ID:DhY4ZB+P Ruby p 0x100.times.map{|i| i*i&0xFF}.uniq.sort # => [0, 1, 4, [...], 233, 241, 249] http://mevius.5ch.net/test/read.cgi/tech/1549160513/53
54: デフォルトの名無しさん [sage] 2019/02/09(土) 10:33:40.76 ID:O4yJeWlE javascript [...new Set(function*(){for(let i=0;i<256;i++)yield i*i%256}())].sort((a,b)=>a-b) http://mevius.5ch.net/test/read.cgi/tech/1549160513/54
55: デフォルトの名無しさん [] 2019/02/09(土) 14:20:17.67 ID:BaccQTUO お題：ハノイの塔の最少手数は一種類しかないのか http://mevius.5ch.net/test/read.cgi/tech/1549160513/55
56: デフォルトの名無しさん [sage] 2019/02/09(土) 14:22:34.94 ID:VrkeVQvn >>50 その44種(mod256)の中に x%256 が一致するか python mod256=sorted({(i**2)%256 for i in range(256)}) x=123*123 print(x%256 in mod256) # True これでmod の話が理解できた。 要は完全な平方数じゃないのは平方根の計算をしないと言う話ね。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/56
57: デフォルトの名無しさん [sage] 2019/02/09(土) 15:28:05.40 ID:1XyVHoA8 >>50 Perl5 %a = map{$_=>1} map{$_*$_%256} 0..256; @a = keys %a; print "@a\n"; 実行結果 ~ $ perl 13_50.pl | wc -w 44 $ perl 13_50.pl 137 89 161 57 1 4 100 17 36 49 121 64 68 144 201 177 65 185 16 9 193 169 129 105 196 132 25 73 249 209 33 233 225 97 41 81 241 164 145 228 217 0 153 113 http://mevius.5ch.net/test/read.cgi/tech/1549160513/57
58: デフォルトの名無しさん [sage] 2019/02/09(土) 17:42:33.15 ID:1XyVHoA8 >>50 Perl5 その2 use List::MoreUtils 'uniq'; @a = uniq map{$_*$_%256} 0..255; print "@a\n"; http://mevius.5ch.net/test/read.cgi/tech/1549160513/58
59: デフォルトの名無しさん [sage] 2019/02/09(土) 18:17:43.26 ID:HLblHrgV >>49 有難う。 python だが、 # 256, 9, 5, 7, 13, 17 97 のmodであらかじめカットしたら、5倍くらい早くなった。 因みに >>50 のお題で mod256=sorted({(i**2)%256 for i in range(256)}) と modn = lambda n:set((i**2)%n for i in range(n)) mod256 = modn(256) では下のsetを使った方が3割くらいスピードが速かった。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/59
60: デフォルトの名無しさん [sage] 2019/02/09(土) 18:57:59.38 ID:luPnpF49 >>59 # 256, 9, 5, 7, 13, 17 97 なんて順番ははおかしいんじゃねと思って、 大きい順にカットしたら、更に2割以上早くなった。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/60
61: デフォルトの名無しさん [] 2019/02/10(日) 06:54:30.87 ID:qszHu1wC >>50 J 64個の平方数を調べれば44種類のパターンはそろうようだ。 /:~ ~. 256| *: i. 64 http://mevius.5ch.net/test/read.cgi/tech/1549160513/61
62: デフォルトの名無しさん [sage] 2019/02/10(日) 12:16:48.56 ID:8pY6FeJB お題 ある数 n とする。 下位から24bit区切りの数を足し合わせてからmod 2^24-1 した数が、元の数nのmod 2^24-1 と一致することを確認しなさい。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/62
63: デフォルトの名無しさん [sage] 2019/02/10(日) 12:27:09.74 ID:Mq5me4ef >>62 任意の n に対してある自然数 N, 自然数列{a_k} が存在して n = Σ_{k = 0}^{N} a_k * 2^(24 * k) と書けるので mod 2^24 - 1 として n = Σ_{k = 0}^{N} a_k * 1^k = Σ_{k = 0}^{N} a_k ■ http://mevius.5ch.net/test/read.cgi/tech/1549160513/63
64: デフォルトの名無しさん [sage] 2019/02/10(日) 14:27:03.54 ID:H2rtpzeI >>59,60 256はmodじゃなくて&255を取る 確率的には大きい順じゃなくて9,97,17,13,7,5が良いのでは？ 9,97,17,13,7,5でmodを取る場合、大きい数からそのままmodを取るのではなく2^48-1でmodを取った数値に対してmod これで速度どうなる？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/64
65: デフォルトの名無しさん [sage] 2019/02/10(日) 14:33:21.22 ID:JrJlQQ/Q >>63 それなんと言うプログラム？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/65
66: デフォルトの名無しさん [sage] 2019/02/10(日) 14:41:11.23 ID:fWGYOSi7 またこの流れ？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/66
67: デフォルトの名無しさん [sage] 2019/02/10(日) 14:49:22.42 ID:NRo2aHHT mod 255にしたら遅くなるんじゃねーの 0 < n mod 255 < 254 だぞ http://mevius.5ch.net/test/read.cgi/tech/1549160513/67
68: デフォルトの名無しさん [sage] 2019/02/10(日) 14:49:43.12 ID:NRo2aHHT 0 <= n mod 255 <= 254 だった http://mevius.5ch.net/test/read.cgi/tech/1549160513/68
69: デフォルトの名無しさん [sage] 2019/02/10(日) 15:12:41.36 ID:95x0uvij >>62 python # n%(2**24-1) を求める def mod224get(n): bn=(n.bit_length()+7)//8 #byte長 bb=n.to_bytes(bn,'little') s= sum([int.from_bytes(bb[i:i+3],'little') for i in range(0,bn,3) ]) #24bit毎の合計 return s%(2**24-1) v0=12345678901234567890 #v0=0 n=v0**2 loop = 100000 print('テスト範囲は ',n,'〜',n+loop-1,'loop回数=',loop) start =time.process_time() for i in range(n,n+loop): if mod224get(n) != n%(2**24-1) :
print('間違い見っけ',n) end =time.process_time() print('全問正解 かかった時間は、',end-start,'秒') # ―― 結果 テスト範囲は 152415787532388367501905199875019052100 〜 152415787532388367501905199875019152099 loop回数= 100000 全問正解 かかった時間は、 0.2963889999999765 秒 http://mevius.5ch.net/test/read.cgi/tech/1549160513/69
70: デフォルトの名無しさん [sage] 2019/02/10(日) 16:02:45.96 ID:8pY6FeJB >>64 アドバイスありがとう。 それは思ったんだけど、現代の言語がそんなところで手抜きはしていないだろうと信じてテストしていなかった。 今、&255 に変えてテストしてみたけど、スピードの差はなかった。 そう言う発想は昔は非常に重要だったけど、今は言語の中で吸収してるみたいだね。 その下のアドバイスに対しては、何故ご自分では試されないのですか？ あまりやるつもりはないのは、mod 2**24-1 と言うのが理解できていないからです。 これで早くな
るのなら色々試してみたいんですが、このリストを作るだけでもかなりの時間がかかりめげてます。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/70
71: デフォルトの名無しさん [sage] 2019/02/10(日) 16:33:26.08 ID:H2rtpzeI >>70 剰余の順番に関しては確率がこんなんだからやで 3 / 5 = 0.600000 4 / 7 = 0.571429 4 / 9 = 0.444444 7 / 13 = 0.538462 9 / 17 = 0.529412 49 / 97 = 0.505155 テーブルは9, 97, 17, 13, 7, 5の物で良いんやで？ 多倍長整数の剰余より32bit整数/64bit整数の剰余のほうが計算量が少ないから、 (32bitの場合) 2^24-1で剰余を取ったものに対して9, 17, 13, 7, 5の剰余で平方数かどうかを調べる (64bitの場合) 2^48-1で剰余を取ったものに対して9, 97, 17, 13,
7, 5の剰余で平方数かどうかを調べる なしてこんなことができるかってーと、 2^24-1(=16777215)の因数に5, 7, 9, 13, 17が、2^48-1(=281474976710655)の因数に5, 7, 9, 13, 17, 97含まれているからやで http://mevius.5ch.net/test/read.cgi/tech/1549160513/71
72: デフォルトの名無しさん [sage] 2019/02/10(日) 16:55:58.44 ID:8pY6FeJB >>71 あまり深入りするつもりはないけど、mod 2**24-1 でチェックしたら、 mod 9, 97, 17, 13, 7, 5 でチェックする必要はないと言う事？ ま、数学を解いてるつもりは全くなく、プログラムの練習だからいかに沢山の人が素晴らしいプログラムを見せてくれるかにしか興味はない。 プログラムを書かない人は自分にとってはなんの意味もない。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/72
73: デフォルトの名無しさん [sage] 2019/02/10(日) 17:11:01.79 ID:H2rtpzeI >>72 ちゃうねん mod 2**24-1をした数値に対してmod 9, 17, 13, 7, 5 でチェックするねん もしくはmod 2**48-1をした数値に対してmod 9, 97, 17, 13, 7, 5 でチェックするねん http://mevius.5ch.net/test/read.cgi/tech/1549160513/73
74: デフォルトの名無しさん [sage] 2019/02/10(日) 19:32:43.48 ID:/XsfFvRM >> 73 2重に剰余を取るのはGMPみたく多倍長なら意味があるけど, 32/64bit固定長ならあまり意味はない 複数回剰余を確認する必要があるから多倍長から固定長(32/64bit)にしていて, 更に因数を使えば剰余を求めるための除算の代わりに乗算が使えるから因数の多い2^24 - 1や2^48 - 1を採用してる http://mevius.5ch.net/test/read.cgi/tech/1549160513/74
75: デフォルトの名無しさん [sage] 2019/02/11(月) 00:35:41.13 ID:8Hdd2FlG >>62 ガウス少年が見出したように Σ1,2,…,n-2,n-1＝n *(n +1) /2 なので、 n の mod 2^24-1 と Σ1,2,…,n-2,n-1 ＝n *(n +1) /2 の mod 2^24-1 が等しいのは自明だと思うけど、 そういう、ちょっとした数学を使わず Σ1,2,…,n-2,n-1 をloopで和を算出し mod 2^24-1 して比較する n の mod 2^24-1 と比較する プログラムを作れという題なんだろうか… http://mevius.5ch.net/test/read.cgi/tech/1549160513/75
76: デフォルトの名無しさん [sage] 2019/02/11(月) 00:37:45.16 ID:8Hdd2FlG >>75 「比較する」を二度書いちゃった、訂正 Σ1,2,…,n-2,n-1 の和をloopで算出し mod 2^24-1 して n の mod 2^24-1 と比較する http://mevius.5ch.net/test/read.cgi/tech/1549160513/76
77: デフォルトの名無しさん [sage] 2019/02/11(月) 00:57:54.78 ID:HnU/OI7o >>75 お題をよく読んだら？ 24bit = 3バイト毎に取り出してその合計に対して 2**24-1 をしなさいと言う問題だよ。 数学なんて関係ない。 ただ出されたお題をプログラムで解いてくれ。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/77
78: デフォルトの名無しさん [sage] 2019/02/11(月) 01:10:25.11 ID:8Hdd2FlG >>75 ごめん Σ1,2,…,n-2,n-1＝n *(n +1) /2 は間違えた。こうだ Σ1,2,…,n-2,n-1＝n *(n -1) /2 http://mevius.5ch.net/test/read.cgi/tech/1549160513/78
79: デフォルトの名無しさん [sage] 2019/02/11(月) 01:12:22.73 ID:8Hdd2FlG >>77 ｺﾞﾒﾝなんか誤解したかも、よく読む http://mevius.5ch.net/test/read.cgi/tech/1549160513/79
80: デフォルトの名無しさん [sage] 2019/02/11(月) 01:15:22.84 ID:f+GXhEiR ある数nのビット表記方法によって一致する／しないを答えればいいのかな http://mevius.5ch.net/test/read.cgi/tech/1549160513/80
81: デフォルトの名無しさん [sage] 2019/02/11(月) 01:42:54.29 ID:8Hdd2FlG >>62 Perl5 use bignum (l=>GMP); use feature say; sub sum24 { my $v = $_[0]; if ($v > 0) { my $d = int($v / 2**24); my $m = $v % 2**24; # $v - $d * $f6; $m + sum24($d); } else { 0; } } $n = 12345678901234567890; say $n % (2**24 -1); say sum24($n) % (2**24 -1); 実行結果 ~ $ perl 13_62.pl 13189905 13189905 http://mevius.5ch.net/test/read.cgi/tech/1549160513/81
82: デフォルトの名無しさん [sage] 2019/02/11(月) 01:47:30.91 ID:8Hdd2FlG >>81 8行目後半の#から右 # $v - $d * $f6; は削除し忘れたcommentです ｽﾏｿ http://mevius.5ch.net/test/read.cgi/tech/1549160513/82
83: デフォルトの名無しさん [sage] 2019/02/11(月) 01:53:44.12 ID:C0KPLnD/ どうみても自明なんだから確認も糞もないけどな http://mevius.5ch.net/test/read.cgi/tech/1549160513/83
84: デフォルトの名無しさん [sage] 2019/02/11(月) 01:57:28.89 ID:8Hdd2FlG お題を作ることの難しさだよな… http://mevius.5ch.net/test/read.cgi/tech/1549160513/84
85: デフォルトの名無しさん [sage] 2019/02/11(月) 02:15:34.48 ID:HnU/OI7o >>83 自明もへったくれもない。 プログラムが正しいかどうかの確認だよ。 プログラムも書かないで能書きだけ垂れてもなんの足しにもならない。 ここはプログラムのお題スレだよ。 >>62 のお題は前スレのGMP の整数平方根の説明の文章の中から取り出したもの。 つまり、ここまでできると、次は n**2%(2**24-1) のリストを作れと言うお題になるんだろうけど、時間がかかりすぎるからお題にするのはやめた。 このリストができないと実際の平方数の高速チェック
が出来ないじゃん。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/85
86: デフォルトの名無しさん [sage] 2019/02/11(月) 02:26:56.38 ID:8Hdd2FlG そんな怒るなよ。 暖かくしてぐっすりお休みよ http://mevius.5ch.net/test/read.cgi/tech/1549160513/86
87: デフォルトの名無しさん [sage] 2019/02/11(月) 02:31:44.77 ID:HnU/OI7o しかしここまで複雑な処理をして本当に早くなるのかどうか疑問だけどな。 mod 2**24-1 って結構時間がかかりそうな気がする。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/87
88: デフォルトの名無しさん [sage] 2019/02/11(月) 02:35:42.19 ID:ucqIUq+7 >>85 一番能書き垂れてんのお前だろ クソみたいな御託並べる前に自分のことを考えろっつったろうが GMPが一体どこで > n**2%(2**24-1) のリスト なんか使ってんだ？91で割った場合のテーブルでさえ12byte必要だってのにどうやってそんな巨大なテーブル用意するんだ？ GMPの中身なんか数学の成果の塊だぞ？お前が数学したくないだか出来ないだか知らんがアルゴリズム考えるようなスレでクソみたいなこと喋ってんじゃねぇよ お前はコードを書いても価値がない h
ttp://mevius.5ch.net/test/read.cgi/tech/1549160513/88
89: デフォルトの名無しさん [sage] 2019/02/11(月) 02:35:55.83 ID:8Hdd2FlG 単なるbitmaskで済まない様な場合 あるいは除算して剰余を求めるなら さんざ研究されていると思うから自力で１から考える前に 先人の業績を知れってことだろ ｱﾊﾞﾖ ﾉｼ http://mevius.5ch.net/test/read.cgi/tech/1549160513/89
90: デフォルトの名無しさん [sage] 2019/02/11(月) 02:36:00.30 ID:IhaR3BEX お題：ポーカーダイス 通常のサイコロを5個振って出た目をポーカーの役になぞってそれぞれの出現確率を求める。 役は、5カード、4カード、ストレート、フルハウス、3カード、2ペア、1ペア、ブタ（ノーペア） 例えば出た目が 1,1,3,1,4 ならスリーカード。2,5,4,6,3 ならストレート。 5カードは6/(6^5)、4カードは(5*5*6)/(6^5)というように数学的に 求めても難しくはないのですが、ここはプログラミングのスレなので 全通り力技でチェックして求めてみてください。 解答
例：C言語 https://ideone.com/4X62Am http://mevius.5ch.net/test/read.cgi/tech/1549160513/90
91: デフォルトの名無しさん [sage] 2019/02/11(月) 03:04:24.50 ID:8Hdd2FlG 6^5総当りせよってか… native compiler系言語で力技か http://mevius.5ch.net/test/read.cgi/tech/1549160513/91
92: デフォルトの名無しさん [sage] 2019/02/11(月) 03:20:03.89 ID:K/18SmCD Jニキはよ http://mevius.5ch.net/test/read.cgi/tech/1549160513/92
93: デフォルトの名無しさん [sage] 2019/02/11(月) 03:29:32.98 ID:ucqIUq+7 大した数じゃないからズルいことが出来る https://ideone.com/yEcdPV http://mevius.5ch.net/test/read.cgi/tech/1549160513/93
94: デフォルトの名無しさん [sage] 2019/02/11(月) 04:00:05.29 ID:8Hdd2FlG お なかなか http://mevius.5ch.net/test/read.cgi/tech/1549160513/94
95: デフォルトの名無しさん [sage] 2019/02/11(月) 08:16:46.17 ID:b3B7Bg4u python3 https://ideone.com/k6Ea4j 最後の出力部分はpython 3.6以降だと for k,v in hand.items(): print("{} :\n {} / 7776 ({} %)".format(k,v, round(100*v/7776,2))) でいけるけど実行環境が3.5なのでやむなく http://mevius.5ch.net/test/read.cgi/tech/1549160513/95
96: デフォルトの名無しさん [sage] 2019/02/11(月) 16:44:30.42 ID:xTuBWJbc なんか数学でもできる力技お題増えてきたな もっとプログラミングじゃないとできないような良いお題無いんだろうか http://mevius.5ch.net/test/read.cgi/tech/1549160513/96
97: デフォルトの名無しさん [sage] 2019/02/11(月) 17:22:02.16 ID:7gZS39yo >>96 そんなの存在しないんじゃない？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/97
98: デフォルトの名無しさん [sage] 2019/02/11(月) 17:28:00.80 ID:6aFdKLEP 確率の問題でも特定の疑似乱数と種を使った偏りを求めるとかは数学では難しい http://mevius.5ch.net/test/read.cgi/tech/1549160513/98
99: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 17:37:44.75 ID:adj8EvAq お題: 日本語文字とカッコ { } とスラッシュ(/)で構成された入力文字列Sが与えられる。{ }で囲まれ、かつ スラッシュで区切られた部分文字列について、それぞれ場合分けを行って、複数の文字列のリストに展開して改行区切りで出力せよ。 カッコの対応が間違っている場合はERRORを出力せよ。 (例1) {ひまわり/あさがお}は{植物/花}です。 (出力結果) ひまわりは植物です。 あさがおは植物です。 ひまわりは花です。 あさがおは花です。 http://mevius.5ch.net/
test/read.cgi/tech/1549160513/99
100: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 17:59:47.38 ID:BEdrdhIs なお、展開の順序については問わない。カッコがなくなるまで繰り返し展開せよ。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/100
101: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 18:20:25.29 ID:BEdrdhIs (1) {あ{いう/え}/お{か/き}/く}け{こ} (2) さ{し/す}せそ{{た/ち}つ/て}と http://mevius.5ch.net/test/read.cgi/tech/1549160513/101
102: デフォルトの名無しさん [sage] 2019/02/11(月) 19:00:31.50 ID:MkFOBvt9 ネストありかよ、ちょっと面倒だな http://mevius.5ch.net/test/read.cgi/tech/1549160513/102
103: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 19:03:55.20 ID:BEdrdhIs ヒント: まず、適当な場所でブツ切りにしてノードに分ける。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/103
104: デフォルトの名無しさん [sage] 2019/02/11(月) 19:20:26.84 ID:Q78+FEDq >>101 で、どう言う結果を正解とするの？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/104
105: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 19:32:34.31 ID:BEdrdhIs (1)の答え(※ソート済み) あいうけこ あいうけこ あえけこ あえけこ おかけこ おかけこ おきけこ おきけこ くけこ くけこ くけこ くけこ http://mevius.5ch.net/test/read.cgi/tech/1549160513/105
106: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 19:33:13.25 ID:BEdrdhIs (2)の答え(※ソート済み) さしせそたつと さしせそちつと さしせそてと さしせそてと さすせそたつと さすせそちつと さすせそてと さすせそてと http://mevius.5ch.net/test/read.cgi/tech/1549160513/106
107: デフォルトの名無しさん [sage] 2019/02/11(月) 19:36:37.18 ID:MkFOBvt9 これでいいのか？ > (1) {あ{いう/え}/お{か/き}/く}け{こ} あ いう け こ あ え け こ お か け こ お き け こ く け こ > (2) さ{し/す}せそ{{た/ち}つ/て}と さ し せそ た つ と さ す せそ た つ と さ し せそ ち つ と さ す せそ ち つ と さ し せそ て と さ す せそ て と http://mevius.5ch.net/test/read.cgi/tech/1549160513/107
108: デフォルトの名無しさん [sage] 2019/02/11(月) 19:37:56.93 ID:MkFOBvt9 あれ？ 変化しないケースも出力するの？ http://mevius.5ch.net/test/read.cgi/tech/1549160513/108
109: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 19:40:50.96 ID:BEdrdhIs >>107 間違い。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/109
110: さまよえる蟻人間 ◆T6xkBnTXz7B0 [sage] 2019/02/11(月) 19:46:19.44 ID:adj8EvAq ごめんなさい。間違えました。重複は単一化して下さい。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/110
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 892 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.019s