使用 Haskell 求平方和 [英] Sum of Squares using Haskell

问题描述

我正在尝试执行以下计算:x:y 范围内整数的平方和，其中 (x <= y).

I'm trying to carry out the following computation: sum of the squares of integers in the range x:y where (x <= y).

我不确定如何设置约束以确保 x 小于或等于 y.

I'm not sure how to put a constraint to ensure x is less than or equal to y.

我需要能够将 x 的平方与 x+1:y 范围内的平方和相加.

I need to be able to add the square of x to the sum of squares in the range x+1:y.

我看过一些例子，但找不到任何严格地说第一个数字必须小于或等于第二个数字的例子，即 [1..5]

I've had a look at a few examples but cannot find any which strictly say the first number must be less than or equal to the second number i.e. [1..5]

更新:澄清一下，我不想在函数中硬编码 [1..5]，但我希望列表是用户的输入.

UPDATE: Just to clarify, I do not want to hard code [1..5] in the function but I want the list to be an input from the user.

有什么帮助吗?

谢谢

推荐答案

缓慢的方法

明显而缓慢的方法是实际对这些平方求和:

Slow approach

The obvious and slow approach is to actually sum those squares:

sumOfSquaresSlow :: Integral a => a -> a -> a
sumOfSquaresSlow lo hi
    | lo > hi   = error "sumOfSquaresSlow: lo > hi"
    | otherwise = sum $ map (^2) [lo..hi]

这种方法的时间复杂度在 max(y-x,0) 中是线性的；如果您的整数范围很大，则需要一段时间；请参阅我的答案底部的基准.

The time complexity of this approach is linear in max(y-x,0); it will take a while if your range of integers is large; see the benchmark at the bottom of my answer.

但是，因为有一个公式来计算前 n 个(正)整数，您实际上不必将这些平方一一求和.

However, because there is a formula for the sum of the squares of the first n (positive) integers, you don't actually have to sum those squares one by one.

在 x 大于 y 的情况下向用户发出错误消息(如 你的评论)，你可以在这里简单地使用error函数.

To issue an error message to the user in case x is greater that y (as specified in your comment), you can simply use the error function, here.

(编辑:感谢 Chris Drost 指出我把事情复杂化了)

(Edit: thanks to Chris Drost for pointing out that I was overcomplicating things)

sumOfSquaresFast :: Integral a => a -> a -> a
sumOfSquaresFast lo hi
    | lo > hi   = error "sumOfSquaresFast: lo > hi"
    | otherwise = ssq hi - ssq (lo - 1)
  where
    ssq x = div (((2 * x + 3) * x + 1) * x) 6

改用这个公式可以将复杂性降低到接近恒定时间的程度.

Using this formula instead reduces the complexity to something close to constant time.

λ> :set +s

λ> sumOfSquaresSlow (10^3)  (10^7)
333333383333002166500
(17.19 secs, 11563005552 bytes)

λ> sumOfSquaresFast (10^3) (10^7)
333333383333002166500
(0.01 secs, 3106112 bytes)

这篇关于使用 Haskell 求平方和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！