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