[過去ﾛｸﾞ] プログラミングのお題スレ Part17 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

882(1): 2020/06/14(日)17:10 ID:ajoLWV+R(2/3) AAS
>>878 Perl
# 簡略化
use bigint;

$am = $b0 = 1;
$a0 = $bm = 0;

for($m = $N = $ARGV[0]; $m ;$m /= 2) {
$a0b0 = $a0 * $b0;
$b0b0 = $b0 * $b0;
($a0, $am) = ($a0b0 + $am * $b0 + $a0 * $bm, $a0b0 + $am * $bm) if $m % 2;
($b0, $bm) = ($b0b0 + 2 * $b0 * $bm, $b0b0 + $bm * $bm)
省2

---

885: 2020/06/14(日)17:45 ID:ajoLWV+R(3/3) AAS
なおNが大きくなると扱う数の桁数がNに比例して増える
よって>>882の乗算の回数はO(logN)であるが、
計算量はO(logN)に抑えることはできない
おそらくO(N^2)とか、乗算を効率化してもO(N*(logN)^2)あたりではないか

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 1.173s*