[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
780(1): デフォルトの名無しさん [] 2023/06/15(木) 00:31:42.16 ID:K1O29FUe(1/3) AAS
>>774フーリエ変換でなぜ計算できるのか知らないが、とりあえずRに移植してみたら
5秒で完了できなかった。www.ideone.com/nhGFqi
tio.runで実行したら5.975秒かかった。fft関数がRのよりnumpyのの方が速いのか?
RのはUses C translation of Fortran code in Singleton (1979)だそうだが。
784: デフォルトの名無しさん [] 2023/06/15(木) 21:44:36.42 ID:K1O29FUe(2/3) AAS
>>781781(1): デフォルトの名無しさん [] 2023/06/15(木) 01:02:15.13 ID:h+F4OSrU(1/2) AAS
>>780
数え上げの問題を形式的冪級数の議論に対応づけることができる
形式的冪級数同士の積は長さ n が2の冪なら高速フーリエ変換による畳み込みで O(n log n) で計算できる
Rのfftはおそらく高速になる2の冪の長さのfftをしていないんだと思う
Rの標準のfft関数は遅いようなので、fftwパッケージのFFT, IFFT関数に替えたら
実行時間は半分くらいに短縮されたが、ideoneではfftwパッケージがインスール
されていなくて実行できなくて残念。
library(fftw)
conv <- function(f, g) round(Re(IFFT(FFT(f) * FFT(g))))
n <- 1234567L
isprime <- c(FALSE, rep(TRUE, n - 1))
for (i in 2:sqrt(n)) if (isprime[i]) isprime[seq(i + i, n, i)] <- FALSE
N <- nextn(2 * n + 1, 2)
x <- c(0, as.double(isprime), rep(0, N - n - 1))
count <- conv(conv(x, x), x)[n + 1]
i <- 2:(n %/% 2 - 1)
k <- sum(isprime[i] & isprime[n - 2 * i])
cat((count - 3 * k) %/% 6 + k, "通り\n", sep = "")
786: デフォルトの名無しさん [] 2023/06/15(木) 22:26:38.53 ID:K1O29FUe(3/3) AAS
>>785785(2): デフォルトの名無しさん [sage] 2023/06/15(木) 22:01:30.16 ID:4JYva2qR(1/2) AAS
fftなんぞ使って早くなんかならんというに
原理わかってんの？
例えばHaskellの標準のinteger型は何万桁でも計算できる、その際fftで掛け算するので数万桁まで行ってもそこそこ早い
しかし逆に32bitで収まるような計算だと遅くなる
だから“この計算はfftなんか使わなくていいよ、int32の範囲で収まるからそれで計算してね”と専用の型がいっぱいある
Rがそれで早くなるなら素の標準計算がしょぼいとかインタプリタ特有の話
そもそも計算速度気にする場合にRを選択してる時点で筋違い
遅い言語でも工夫次第で制限時間を突破できないかというのがスレの流れなので、
そういう当たり前な突っ込みは野暮というもの。速い言語での正攻法の回答例は
>>746にちゃんと書いた。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.043s