[boost] [GSoC 2013] Boost.Math Bernoulli Numbers and Applications to Special Functions

Subject: [boost] [GSoC 2013] Boost.Math Bernoulli Numbers and Applications to Special Functions
From: Łukasz Marecik (lm277561_at_[hidden])
Date: 2013-04-30 10:39:08

Hi,

My name is Lukasz Marecik, I am fifth year student of Mathematics and  
fourth year student of Computer Science at Warsaw University. I would  
like to apply to Google Summer of Code 2013 project. I am interested  
in Bernoulli Numbers and their applications. While thinking about this  
project and doing some research, I collected some questions and  
issues, which I would like to discuss with my (potential) mentors. The  
answers can have strong influence at my official proposal.

1. Is (one of) the goal of this project to implement FROM SCRATCH  
completely new boost library, which will calculate Bernoulli Numbers ?  
I have already found two great C++ open-source programs:
- http://www.bernoulli.org/
- http://web.maths.unsw.edu.au/~davidharvey/papers/bernmm/
They are already extremely efficient and fast (the funny thing is that  
they use completely different approach). Can boost project include and  
adapt one of them ? Why not ?

2. Are we going to implement only precise calculation of Bernoulli  
numbers or also Bernoulli numbers modulo p (where p is prime) ?

3. How the implementation of method of computing Bernoulli numbers  
will look like? Will it be a big template which works with all  
(reasonable) types (built-in, multiprecision) in the same way ? I was  
thinking for a while about this and I think it would be better to  
implement separately computing rational Bernoulli numbers (e.g.  
gmp_rational type) in a modern way: compute B_n modulo a lot of small  
primes and then reconstruct B_n via Chinese Remainder Theorem. This  
algorithm is one of the faster for this concrete type: precise  
rational numbers, but (in my opinion) it will be inefficient, when we  
want the output be built-in types.
I do not know if I express precise what I want. For example: naive  
Akiyama–Tanigawa algorithm does not assume the type of output: the  
calculation can be performed at any type. Will our library work with  
all types in the same manner,  or will our library run different  
algorithms and choose which one is better in this concrete case ?

4. Do I need to make my own research, reads papers about Bernoulli  
numbers, find the best practical algorithm and then propose it to my  
mentor or my mentor will help me to find and choose algorithm ? (so:  
Can I rely on myself only ?). Until now I have found three interesting  
approach:
- use Chinese Remainder Theorem (described above)
- use Euler's formula and the zeta-function algorithm
- use completely new subquadratic algorithm (the paper was "submitted  
to publication", but it was not published in magazine until now ; it  
is online)
The first two of them all already implemented and work (I think) in  
O(n^(2+eps))  time (it is good to mention that we need \theta(n log n)  
bits to represent precise number). The third one had (asymptotically)  
better complexity, but it goes throw a lot of complicated Maths,  
p-adic numbers etc and it has been not implemented yet - so it can  
turn out that the constant hidden in Big O notation is so big, that it  
is unpractical. But who knows.
Do I need to discuss in my proposal different approach ?

5. Do I need to include in my proposal some words about applications  
to boost function:
- theoretical view: where bernoulli numbers appear
- practical view: how those functions are implemented now and how  
there will be implemented - and why they will be better
?

I am sorry, that I am writing so late, but I was not sure for a long  
time if I want to apply ; I hope I finish my proposal in time.

Kind regards,

Lukasz Marecik