search

Bodigrim / arithmoi

Number theory: primes, arithmetic functions, modular computations, special sequences
http://hackage.haskell.org/package/arithmoi
MIT License
147 stars 40 forks source link

Computing the partition function for a single value #149

Closed rockbmb closed 4 years ago

rockbmb commented 5 years ago

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 commented 5 years ago

Yeah, it sounds very interesting.

rockbmb commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

@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 commented 5 years ago

@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 commented 5 years ago

rounded looks nice, but I have not used it.

Bodigrim commented 4 years ago

Closing, since #149 has been withdrawn.