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

Implementation of Ramanujan tau-function #112

Closed b-mehta closed 6 years ago

b-mehta commented 6 years ago

Fixes #106, using the first formula given here and the second from here. The latter could be improved to the binomial summation formula instead, which would prevent lots of unnecessary recalculation for primes to a large power, but this requires an implementation of binomial coefficients as well. Tested against OEIS and congruences 1-4 and 8,9 listed here: note congruence 10 is automatically satisfied by definition. An alternative method is proposed in equation 10 or in Charles 2006.

Bodigrim commented 6 years ago

Super cool! Extra kudos for tests.

The latter could be improved to the binomial summation formula instead, which would prevent lots of unnecessary recalculation for primes to a large power, but this requires an implementation of binomial coefficients as well.

Binomial coefficients are implement as Math.NumberTheory.Recurrencies.Bilinear.binomial.

b-mehta commented 6 years ago

Thank you! Ah, I didn't look hard enough clearly for binomial coefficients. I'll have a closer look later.

Bodigrim commented 6 years ago

Nice. Could you also please add a simple benchmark to Math.NumberTheory.ArithmeticFunctionsBench?

b-mehta commented 6 years ago

I've added a benchmark, but the function is significantly slower than the others in the same group so I've used a smaller range.

Bodigrim commented 6 years ago

Well done! Taking into account the nature of computations, I suggest to add two pointwise benchmarks:

Bodigrim commented 6 years ago

@b-mehta any chance to improve tests soon? Otherwise I can merge it as is.

b-mehta commented 6 years ago

Apologies, I'll improve tests soon - I also suspect the triangular formula in equation 10 will be more efficient for computing values of tau for ranges [1..n] which I'm keen to investigate. For specific values it doesn't seem to create an improvement though.

Bodigrim commented 6 years ago

Since Ramanujan tau is multiplicative, one can use Math.NumberTheory.ArithmeticFunctions.SieveBlock to evaluate it over a range [1..n].

b-mehta commented 6 years ago

Sure, but I suspect the triangular number formula may be significantly more efficient

Bodigrim commented 6 years ago

Looks great! I am keen to merge, if you do not mind. Bulk computations over [1..n] may be a subject of a separate branch.

b-mehta commented 6 years ago

Sure, sounds good to me.