共同LISP和堆栈中的数字类型边界在GHCI中流动 [英] Number type boundaries in Common LISP and Stack flowing over in GHCI

问题描述

第一个问题在这里，并且在Common LISP和Haskell中都是新手，请友好。
我在Common LISP中有一个函数 - 下面的代码 - 它是用来判断一个三角形的面积是一个整数（整数？）。

<$ p （*（（s（/（+ abc）2））
（面积（sqrt（* s（$ s）如果（等于（上限面积）（面积））
t
无）））
（ - sb）（ - sc））））
code>

这应该使用 Heron公式来计算三角形的面积，并给出三面的大小，并决定它是否是一个整数，比较天花板和地面。我们被告知等边三角形的面积从来不是一个整数。因此，为了测试函数是否正常工作，我使用参数 333 来运行它。这是我得到的回报：

  CL-USER> （area-int-p 333 333 333）
无
  

完美！有用。为了测试它，我使用参数 3333 来运行它。这是我得到的回报：

  CL-USER> （area-int-p 3333 3333 3333）
 T 
  

有些错误，这是不应该发生！
因此，我尝试了下面的，希望等价的Haskell函数来看看会发生什么：

  areaIntP ::（Integral a ）=> a  - > a  - > a  - > Bool 
 areaIntP abc = 
 let aa = fromIntegral a 
 bb = fromIntegral b 
 cc = fromIntegral c 
 perimeter = aa + bb + cc 
s =周长/ 2 
 area = sqrt（s *（s  -  aa）*（s  -  bb）*（s  -  cc））
 in if ceiling area == floor area 
 then True 
 else False 
  

这就是我得到的结果：

  * Main> areaIntP 3333 3333 3333 
 False 
 * Main> areaIntP 333 333 333 
 False 
  

看起来很完美。在此鼓励下，我使用Haskell中的以下函数来将等腰三角形的边界与第三方的边界相加，所述第三边与另一边的距离仅为一个单位，积分区域以及低于10亿英寸的边界。

  toplamArtilar :: Integral a => a  - > a  - > a  - > a 
 toplamArtilar altSinir ustSinir toplam = 
 if ustSinir == altSinir 
 then toplam 
 else if areaIntP ustSinir ustSinir（ustSinir + 1）== True 
 then toplamArtilar altSinir（ ustSinir  -  1）（toplam +（3 * ustSinir + 1））
 else toplamArtilar altSinir（ustSinir  -  1）toplam 
 
 toplamEksiler :: Integral a => a  - > a  - > a  - > a 
 toplamEksiler altSinir ustSinir toplam = 
 if ustSinir == altSinir 
 then toplam 
 else if areaIntP ustSinir ustSinir（ustSinir  -  1）== True 
 then toplamEksiler altSinir（ ustSinir  -  1）（toplam +（3 * ustSinir  -  1））
 else toplamEksiler altSinir（ustSinir  -  1）toplam 
 
 sonuc altSinir ustSinir = 
 toplamEksiler altSinir ustSinir（toplamArtilar altSinir ustSinir 0）
  

（ ustSinir 表示上限， altSinir 的下限）
运行 sonuc 参数 2 和 333333333 但是，我的堆栈流过。在Common LISP中运行相同的函数，堆栈是可以的，但是 area-int-p 函数不可靠，可能是由于解释器推断的数字类型的边界。
毕竟，我的问题是双重的：

1）如何解决Common LISP函数 2）我如何通过上面的Haskell函数来防止堆栈溢出，或者在Emacs中运行，或者用GHCi运行从终端？

请注意那些想知道我在这里实现的内容：请不要告诉我使用Java BigDecimal 和 BigInteger 。

在非常好的回复后编辑：我在一个问中提出了两个问题，并且获得了非常满意的，新手友好的答案以及来自非常有帮助的人的风格说明。

解决方案

我们定义一个中间的Common Lisp函数：

<$ （*（s（ - abc）2）））
（sqrt（* s（ - sa）（ - sb）（ - sc））））


您的测试结果如下：

  CL-USER> （面积333 333 333）
 48016.344 
 
 CL-USER> （面积3333 3333 3333）
 4810290.0 
  

在第二种情况下，应该清楚天花板和地板都是平等的。在Haskell中，第二个测试（3333）返回的情况并非如此：

  4810290.040910754 
  
 
浮点
 
 
 
在Common Lisp中，我们取一个正方形的值根是：
  370222244442963/16 
  
这是因为计算是用有理数进行的。到目前为止，精度是最高的。但是，  SQRT  是免费的在可能的情况下返回理性结果，或者返回近似结果。作为特例，Rainer Joswig在评论中指出，结果在某些实现中可能是整数。这很有意义，因为  和比例是 类型的不相交子类型。但是，正如你的问题所显示的那样，一些平方根是不合理的（例如√2），并且在这种情况下，CL可以返回一个接近该值的浮点数（或者一个复数浮点数）。 
 
 
关于浮点数和数学函数的相关章节是 12.1.3.3浮点数可替换性规则。长话短说，当您计算平方根时，结果会转换为单浮点数，这会发生一些精确性。为了有一个双重的，你必须更加明确：
 
 $ $ p $ （defun area（abc）
（let （（s（/（+ abc）2）））
（sqrt（float（* s（ -  sa）（ -  sb）（ -  sc））0d0））））
  

我也可以使用（coerce ...'double-float），但在这里
我选择调用 FLOAT 0d0 ，一个双重浮动。您也可以使用 0l0 作为长双打或 0s0 。如果您希望与输入float具有相同的精度，但该参数非常有用，但也可以与文字一起使用，如示例中所示。短，单，双或长浮点类型的确切含义是由实现定义的，但它们应该遵守一些规则。

  CL-USER>目前的实施方式通常会提供更高的精确度。 （面积3333 3333 3333）
 4810290.040910754d0 
  

现在，如果我想测试结果是不可或缺的，我会截断浮点数，并查看第二个返回值，其余部分是否为零。



  CL-USER> ; （zerop（nth-value 1（truncate 4810290.040910754d0）））
 NIL 
  





任意 - 精确

请注意，无论实现语言（Haskell，CL还是其他语言），该方法都会给出一些输入的不正确结果，因为它表示浮点数。事实上，与CL相同的问题可能会导致更精确的浮点数输入，其结果会非常接近整数。您可能需要使用其他数学方法或 MPFR 来进行任意精度浮点计算。 SBCL附带 sb-mpfr ：

  CL-USER> （要求：sb-mpfr）
（SB-MPFRSB-GMP）
 
 CL-USER> （in-package：sb-mpfr）
＃< PACKAGESB-MPFR> 
  

然后：

  SB-MPFR> （精度为256 
（sqrt（强制370222244442963/16'mpfr-float）））
 .4810290040910754427104204965311207243133723228299086361205561385039201180068712e + 7 
 -1 
  

First question ever here, and newbie in both Common LISP and Haskell, please be kind. I have a function in Common LISP - code below - which is intended to tell whether the area of a triangle is an integral number (integer?).

(defun area-int-p (a b c)
  (let* ((s (/ (+ a b c) 2))
         (area (sqrt (* s (- s a) (- s b) (- s c)))))
    (if (equal (ceiling area) (floor area))
        t
        nil)))

This is supposed to use Heron's formula to calculate the area of the triangle, given the size of the three sides, and decide whether it is an integer comparing the ceiling and the floor. We are told that the area of an equilateral triangle is never an integer. Therefore, to test whether the function is working, I ran it with the arguments 333. Here is what I got in return:

CL-USER> (area-int-p 333 333 333)
NIL

Perfect! It works. To test it even more, I ran it with the arguments 3333. This is what I got in return:

CL-USER> (area-int-p 3333 3333 3333)
T

Something is wrong, this is not supposed to happen! So, I try the following, hopefully equivalent Haskell function to see what happens:

areaIntP :: (Integral a) => a -> a -> a -> Bool
areaIntP a b c =
  let aa = fromIntegral a
      bb = fromIntegral b
      cc = fromIntegral c
      perimeter = aa + bb + cc
      s = perimeter/2
      area = sqrt(s * (s - aa) * (s - bb) * (s - cc))
  in  if ceiling area == floor area
      then True
      else False

This is what I get:

*Main> areaIntP 3333 3333 3333
False
*Main> areaIntP 333 333 333
False

Looks perfect. Encouraged by this, I use the below functions in Haskell to sum the perimeters of of isosceles triangles with the third side differing just one unit from the other sides, an integral area, and perimeter below 1,000,000,000.

toplamArtilar :: Integral a => a -> a -> a -> a
toplamArtilar altSinir ustSinir toplam =
  if ustSinir == altSinir
  then toplam
  else if areaIntP ustSinir ustSinir (ustSinir + 1) == True
       then toplamArtilar altSinir (ustSinir - 1) (toplam + (3 * ustSinir + 1))
       else toplamArtilar altSinir (ustSinir - 1) toplam

toplamEksiler :: Integral a => a -> a -> a -> a
toplamEksiler altSinir ustSinir toplam =
  if ustSinir == altSinir
  then toplam
  else if areaIntP ustSinir ustSinir (ustSinir - 1) == True
       then toplamEksiler altSinir (ustSinir - 1) (toplam + (3 * ustSinir - 1))
       else toplamEksiler altSinir (ustSinir - 1) toplam

sonuc altSinir ustSinir =
  toplamEksiler altSinir ustSinir (toplamArtilar altSinir ustSinir 0)

(ustSinir means upper limit, altSinir lower limit by the way.) Running sonuc with the arguments 2 and 333333333 however, my stack flows over. Runnning the equivalent functions in Common LISP the stack is OK, but area-int-p function is not reliable, probably because of the boundaries of the number type the interpreter deduces. After all this, my question is two-fold:

1) How do I get round the problem in the Common LISP function area-int-p?

2) How do I prevent the stack overflow with the Haskell functions above, either within Emacs or with GHCi run from the terminal?

Note for those who figure out what I am trying to achieve here: please don't tell me to use Java BigDecimal and BigInteger.

Edit after very good replies: I asked two questions in one, and received perfectly satisfying, newbie friendly answers and a note on style from very helpful people. Thank you.

解决方案

Let's define an intermediate Common Lisp function:

(defun area (a b c)
  (let ((s (/ (+ a b c) 2)))
    (sqrt (* s (- s a) (- s b) (- s c)))))

Your tests give:

CL-USER> (area 333 333 333)
48016.344

CL-USER> (area 3333 3333 3333)
4810290.0

In the second case, it should be clear that both the ceiling and floor are equal. This is not the case in Haskell where the second test, with 3333, returns:

4810290.040910754

Floating point

In Common Lisp, the value from which we take a square root is:

370222244442963/16 

This is because computations are made with rational numbers. Up to this point, the precision is maximal. However, SQRT is free to return either a rational, when possible, or an approximate result. As a special case, the result can be an integer on some implementations, as Rainer Joswig pointed out in a comment. It makes sense because both integer and ratio are disjoint subtypes of the rational type. But as your problem shows, some square roots are irrational (e.g. √2), and in that case CL can return a float approximating the value (or a complex float).

The relevant section regarding floats and mathematical functions is 12.1.3.3 Rule of Float Substitutability. Long story short, the result is converted to a single-float when you compute the square root, which happens to loose some precision. In order to have a double, you have to be more explicit:

(defun area (a b c)
   (let ((s (/ (+ a b c) 2)))
     (sqrt (float (* s (- s a) (- s b) (- s c)) 0d0))))

I could also have used (coerce ... 'double-float), but here I chose to call the FLOAT conversion function. The optional second argument is a float prototype, ie. a value of the target type. Above, it is 0d0, a double float. You could also use 0l0 for long doubles or 0s0 for short. This parameter is useful if you want to have the same precision as an input float, but can be used with literals too, like in the example. The exact meaning of short, single, double or long float types is implementation-defined, but they shall respect some rules. Current implementations generally give more precision that the minimum required.

CL-USER> (area 3333 3333 3333)
4810290.040910754d0

Now, if I wanted to test if the result is integral, I would truncate the float and look if the second returned value, the remainder, is zero.

CL-USER> (zerop (nth-value 1 (truncate 4810290.040910754d0)))
NIL

Arbitrary-precision

Note that regardless of the implementation language (Haskell, CL or another one) the approach is going to give incorrect results for some inputs, given how floats are represented. Indeed, the same problem you had with CL could arise for some inputs with more precise floats, where the result would be very close to an integer. You might need another mathematical approach or something like MPFR for arbitrary precision floating point computations. SBCL ships with sb-mpfr:

CL-USER> (require :sb-mpfr)
("SB-MPFR" "SB-GMP")

CL-USER> (in-package :sb-mpfr)
#<PACKAGE "SB-MPFR">

And then:

SB-MPFR> (with-precision 256
           (sqrt (coerce 370222244442963/16 'mpfr-float)))
.4810290040910754427104204965311207243133723228299086361205561385039201180068712e+7
-1

这篇关于共同LISP和堆栈中的数字类型边界在GHCI中流动的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！