Странное поведение (^) в Haskell

12

Почему GHCi дает неправильный ответ ниже?

GHCi

λ> ((-20.24373193905347)^12)^2 - ((-20.24373193905347)^24)
4.503599627370496e15

python3

>>> ((-20.24373193905347)**12)**2 - ((-20.24373193905347)**24)
0.0

ОБНОВЛЕНИЕ Я бы реализовал функцию Haskell (^) следующим образом.

powerXY :: Double -> Int -> Double
powerXY x 0 = 1
powerXY x y
    | y < 0 = powerXY (1/x) (-y)
    | otherwise = 
        let z = powerXY x (y `div` 2)
        in  if odd y then z*z*x else z*z

main = do 
    let x = -20.24373193905347
    print $ powerXY (powerXY x 12) 2 - powerXY x 24 -- 0
    print $ ((x^12)^2) - (x ^ 24) -- 4.503599627370496e15

Хотя моя версия не выглядит более правильной, чем приведенная ниже @WillemVanOnsem, она как минимум странно дает правильный ответ для этого конкретного случая.

Python похож.

def pw(x, y):
    if y < 0:
        return pw(1/x, -y)
    if y == 0:
        return 1
    z = pw(x, y//2)
    if y % 2 == 1:
        return z*z*x
    else:
        return z*z

# prints 0.0
print(pw(pw(-20.24373193905347, 12), 2) - pw(-20.24373193905347, 24))
Случайный чувак
источник
Это ошибка мантиссы. a^24примерно 2.2437e31, и, следовательно, есть ошибка округления, которая производит это.
Виллем Ван Онсем
Я не понимаю Почему в GHCi есть ошибка округления?
Случайный чувак
это не имеет ничего общего с ghci, это просто то, как модуль с плавающей запятой обрабатывает плавающие числа.
Виллем Ван Онсем
1
Это вычисляет, у 2.243746917640863e31 - 2.2437469176408626e31которого есть небольшая ошибка округления, которая усиливается. Похоже, вопрос отмены.
чи
2
Может быть, Python использует другой алгоритм возведения в степень, который в этом случае является более точным? В общем, независимо от того, какой язык вы используете, операции с плавающей запятой имеют некоторую ошибку округления. Тем не менее, было бы интересно понять различия между этими двумя алгоритмами.
чи

Ответы:

14

Краткий ответ : есть разница между (^) :: (Num a, Integral b) => a -> b -> aи (**) :: Floating a => a -> a -> a.

(^)Функция работает только на интегральных показателях. Обычно он использует итеративный алгоритм, который каждый раз проверяет, делится ли мощность на два, и делит мощность на два (и, если не делится, умножает результат на x). Таким образом, это означает, что для 12, он будет выполнять в общей сложности шесть умножений. Если умножение имеет определенную ошибку округления, эта ошибка может «взорваться». Как мы видим из исходного кода , (^)функция реализована следующим образом :

(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0    = errorWithoutStackTrace "Negative exponent"
        | y0 == 0   = 1
        | otherwise = f x0 y0
    where -- f : x0 ^ y0 = x ^ y
          f x y | even y    = f (x * x) (y `quot` 2)
                | y == 1    = x
                | otherwise = g (x * x) (y `quot` 2) x         -- See Note [Half of y - 1]
          -- g : x0 ^ y0 = (x ^ y) * z
          g x y z | even y = g (x * x) (y `quot` 2) z
                  | y == 1 = x * z
                  | otherwise = g (x * x) (y `quot` 2) (x * z) -- See Note [Half of y - 1]

(**)Функция, по крайней мере, Floatс и Doubleы реализована для работы на устройстве с плавающей точкой. Действительно, если мы посмотрим на реализацию (**), мы увидим:

instance Floating Float where
    -- …
    (**) x y = powerFloat x y
    -- …

Таким образом, это перенаправляет powerFloat# :: Float# -> Float# -> Float#функцию, которая обычно будет связана с соответствующей операцией (-ами) FPU компилятором.

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

Prelude> (a**12)**2 - a**24
0.0

Мы можем, например, реализовать итерационный алгоритм в Python:

def pw(x0, y0):
    if y0 < 0:
        raise Error()
    if y0 == 0:
        return 1
    return f(x0, y0)


def f(x, y):
    if (y % 2 == 0):
        return f(x*x, y//2)
    if y == 1:
        return x
    return g(x*x, y // 2, x)


def g(x, y, z):
    if (y % 2 == 0):
        return g(x*x, y//2, z)
    if y == 1:
        return x*z
    return g(x*x, y//2, x*z)

Если мы затем выполняем ту же операцию, я получаю локально:

>>> pw(pw(-20.24373193905347, 12), 2) - pw(-20.24373193905347, 24)
4503599627370496.0

Это то же значение, что мы получаем (^)в GHCi.

Виллем Ван Онсем
источник
1
Итерационный алгоритм для (^) при реализации в Python не дает этой ошибки округления. Отличается ли (*) в Haskell и Python?
Случайный чувак
@Randomdude: насколько я знаю, pow(..)функция в Python имеет только определенный алгоритм для "int / long", а не для float. Для поплавков это будет «запасной вариант» по мощности FPU.
Виллем Ван Онсем
Я имею в виду, когда я сам реализую функцию power с использованием (*) в Python так же, как реализация (^) на Haskell. Я не использую pow()функцию.
Случайный чувак
2
@Randomdude: Я реализовал алгоритм в Python и получил то же значение, что и в ghc.
Виллем Ван Онсем
1
Обновил мой вопрос, добавив версии (^) в Haskell и Python. Мысли, пожалуйста?
Случайный чувак