Как определить, является ли 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

Подумайте об этом так: если у вас положительное значение 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). Легко изменить совершенные кубы и более высокие способности.

Answer 2

В Haskell есть библиотека замечательная для большинства проблем, связанных с теорией чисел, включенная в пакет arithmoi.

Используйте библиотеку Math.NumberTheory.Powers.Squares.

В частности, функция isSquare'.

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

Библиотека оптимизирована и хорошо проверена людьми, гораздо более преданными эффективности, чем вы или я. Хотя в настоящее время в ней нет такого рода махинаций , которые могут происходить под капотом, в будущем это возможно поскольку библиотека развивается и становится более оптимизированной. Просмотрите исходный код , чтобы понять, как он работает!

Не изобретайте велосипед, всегда используйте библиотеку, когда она доступна.

Answer 3

Я думаю, что код, который вы предоставили, является самым быстрым, что вы собираетесь получить:

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

Сложность этого кода: один sqrt, одно двойное умножение, одно приведение (dbl-> int) и одно сравнение. Вы могли бы попытаться использовать другие методы вычисления, чтобы заменить sqrt и умножение только целочисленной арифметикой и сдвигами, но есть вероятность, что это не будет быстрее, чем один sqrt и одно умножение.

Единственное место, где стоит использовать другой метод, - это если процессор, на котором вы работаете, не поддерживает арифметику с плавающей запятой. В этом случае компилятору, вероятно, придется генерировать sqrt и двойное умножение в программном обеспечении, и вы можете получить преимущество в оптимизации для вашего конкретного приложения.

Как указывает другой ответ, по-прежнему существует ограничение больших целых чисел, но если вы не собираетесь сталкиваться с этими числами, вероятно, лучше воспользоваться преимуществами аппаратной поддержки с плавающей запятой, чем писать собственный алгоритм.

Answer 4

В комментарии к другому ответу на этот вопрос вы обсуждали памятку . Имейте в виду, что этот метод помогает, когда ваши образцы зондов демонстрируют хорошую плотность. В этом случае это будет означать тестирование одних и тех же целых чисел снова и снова. Насколько вероятно, что ваш код будет повторять ту же самую работу и, таким образом, получать выгоду от кэширования ответов?

Вы не дали нам представление о распределении ваших входных данных, поэтому рассмотрим быстрый тест, который использует превосходный пакет критерий :

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 5

Существует очень простой способ проверить идеальный квадрат - буквально, вы проверяете, есть ли в корне квадратного числа что-либо кроме нуля в дробной части. Я предполагаю функцию квадратного корня, которая возвращает плавающую точку, и в этом случае вы можете сделать (Psuedocode):

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

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

О, сегодня мне нужно было определить, является ли число идеальным кубом, и подобное решение было ОЧЕНЬ медленным.

Итак, я придумал довольно умную альтернативу

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

Очень просто. Я думаю, мне нужно использовать дерево для более быстрого поиска, но сейчас я попробую это решение, возможно, оно будет достаточно быстрым для моей задачи. Если нет, я отредактирую ответ с правильной структурой данных

Answer 8

Статья Wikipedia о целочисленных квадратных корнях имеет алгоритмы, которые можно адаптировать к вашим потребностям.Метод Ньютона хорош, потому что он сходится квадратично, т. Е. Вы получаете вдвое больше правильных цифр за каждый шаг.

Я бы посоветовал вам держаться подальше от Double, если входное значение может быть больше, чем 2^53, после того, каккоторые не все целые числа могут быть точно представлены как Double.

Answer 9

Это не особенно красиво и быстро, но вот версия без FPA, без 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

Вероятно, это может быть ускорено дополнительным обманом теории чисел.