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

问题描述

我试图进行以下计算：
范围x：y中整数的平方和（x <= y）。

我不确定如何设置一个约束来确保x小于或等于y。

我需要能够将平方x到x + 1：y范围内的平方和。

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

更新：为了澄清，我不想硬编码[1..5 ]的功能，但我希望列表是用户的输入。

任何帮助？

谢谢

解决方案

缓慢的做法

显而易见的方法是实际上就是这些方块的总和：

  sumOfSquaresSlow :: Integral a => a  - > a  - > 
 sumOfSquaresSlow lo hi 
 | lo> hi =错误sumOfSquaresSlow：lo> hi
 |否则=总和$ map（^ 2）[lo..hi] 
  

这种方法的时间复杂度在max（yx，0）中是线性的;如果整数范围很大，则需要一段时间;看到我的答案底部的基准。

更快的方法

然而，因为有一个公式为前n个（正整数）整数的平方和，实际上必须一个接一个地求和这些方块。

如果 x 为用户发出错误信息大于 y （详见您的评论），您可以在这里简单地使用错误函数。

strong>编辑：感谢Chris Drost的指出我是）

  sumOfSquaresFast :: Integral a => a  - > a  - > 
 sumOfSquaresFast lo hi 
 | lo> hi =错误sumOfSquaresFast：lo> hi
 |否则= ssq hi  -  ssq（lo  -  1）
其中
 ssq x = div（（（2 * x + 3）* x + 1）* x）6 
  
 
使用这个公式可以将复杂度降低到接近恒定时间的水平。
 
 
 
 GHCi中的基准 
 
 
 λ> ：set + s 
 
λ> sumOfSquaresSlow（10 ^ 3）（10 ^ 7）
 333333383333002166500 
（17.19秒，11563005552字节）
 
λ> sumOfSquaresFast（10 ^ 3）（10 ^ 7）
 333333383333002166500 
（0.01秒，3106112字节）
  
 
I'm trying to carry out the following computation:
sum of the squares of integers in the range x:y where (x <= y).

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

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

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]

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.

Any help?

Thanks
解决方案
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]
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.

Faster approach

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.

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.

(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.

Benchmark in GHCi

λ> :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屋！