16

シンプルな機能が欲しい

is_square :: Int -> Bool

これは、Int N が完全な正方形かどうかを判断します (x*x = N となる整数 x はありますか)。

もちろん、私はちょうどのようなものを書くことができます

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

しかし、それはひどいようです！そのような述語を実装する一般的な簡単な方法があるでしょうか?

4

9 に答える 9

10

パッケージに含まれる Haskell のほとんどの数論関連の問題に対する素晴らしいライブラリがあります。arithmoi

ライブラリを使用しMath.NumberTheory.Powers.Squaresます。

具体的にはisSquare'機能。

is_square :: Int -> Bool
is_square = isSquare' . fromIntegral

ライブラリは最適化されており、あなたや私よりもはるかに効率に専念している人々によって十分に吟味されています。現在、この種の悪ふざけは内部で行われていませんが、ライブラリが進化し、より最適化されるにつれて、将来的にはそうなる可能性があります。ソースコードを表示して、その仕組みを理解してください!

車輪を再発明するのではなく、利用可能な場合は常にライブラリを使用してください。

于 2014-07-10T13:55:48.487 に答える
10

このように考えてください。正の int がある場合、n基本的に 1 .. n からの数値の範囲でバイナリ検索を実行して、最初の数値を見つけn'ますn' * n' = n。

Haskell はわかりませんが、この F# は簡単に変換できるはずです。

let is_perfect_square n =
    let rec binary_search low high =
        let mid = (high + low) / 2
        let midSquare = mid * mid

        if low > high then false
        elif n = midSquare then true
        else if n < midSquare then binary_search low (mid - 1)
        else binary_search (mid + 1) high

    binary_search 1 n

O(log n) であることが保証されます。完璧な立方体とより高いパワーを簡単に変更できます。

于 2010-05-11T19:46:26.123 に答える
6

あなたが提供したコードは、あなたが得ようとしている最速のものだと思います：

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

このコードの複雑さは、1 つの sqrt、1 つの double 乗算、1 つのキャスト (dbl->int)、および 1 つの比較です。他の計算方法を使用して、sqrt と乗算を整数演算とシフトだけに置き換えることもできますが、1 つの sqrt と 1 つの乗算よりも高速ではない可能性があります。

別の方法を使用する価値がある唯一の場所は、実行している CPU が浮動小数点演算をサポートしていない場合です。この場合、コンパイラはおそらくソフトウェアで sqrt と double の乗算を生成する必要があり、特定のアプリケーション向けに最適化する際に利点を得ることができます。

他の回答で指摘されているように、大きな整数にはまだ制限がありますが、これらの数値に遭遇しない限り、独自のアルゴリズムを作成するよりも浮動小数点ハードウェア サポートを利用する方がよいでしょう。

于 2010-05-11T03:15:58.653 に答える
2

この質問に対する別の回答に関するコメントで、メモ化について説明しました。この手法は、プローブ パターンの密度が高い場合に役立つことに注意してください。この場合、それは同じ整数を何度もテストすることを意味します。あなたのコードが同じ作業を繰り返し、回答をキャッシュすることで利益を得る可能性はどのくらいありますか?

入力の分布についてのアイデアが得られなかったので、優れた基準パッケージを使用する簡単なベンチマークを検討してください。

module Main
where

import Criterion.Main
import Random

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

is_square_mem =
  let check n = sq * sq == n
        where sq = floor $ sqrt $ (fromIntegral n :: Double)
  in (map check [0..] !!)

main = do
  g <- newStdGen
  let rs = take 10000 $ randomRs (0,1000::Int) g
      direct = map is_square
      memo   = map is_square_mem
  defaultMain [ bench "direct" $ whnf direct rs
              , bench "memo"   $ whnf memo   rs
              ]

このワークロードは、実行していることを正しく表している場合とそうでない場合がありますが、記載されているように、キャッシュ ミス率が高すぎるように見えます。

タイミング確率密度

于 2010-05-11T19:17:33.677 に答える
1

ああ、今日は数値が完全な立方体かどうかを判断する必要がありましたが、同様の解決策は非常に遅かったです。

それで、私はかなり賢い代替案を思いつきました

cubes = map (\x -> x*x*x) [1..]
is_cube n = n == (head $ dropWhile (<n) cubes)

とてもシンプルです。ルックアップを高速化するにはツリーを使用する必要があると思いますが、このソリューションを試してみます。おそらく、私のタスクには十分高速です。そうでない場合は、適切なデータ構造で回答を編集します

于 2010-05-11T18:09:17.207 に答える
1

場合によっては、問題を小さすぎる部分 (チェックなどis_square)に分割してはならないことがあります。

intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted xs (y:ys) | head xs > y = intersectSorted xs ys
intersectSorted (x:xs) ys | head ys > x = intersectSorted xs ys
intersectSorted (x:xs) (y:ys) | x == y = x : intersectSorted xs ys

squares = [x*x | x <- [ 1..]]
weird = [2*x+1 | x <- [ 1..]]

perfectSquareWeird = intersectSorted squares weird
于 2010-05-11T18:20:18.403 に答える
1

完全な平方をテストする非常に簡単な方法があります。文字通り、数値の平方根の小数部にゼロ以外の値があるかどうかを確認します。
私は、浮動小数点を返す平方根関数を想定しています。その場合、次のことができます (疑似コード): 

func IsSquare(N)  
   sq = sqrt(N)
   return (sq modulus 1.0) equals 0.0
于 2010-05-11T18:59:31.380 に答える
1

ウィキペディアの整数平方根に関する記事には、ニーズに合わせてアルゴリズムを調整できることが記載されています。ニュートンの方法は、2 次的に収束するため、優れています。つまり、各ステップで 2 倍の数の正しい数字が得られます。

Double入力が よりも大きい可能性がある場合は、近づかないことをお勧めします2^53。その後、すべての整数を として正確に表現できるわけではありませんDouble。

于 2010-05-11T02:39:40.783 に答える
0

特にきれいでも高速でもありませんが、任意の大きな整数に対して（ゆっくりと）機能するニュートンの方法に基づいたキャストフリー、FPAフリーのバージョンを次に示します。

import Control.Applicative ((<*>))
import Control.Monad (join)
import Data.Ratio ((%))

isSquare = (==) =<< (^2) . floor . (join g <*> join f) . (%1)
  where
    f n x = (x + n / x) / 2
    g n x y | abs (x - y) > 1 = g n y $ f n y
            | otherwise       = y

おそらく、数論のトリックを追加することでスピードアップできるでしょう。

于 2010-05-11T14:46:51.320 に答える