ما هي الطريقة لتحديد ما إذا كان INT مربعًا مثاليًا في Haskell؟

Question

أحتاج إلى وظيفة بسيطة

is_square :: Int -> Bool

الذي يحدد ما إذا كان int n مربعًا مثاليًا (هل هناك عدد صحيح x بحيث x*x = n).

بالطبع يمكنني كتابة شيء مثل

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

لكنها تبدو فظيعة! ربما هناك طريقة بسيطة شائعة لتنفيذ مثل هذا المسند؟

Answer 1

أوه ، اليوم كنت بحاجة إلى تحديد ما إذا كان الرقم هو مكعب مثالي ، وكان الحل المماثل بطيئًا للغاية.

لذا ، توصلت إلى بديل ذكي جدًا

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

بسيط جدا. أعتقد ، أنني بحاجة إلى استخدام شجرة لإجراء بحث أسرع ، لكن الآن سأحاول هذا الحل ، ربما سيكون سريعًا بما يكفي لمهمتي. إذا لم يكن الأمر كذلك ، فسوف أقوم بتحرير الإجابة باستخدام بنية البيانات المناسبة

Answer 2

فكر في الأمر بهذه الطريقة ، إذا كان لديك 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 (سجل n). من السهل تعديل مكعبات مثالية وقوى أعلى.

Answer 3

هناك رائع مكتبة لمعظم المشكلات المتعلقة نظرية الأرقام في هاسكل المدرجة في arithmoi صفقة.

استخدم ال Math.NumberTheory.Powers.Squares مكتبة.

على وجه التحديد isSquare' وظيفة.

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

تم تحسين المكتبة وفحصها بشكل جيد من قبل أشخاص أكثر تكريسًا للكفاءة ، ثم أنت أو I. بينما لا تملك حاليًا هذا النوع من shenanigans عند الذهاب تحت الغطاء ، يمكن أن يكون في المستقبل مع تطور المكتبة ويحصل أكثر تحسينًا. عرض رمز المصدر لفهم كيف يعمل!

لا تعيد اختراع العجلة ، واستخدم مكتبة دائمًا عند توفرها.

Answer 4

أعتقد أن الرمز الذي قدمته هو الأسرع التي ستحصل عليها:

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

تعقيد هذا الرمز هو: واحد SQRT ، وضرب واحد مزدوج ، واحد يلقي (DBL-> int) ، ومقارنة واحدة. يمكنك محاولة استخدام أساليب حساب أخرى لاستبدال SQRT والضرب مع الحساب الصحيح فقط والتحولات ، ولكن من المحتمل أن تكون أسرع من SQRT واحد وضرب واحد.

المكان الوحيد الذي قد يكون من المفيد استخدام طريقة أخرى هو إذا كان وحدة المعالجة المركزية التي تقوم بتشغيلها لا تدعم الحساب العائم. في هذه الحالة ، من المحتمل أن يتعين على المترجم إنشاء SQRT والتكاثر المزدوج في البرنامج ، ويمكنك الحصول على ميزة في التحسين لتطبيقك المحدد.

كما أشار إلى إجابة أخرى ، لا يزال هناك قيود على الأعداد الصحيحة الكبيرة ، ولكن ما لم تكن ستواجه هذه الأرقام ، فمن الأفضل الاستفادة من دعم أجهزة النقطة العائمة بدلاً من كتابة الخوارزمية الخاصة بك.

Answer 5

ويكيبيديا مقال عن الجذور المربعة الصحيح يمكن تكييف الخوارزميات لتناسب احتياجاتك. طريقة نيوتن لطيفة لأنها تتقارب من الناحية التربيعية ، أي ستحصل على ضعف عدد الأرقام الصحيحة في كل خطوة.

أنصحك بالابتعاد عن Double إذا كان المدخلات قد يكون أكبر من 2^53, ، وبعد ذلك لا يمكن تمثيل جميع الأعداد الصحيحة تمامًا Double.

Answer 6

في بعض الأحيان يجب ألا تقسم المشكلات إلى أجزاء صغيرة جدًا (مثل الشيكات 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

Answer 7

هناك طريقة بسيطة للغاية لاختبار مربع مثالي - حرفيًا تمامًا ، يمكنك التحقق مما إذا كان الجذر التربيعي للرقم يحتوي على أي شيء آخر غير الصفر في الجزء الكسري منه.
أفترض أن وظيفة الجذر التربيعي تقوم بإرجاع نقطة عائمة ، وفي هذه الحالة يمكنك القيام (psuedocode):

func IsSquare(N)  
   sq = sqrt(N)
   return (sq modulus 1.0) equals 0.0

Answer 8

في تعليق على إجابة أخرى على هذا السؤال ، ناقشت المذكرات. ضع في اعتبارك أن هذه التقنية تساعد عندما تظهر أنماط التحقيق الكثافة الجيدة. في هذه الحالة ، من شأن ذلك أن يعني اختبار نفس الأعداد الصحيحة مرارًا وتكرارًا. ما مدى احتمال تكرار الكود الخاص بك وبالتالي الاستفادة من الإجابات التخزين المؤقت؟

لم تعطينا فكرة عن توزيع مدخلاتك ، لذا فكر في معيار سريع يستخدم الممتاز معيار صفقة:

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
              ]

قد يكون أو لا يكون عبء العمل هذا ممثلًا عادلًا لما تفعله ، ولكن كما هو مكتوب ، يبدو معدل تفويت ذاكرة التخزين المؤقت مرتفعًا جدًا:

Answer 9

إنها ليست جميلة أو سريعة بشكل خاص ، ولكن إليك نسخة خالية من 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

من المحتمل أن يتم تسريعها مع بعض خداع نظرية الأرقام الإضافية.