Haskell: как я могу использовать математические функции, такие как "logBase", для работы с неограниченными целыми числами? - PullRequest
Новая
       19

Haskell: как я могу использовать математические функции, такие как "logBase", для работы с неограниченными целыми числами?

3 голосов
/ 30 июня 2011

Я пытаюсь создать список чисел Фибоначчи для сравнения со списком простых чисел (например).Оба списка начинаются с первого известного числа Фибо / простого числа и заканчиваются 10000-м.Проблема в том, что графическое сравнение (диаграмма) возможно только в том случае, если к числам фибоначчи применяется какая-то функция, такая как «logBase 2», а «logBase» работает только (?) С «плавающими» числами.К сожалению, числа Фибоначчи становятся огромными, поэтому я думаю, что числа Фибоначчи должны быть «целыми» (неограниченными).

Это приводит к проблемам с конвертацией.

Пример (Двойное по сравнению с целым числом по сравнению с рациональным): 

Prelude> (fromInteger 99^155 :: Double) 
Infinity

Prelude> 99^155
2105984461967288122980631709715261275645844225982779394351624787177327329412781425212770617487844004735075332631944629831514476725173837569097618069672639524362255333585985536520710945968603104880488606713054412670128838036813075895861981025491395960367363513228812061706617371582639821584522415306665565665499

Prelude> logBase 2 $ fromRational (fromInteger 99^155 :: Rational) 
Infinity

Поэтому возникает вопрос: как я могу использовать математические функции, такие как «logBase», для работы с неограниченными целыми числами?Какой-нибудь намек?

1 Ответ

2 голосов
/ 30 июня 2011

Как насчет использования математических свойств журнала - что-то вроде 

{-# LANGUAGE ScopedTypeVariables #-}

logBaseRational :: forall a . (RealFloat a, Floating a) => Rational -> Rational -> a
logBaseRational k n | isInfinite (fromRational n :: a) = logBaseRational k (n/k) + 1
logBaseRational k n | isDenormalized (fromRational n :: a) = logBaseRational k (n*k) - 1
logBaseRational k n = logBase (fromRational k) (fromRational n)

Что-то более эффективное можно сделать, если вам нужно обрабатывать действительно большие числа, но это должно быть сделано для интересующего вас диапазона.

Использование ScopedTypeVariables просто для того, чтобы гарантировать, что isInfinite и isDenormalized тесты выполнены в правильном типе.

Кроме того, isDenormalized не является полнымпроверить нижний предел диапазона - вам нужно проверить и это (из-за проблем с потерей точности), а также то, является ли преобразованное значение 0, если не преобразованное значение - но, так как этот вопрос о большомтолько цифры, это не важно, я просто добавил, чтобы мой ответ был более общим.

...