История изменений

Исправление Waterlaz, 11.12.21 02:11 (текущая версия) :

Я тут чуть-чуть наговнокодил. Моих знаний Хаскела сделать быстро красивее не хватает.

import Data.Ratio
import Data.List

data Sum = Sum  [(Rational, Rational)]

takeWhileOneMore p = foldr (\x ys -> if p x then x:ys else [x]) []

eval precision (Sum xs) =
    sum $ map fst $ takeWhileOneMore ((>precision).snd) xs

instance Num Sum where
    Sum xs + Sum ys = Sum $ zipWith (\(a1, b1) (a2, b2) -> (a1+a2, b1+b2) ) xs ys
    Sum xs * Sum ys = Sum zs where
        psx = scanl1 (+) $ map fst xs
        psy = scanl1 (+) $ map fst ys
        psz = zipWith (*) psx psy
        as = zipWith (-) psz (0:psz)
        ds = zipWith4 (\sx sy dx dy -> (abs sx)*dy + (abs sy)*dx + dx*dy) psx psy (map snd xs) (map snd ys)
        zs = zip as ds
    negate (Sum xs) = Sum $ map (\(a, b) -> (-a, b)) xs
    fromInteger i = Sum $ (i%1, 0) : repeat (0, 0)

sqrt' :: Rational -> Sum
sqrt' x = res
    where res = Sum $ zip as $ map (\s -> abs (s - x/s)) ps
          as = a1 : map (\s -> (x/s - s)/2) ps
          ps = scanl1 (+) as
          a1 = fromIntegral (floor $ sqrt $ fromRational x) % 1

Смысл в том, что числа x представляются бесконечной последовательностью пар рациональных (aᵢ, bᵢ) таких, что
x = a₁ + a₂ + a₃ + ...
bᵢ ≥ |aᵢ₊₁ + aᵢ₊₂ + aᵢ₊₃ + ...|
bᵢ -> 0

Ну и пример использования:

Создаем пару чисел s2 = √2 и s3 = √3:

*Main> s2 = sqrt' 2
*Main> s3 = sqrt' 3

Их можно 'вычислить' с любой наперёд заданной точностью как рациональное число, которое, естественно, можно перевести и в Double:

*Main> eval (1%100) s2
17 % 12
*Main> eval (1%1000) s2
577 % 408
*Main> eval (1%1000000) s2
665857 % 470832
*Main> fromRational $ eval (1%100) s2
1.4166666666666667
*Main> fromRational $ eval (1%1000) s2
1.4142156862745099
*Main> fromRational $ eval (1%1000000) s2
1.4142135623746899

С числами можно делать арифметические операции. Ожидаемо x = (√3-√2)*(√3+√2) = 1

*Main> x = (s3-s2)*(s3+s2)
*Main> eval (1%100) x
1019911 % 1019592
*Main> fromRational $ eval (1%100) x
1.0003128702461377
*Main> fromRational $ eval (1%1000) x
1.0003128702461377
*Main> fromRational $ eval (1%1000000) x
1.0000000084681628

Исправление Waterlaz, 11.12.21 01:57:

Я тут чуть-чуть наговнокодил. Моих знаний Хаскела сделать быстро красивее не хватает.

import Data.Ratio
import Data.List

data Sum = Sum  [(Rational, Rational)]

takeWhileOneMore p = foldr (\x ys -> if p x then x:ys else [x]) []

eval precision (Sum xs) =
    sum $ map fst $ takeWhileOneMore ((>precision).snd) xs

instance Num Sum where
    Sum xs + Sum ys = Sum $ zipWith (\(a1, b1) (a2, b2) -> (a1+a2, b1+b2) ) xs ys
    Sum xs * Sum ys = Sum zs where
        psx = scanl1 (+) $ map fst xs
        psy = scanl1 (+) $ map fst ys
        psz = zipWith (*) psx psy
        as = zipWith (-) psz (0:psz)
        ds = zipWith4 (\sx sy dx dy -> (abs sx)*dy + (abs sy)*dx + dx*dy) psx psy (map snd xs) (map snd ys)
        zs = zip as ds
    negate (Sum xs) = Sum $ map (\(a, b) -> (-a, b)) xs
    fromInteger i = Sum $ (i%1, 0) : repeat (0, 0)

sqrt' :: Rational -> Sum
sqrt' x = res
    where res = Sum $ zip as $ map (\s -> abs (s - x/s)) ps
          as = a1 : map (\s -> (x/s - s)/2) ps
          ps = scanl1 (+) as
          a1 = fromIntegral (floor $ sqrt $ fromRational x) % 1

Смысл в том, что числа x представляются бесконечной последовательностью пар рациональных (aᵢ, bᵢ) таких, что
x = a₁ + a₂ + a₃ + ...
bᵢ ≥ aᵢ₊₁ + aᵢ₊₂ + aᵢ₊₃ + ...
bᵢ -> 0

Ну и пример использования:

Создаем пару чисел s2 = √2 и s3 = √3:

*Main> s2 = sqrt' 2
*Main> s3 = sqrt' 3

*Main> eval (1%100) s2
17 % 12
*Main> eval (1%1000) s2
577 % 408
*Main> eval (1%1000000) s2
665857 % 470832
*Main> fromRational $ eval (1%100) s2
1.4166666666666667
*Main> fromRational $ eval (1%1000) s2
1.4142156862745099
*Main> fromRational $ eval (1%1000000) s2
1.4142135623746899

С числами можно делать арифметические операции. Ожидаемо x = (√3-√2)*(√3+√2) = 1

*Main> x = (s3-s2)*(s3+s2)
*Main> eval (1%100) x
1019911 % 1019592
*Main> fromRational $ eval (1%100) x
1.0003128702461377
*Main> fromRational $ eval (1%1000) x
1.0003128702461377
*Main> fromRational $ eval (1%1000000) x
1.0000000084681628

Исходная версия Waterlaz, 11.12.21 01:56:

Я тут чуть-чуть наговнокодил. Моих знаний Хаскела сделать быстро красивее не хватает.

import Data.Ratio
import Data.List

data Sum = Sum  [(Rational, Rational)]

takeWhileOneMore p = foldr (\x ys -> if p x then x:ys else [x]) []

eval precision (Sum xs) =
    sum $ map fst $ takeWhileOneMore ((>precision).snd) xs

instance Num Sum where
    Sum xs + Sum ys = Sum $ zipWith (\(a1, b1) (a2, b2) -> (a1+a2, b1+b2) ) xs ys
    Sum xs * Sum ys = Sum zs where
        psx = scanl1 (+) $ map fst xs
        psy = scanl1 (+) $ map fst ys
        psz = zipWith (*) psx psy
        as = zipWith (-) psz (0:psz)
        ds = zipWith4 (\sx sy dx dy -> (abs sx)*dy + (abs sy)*dx + dx*dy) psx psy (map snd xs) (map snd ys)
        zs = zip as ds
    negate (Sum xs) = Sum $ map (\(a, b) -> (-a, b)) xs
    fromInteger i = Sum $ (i%1, 0) : repeat (0, 0)

sqrt' :: Rational -> Sum
sqrt' x = res
    where res = Sum $ zip as $ map (\s -> abs (s - x/s)) ps
          as = a1 : map (\s -> (x/s - s)/2) ps
          ps = scanl1 (+) as
          a1 = fromIntegral (floor $ sqrt $ fromRational x) % 1

Смысл в то, что числа x представляются бесконечной последователностью пар (aᵢ, bᵢ) таких, что
x = a₁ + a₂ + a₃ + ...
bᵢ ≥ aᵢ₊₁ + aᵢ₊₂ + aᵢ₊₃ + ...
bᵢ -> 0

Ну и пример использования:

Создаем пару чисел s2 = √2 и s3 = √3:

*Main> s2 = sqrt' 2
*Main> s3 = sqrt' 3

Их можно 'вычислить' с любой наперёд заданной точностью, как рациональное число, которое, естественно, можно перевести и в Double:

*Main> eval (1%100) s2
17 % 12
*Main> eval (1%1000) s2
577 % 408
*Main> eval (1%1000000) s2
665857 % 470832
*Main> fromRational $ eval (1%100) s2
1.4166666666666667
*Main> fromRational $ eval (1%1000) s2
1.4142156862745099
*Main> fromRational $ eval (1%1000000) s2
1.4142135623746899

С числами можно делать арифметические операции. Ожидаемо x = (√3-√2)*(√3+√2) = 1

*Main> x = (s3-s2)*(s3+s2)
*Main> eval (1%100) x
1019911 % 1019592
*Main> fromRational $ eval (1%100) x
1.0003128702461377
*Main> fromRational $ eval (1%1000) x
1.0003128702461377
*Main> fromRational $ eval (1%1000000) x
1.0000000084681628