平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.1) - エンジニアをリングする
先日、minghaiさんによる非公式PDF版SICPの全訳を公開しましたというブログを見かけました。 SICPは以前に話を聞いて、難しそうだけどプログラミングの基礎体力的なものがつきそうでいいなあと思っていたところ、ちょうど日本語訳PDFが公開されたということでありがたくやってみることに。 全訳して公開って、素晴らしいですよね。minghaiさんありがとうございます。 私はプログラミングが好きなのですが数学や情報系を専攻していた経験がないので（関数型言語の経験もなし）、はたしてSICP理解できるのか？って感じですが・・ 読んでみて思ったことやメモ書きを残しておきたいと思います。 印象深いところをピックアップしてあとから読み返せるように、引用を多めにさせてもらってます。 ちなみに非公式PDF版SICPのminghaiさんによる全訳のライセンスはCC BY-NC-SAです。 Scheme実行環
素数判定 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "素数判定" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2018年1月） 素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在する
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
