Что такое способ определить, является ли INT идеальный квадрат в Haskell?

StackOverflow https://stackoverflow.com/questions/2807686

  •  25-09-2019
  •  | 
  •  

Вопрос

Мне нужна простая функция

is_square :: Int -> Bool

который определяет, если int n идеальный квадрат (есть ли целое число X такое, что x * x = n).

Конечно, я могу просто написать что-то вроде

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

Но это выглядит ужасно! Возможно, есть общий простой способ реализации такого предиката?

Это было полезно?

Решение 5

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

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

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

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

Другие советы

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

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

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

Конкретно то isSquare' функция.

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

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

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

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

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

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

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

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

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

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

Иногда вы не должны разделить проблемы в слишком маленькие детали (например, проверки 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

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

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

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

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

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
              ]

Эта рабочая нагрузка может быть или не может быть справедливым представителем того, что вы делаете, но, как написано, скорость мисс кэша появляется слишком высокой:

timing probability-density

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top