Computing the partition function for a single value

[rockbmb]

After #107, this library now offers a way to calculate a contiguous sequence of values of the partition function.

However, for a large, isolated n, this is impractical because all values up to this n have to be calculated, and as stated here, it is not possible to calculate beyond the 2^64-th element of this (zero-indexed) sequence (on 64 bit machines).

For the purpose of calculating p(n) for a single value, the Hardy-Ramanujan-Rademacher formula exists.

This issue will be about writing a new function partitionOf :: Integral a => Natural -> a (the type is most likely wrong and the name can be made more suggestive later).

@Bodigrim would you find this worthwhile?

[Bodigrim]

Yeah, it sounds very interesting.

[rockbmb]

As a first observation, the calculation of p(n) requires O(n^1/2) = O(sqrt n) bits, so Double is out of the question. Data.Numbers.Fixed from numbers is an alternative, though the Prec datatypes will need to be generalized to allow for different precision fixed point numbers (similar to the PR I made for Data.Fixed).

[Bodigrim]

Maybe try bindings to MPFR?
http://hackage.haskell.org/package/hmpfr
(API is horrible, I wonder if one can have proper Num and Floating instances, storing RoundMode and Precision on type level)

[rockbmb]

I don't think that will be necessary. There already exists an Epsilon e => Floating (Fixed e) instance, so all that will be necessary when calculating p(n) is

1. Write an instance (Integral a) => Epsilon a', where a' is the a value as a type
2. Some type-level programming to reify a number O(integerSqrt n) to become Fixed's type argument.

I get the feeling 1. won't work, but if it does this'll be relatively easy.

[rockbmb]

@Bodigrim I was taking a closer look at MPFR, and yes, the API is not very nice to work with. I'm currently working through the paper, and it seems the most troublesome terms are those at lower indices, which require a lot of precision.

I also see plenty of mentions to floating precision (some to MPFR), I'll have to get a better understanding of the paper because I don't yet understand how 64-bit floating point numbers are used to calculate numbers with billions of digits. I am missing something.

[rockbmb]

@Bodigrim I've only taken a cursory look, but there's this alternative to hmpfr. Have you seen this before? The type literals idea is basically what I had in mind, but much more polished.

[Bodigrim]

rounded looks nice, but I have not used it.

[Bodigrim]

Closing, since #149 has been withdrawn.