[GSoC] Extending Elementary Functions for CSymPy

[Sushant Hiray]

Hi All,

I would like to work on extending the elementary functions module for CSymPy this summer
as a GSoC project. I would like to focus mainly on implementing functions on Combinatorial Number Theory.

These mainly include the functions which are currently implemented in combinatorial module of SymPy.

I hope to implement following (rough) list of things related to combinatorial number theory:

1. Functions corresponding to the factorial module in SymPy:
1. Factorial*
2. SubFactorial
3. Rising Factorial
4. Falling Factorial
5. Factorial2*
6. Multifactorial*
7. Binomial Coefficient*
2. Some Special Numbers from those implemented in numbers module in SymPy
1. Fibonacci*
2. Lucas*
3. Bernoulli
4. Catalan
   

Currently we are using gmp library in CSymPy. Some of whose functions have been used in the ntheory module for CSymPy by Thilina.

From the above list, the items marked (*) have already been implemented in the Ntheory module of GMP [1]

I haven't yet decided upon the scope of the project. If the current amount of work seems on the pessimist side,

I can include a couple of more Special Numbers implemented by SymPy and then plan my timeline accordingly.

As far as implementing Bernoulli number is concerned, I have looked into the bernmm[2] which has been authored 

solely for computing Bernoulli numbers efficiently. It is also being used in sage[5] to implement `bernoulli` function.

The dependencies of bernmm include GMP[3] (which is already being used as a dependency) and NLT[4]

We can either look into reusing the same code, in such a scenario I can find some more time to implement

some other combinatorial numbers or else we can look into implementing the algorithm[6] itself.

I have created a very rough draft of the my proposal: https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Sushant-Hiray:-Extending-Elementary-Functions-CSymPy

Currently I'm trying to figure out the scope of the project, I would then update the implementation issues and timeline accordingly.

Also as far as implementation is concerned, I'm following the route taken by Thilina by creating

functions corresponding to each Combinatorial Number.

 

An alternate implementation might be to create a class corresponding to each Combinatorial Number.

Using the latter method, we could add more functions later on

for eg:

risingfactorial(x,5) = x*(x+1)*(x+2)*(x+3)*(x+4)

In such a case, we can as well define the derivative, integral as the library improves in the later stages.

So for such cases we might as well implement an eval function inside the class which could evaluate its value

rather than just having it as a function which evaluates its value.

As far as proposal is concerned, I have followed the former method, but I would like to hear suggestions regarding this.

Hoping to hear some feedback from you guys.

[1] https://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions

[2] http://web.maths.unsw.edu.au/~davidharvey/code/bernmm/

[3] https://gmplib.org/

[4] http://www.shoup.net/ntl/

[5] http://www.sagemath.org/

[6] http://web.maths.unsw.edu.au/~davidharvey/papers/bernmm/

Regards,

Sushant Hiray

[Ondřej Čertík]

Hi Sushant,

On Sat, Mar 15, 2014 at 8:02 AM, Sushant Hiray <hirays...@gmail.com> wrote:
> Hi All,
>
> I would like to work on extending the elementary functions module for CSymPy
> this summer
> as a GSoC project. I would like to focus mainly on implementing functions on
> Combinatorial Number Theory.
> These mainly include the functions which are currently implemented in
> combinatorial module of SymPy.

Thanks for your interest!

There is a good library called Arb from Fredrik, which among others
can do Bernoulli numbers:

http://fredrikj.net/arb/
http://fredrikj.net/arb/bernoulli.html

I think it is very fast, judging from Fredrik's blogposts:

http://fredrikj.net/blog/2013/07/computing-100000-digits-of-zetazero1/

>
> I have created a very rough draft of the my proposal:
> https://github.com/sympy/sympy/wiki/GSoC-2014-Application-Sushant-Hiray:-Extending-Elementary-Functions-CSymPy
> Currently I'm trying to figure out the scope of the project, I would then
> update the implementation issues and timeline accordingly.
>
> Also as far as implementation is concerned, I'm following the route taken by
> Thilina by creating
> functions corresponding to each Combinatorial Number.

Yes, that should always be the start to create a simple function which
does the actual implementation.

>
> An alternate implementation might be to create a class corresponding to each
> Combinatorial Number.
> Using the latter method, we could add more functions later on
> for eg:
> risingfactorial(x,5) = x*(x+1)*(x+2)*(x+3)*(x+4)

Then to use these functions symbolically, one has to add classes for
them, so that they can be used
in symbolic expressions. This is what would make the proposal very
useful, so it should be part of it.

>
> In such a case, we can as well define the derivative, integral as the
> library improves in the later stages.
> So for such cases we might as well implement an eval function inside the
> class which could evaluate its value
> rather than just having it as a function which evaluates its value.

Right.

>
> As far as proposal is concerned, I have followed the former method, but I
> would like to hear suggestions regarding this.
>
> Hoping to hear some feedback from you guys.

We can discuss it more, I just wanted to write a quick feedback for now.

Ondrej

>
> [1]
> https://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions
> [2] http://web.maths.unsw.edu.au/~davidharvey/code/bernmm/
> [3] https://gmplib.org/
> [4] http://www.shoup.net/ntl/
> [5] http://www.sagemath.org/
> [6] http://web.maths.unsw.edu.au/~davidharvey/papers/bernmm/
>
>
> Regards,
> Sushant Hiray
>

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/7a391d3f-898d-462d-9e25-167f568ce5e3%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Sushant Hiray]

Hey,

Thanks for the reply Ondřej.

 

There is a good library called Arb from Fredrik, which among others
can do Bernoulli numbers:

http://fredrikj.net/arb/
http://fredrikj.net/arb/bernoulli.html

I think it is very fast, judging from Fredrik's blogposts:

http://fredrikj.net/blog/2013/07/computing-100000-digits-of-zetazero1/

I will look into this library and see if I can find any benchmarks comparing Arb with bernmm and then we can choose accordingly.

Yes, that should always be the start to create a simple function which
does the actual implementation.

Thanks for the guideline.

 

Then to use these functions symbolically, one has to add classes for
them, so that they can be used
in symbolic expressions. This is what would make the proposal very
useful, so it should be part of it.

I'll add those changes in the proposal shortly.

Also regarding our brief talk in IRC, there are quite a few applications of Combinatorial Numbers[1][2]

Apart from these could you suggest some more symbolic things which could added as a part of my proposal?

After a quick check I could find the following additions which could be merged to my existing proposal, 

adding hyperbolic functions on the similar lines of current implementation of

Trignometric Functions,  or (a bit more ambitious) adding  basic version of Taylor series expansion along the lines of SymPy.

How do these additions sound?

[1] http://www.math.hmc.edu/~benjamin/papers/fibinomial.pdf

[2] http://www.sbc.edu/sites/default/files/Honors/XiaotongJiang.July20_0.pdf

[someone]

Hi,

> There is a good library called Arb from Fredrik, which among others
> can do Bernoulli numbers:
>
> http://fredrikj.net/arb/
> http://fredrikj.net/arb/bernoulli.html
>
> I think it is very fast, judging from Fredrik's blogposts:
>
> http://fredrikj.net/blog/2013/07/computing-100000-digits-of-zetazero1/

Arb is really awesome! I definitely recommend it for validated numerics to
anyone. I used it for a few small things and it plays very well with flint too.


BTW: Maybe you want also have a look at http://www.mathemagix.org/

[Sushant Hiray]

Hi,

 

Arb is really awesome! I definitely recommend it for validated numerics to 
anyone. I used it for a few small things and it plays very well with flint too. 

Thanks, we should definitely look into this further.

Considering that even in the thread of Thilina's proposal, it is being recommended to use dependencies

in and around flint.

Also after discussing with Ondrej, I've decided to shift the focus of my proposal from 

implementing just fast numeric methods to symbolically implementing some special functions

and then using the fast numeric methods in their evaluation.

So i have updated my proposal accordingly. 

I would like to get your views regarding the current proposal.

Also a more concrete advice on the scope of the project, if it is way too pessimistic/optimistic

would be highly appreciated.

Looking forward to hear from you.

Regards,

Sushant Hiray

[Ondřej Čertík]

On Mon, Mar 17, 2014 at 8:37 AM, Sushant Hiray <hirays...@gmail.com> wrote:
> Hi,
>
>>
>> Arb is really awesome! I definitely recommend it for validated numerics to
>> anyone. I used it for a few small things and it plays very well with flint
>> too.
>
>
> Thanks, we should definitely look into this further.
> Considering that even in the thread of Thilina's proposal, it is being
> recommended to use dependencies
> in and around flint.
>
> Also after discussing with Ondrej, I've decided to shift the focus of my
> proposal from
> implementing just fast numeric methods to symbolically implementing some
> special functions
> and then using the fast numeric methods in their evaluation.
>
> So i have updated my proposal accordingly.
> I would like to get your views regarding the current proposal.
> Also a more concrete advice on the scope of the project, if it is way too
> pessimistic/optimistic
> would be highly appreciated.

Looks much better. As to complex numbers, see also:

https://github.com/certik/csympy/issues/47

as to trig functions, the simplification of things like sin(3*pi/2) is
nontrivial since you have to code this for all of the functions.
There is a way to code this up once for a general trig function and
then all other functions work automatically, see the "trig" branch
here:

https://github.com/certik/sympy/blob/trig/t.py

See the tests at the end for things that must work. I think that's the
easiest implementation of trig functions and it should be pretty fast
too.

You should also put there a schedule of what things you want to get
done each week.

Ondrej

[Sushant Hiray]

Hi,

Looks much better.

Thank you.

As to complex numbers, see also:

https://github.com/certik/csympy/issues/47

I've looked into the issue, I mentioned it there as well that
we should probably go ahead with extending the numbers module
for the complex module.
 

as to trig functions, the simplification of things like sin(3*pi/2) is
nontrivial since you have to code this for all of the functions.
There is a way to code this up once for a general trig function and
then all other functions work automatically, see the "trig" branch
here:

https://github.com/certik/sympy/blob/trig/t.py

I had looked into the implementation of lookup tables
when we had discussed about this on gitter. 

Considering there are a lot of corner cases to be handled
and ensuring the module passes the unit tests, a significant
time needs to be spent on enhancing and testing the current module
and then further extending it to inverses and hyperbolic modules.

Also adding python wrappers should be a decent plus.

You should also put there a schedule of what things you want to get
done each week.

I wanted to have a review first on how the proposal looks. Now
that it is decent enough, I'll add a timeline and we can discuss further
upon that.

Also I looked into the current SymPy Trignometric Module
and added a small patch to implement Taylor Term for sec.

It would be great if you could look into it or redirect me to someone
who worked on those lines recently. There are quite a few things
which are still marked TODO in that module. I'll try to fix more
once I'm done with the proposal.

Regards,
Sushant Hiray

[Ondřej Čertík]

>> as to trig functions, the simplification of things like sin(3*pi/2) is
>> nontrivial since you have to code this for all of the functions.
>> There is a way to code this up once for a general trig function and
>> then all other functions work automatically, see the "trig" branch
>> here:
>>
>> https://github.com/certik/sympy/blob/trig/t.py
>>
>
> I had looked into the implementation of lookup tables
> when we had discussed about this on gitter.
>
> Considering there are a lot of corner cases to be handled
> and ensuring the module passes the unit tests, a significant
> time needs to be spent on enhancing and testing the current module
> and then further extending it to inverses and hyperbolic modules.

I would simply translate the `t.py` implementation to C++ in CSymPy.
I don't think it's hard. Just implement the "TrigFunction" class which
implements the gist of the algorithm and then implement the actual
Sin, Cos, Tan classes as in `t.py`.

There will probably be some corner cases, so it's good to spend some time
on this and get this right.

We'll also probably want to extend it to functions like sec(), but getting
sin/cos/tan right is more important.

>
> Also adding python wrappers should be a decent plus.
>
>> You should also put there a schedule of what things you want to get
>> done each week.
>
>
> I wanted to have a review first on how the proposal looks. Now
> that it is decent enough, I'll add a timeline and we can discuss further
> upon that.
>
> Also I looked into the current SymPy Trignometric Module
> and added a small patch to implement Taylor Term for sec.

Thanks! I left some minor comments on the PR.

>
> It would be great if you could look into it or redirect me to someone
> who worked on those lines recently. There are quite a few things
> which are still marked TODO in that module. I'll try to fix more
> once I'm done with the proposal.

You can use "git blame" to figure out who wrote what. I only remember that long
time ago, Luke and I wanted to reimplement the trig stuff along the
lines of t.py above,
which should simplify things a lot, but didn't manage to finish it up.

Ondrej

[Sushant Hiray]

Hi,

I would simply translate the `t.py` implementation to C++ in CSymPy.
I don't think it's hard. Just implement the "TrigFunction" class which
implements the gist of the algorithm and then implement the actual
Sin, Cos, Tan classes as in `t.py`.

There will probably be some corner cases, so it's good to spend some time
on this and get this right.

True. I went through the code and I guess the code is not that hard.

So I shaped my timeline accordingly.
 

We'll also probably want to extend it to functions like sec(), but getting
sin/cos/tan right is more important.

Yeah, sure! That is the aim. Well we could atleast use them as the reciprocal
of `sin`,`cos`,`tan` just for the sake of completeness.
 

>
> Also adding python wrappers should be a decent plus.
>

I do not have any experience regarding this. Though surely we can try this
out. I did give it a place in the timeline :)
 

>> You should also put there a schedule of what things you want to get
>> done each week.
>

I have written a rough timeline. There can still be some more changes before
it gets finalized. Do give me some inputs regarding how it looks.

Too optimistic maybe?
 

Thanks! I left some minor comments on the PR.

Thanks about that! I've updated according to Sergey's suggestions as well.

I guess there was some issue with Travis builds. I saw it on gitter. So I suspect

it'll take some time before the tests are scheduled back on track again.

Anyways looking forward to the inputs on the timeline.

If I manage some time, I'll push in taylor term for cosec.

Rest have been added.

Regards,

Sushant Hiray

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/V1zGL4YM_kE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVA%3DmxkB5xp-Q%3D-baF3eAcD-1YrNZ7P1tDf%2B0H7uYCinJQ%40mail.gmail.com.

[Ondřej Čertík]

On Tue, Mar 18, 2014 at 5:09 PM, Sushant Hiray <hirays...@gmail.com> wrote:
> Hi,
>
>>
>> I would simply translate the `t.py` implementation to C++ in CSymPy.
>> I don't think it's hard. Just implement the "TrigFunction" class which
>> implements the gist of the algorithm and then implement the actual
>> Sin, Cos, Tan classes as in `t.py`.
>>
>> There will probably be some corner cases, so it's good to spend some time
>> on this and get this right.
>>
>
> True. I went through the code and I guess the code is not that hard.
> So I shaped my timeline accordingly.
>
>>
>> We'll also probably want to extend it to functions like sec(), but getting
>> sin/cos/tan right is more important.
>>
>
> Yeah, sure! That is the aim. Well we could atleast use them as the
> reciprocal
> of `sin`,`cos`,`tan` just for the sake of completeness.
>
>>
>> >
>> > Also adding python wrappers should be a decent plus.
>> >
>
>
> I do not have any experience regarding this. Though surely we can try this
> out. I did give it a place in the timeline :)
>
>>
>> >> You should also put there a schedule of what things you want to get
>> >> done each week.
>> >
>
>
> I have written a rough timeline. There can still be some more changes before
> it gets finalized. Do give me some inputs regarding how it looks.
> Too optimistic maybe?

I looked at the timeline, I don't think it's too optimistic. Obviously things
go a little slower in C++ than in Python, but it's really not that difficult.

I think the trig stuff can be done sooner, I don't expect any major issues.
The Complex stuff might trigger some issues that we might to tackle, we'll see.

Otherwise looks good to me.

Ondrej

>
>>
>>
>> Thanks! I left some minor comments on the PR.
>>
> Thanks about that! I've updated according to Sergey's suggestions as well.
> I guess there was some issue with Travis builds. I saw it on gitter. So I
> suspect
> it'll take some time before the tests are scheduled back on track again.
>
> Anyways looking forward to the inputs on the timeline.
>
> If I manage some time, I'll push in taylor term for cosec.
> Rest have been added.
>
> Regards,
> Sushant Hiray
>>
>> --
>> You received this message because you are subscribed to a topic in the
>> Google Groups "sympy" group.
>> To unsubscribe from this topic, visit
>> https://groups.google.com/d/topic/sympy/V1zGL4YM_kE/unsubscribe.
>> To unsubscribe from this group and all its topics, send an email to
>> sympy+un...@googlegroups.com.
>>
>> To post to this group, send email to sy...@googlegroups.com.
>> Visit this group at http://groups.google.com/group/sympy.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/sympy/CADDwiVA%3DmxkB5xp-Q%3D-baF3eAcD-1YrNZ7P1tDf%2B0H7uYCinJQ%40mail.gmail.com.
>>
>> For more options, visit https://groups.google.com/d/optout.
>
>
> --

> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/CAN2RUgrfCOwdGwUqQbOsGhAFCDY1cXCM%2BaHjusQKJrJ-5p%3Ddig%40mail.gmail.com.

[Sushant Hiray]

Hi,

I looked at the timeline, I don't think it's too optimistic. Obviously things
go a little slower in C++ than in Python, but it's really not that difficult.

I think the trig stuff can be done sooner, I don't expect any major issues.

Thanks.

I guess I'll keep it this way. In case we do finish it sooner
(which I guess we will) we can start looking into the python wrapper in parallel.
I had kept it during 5th week, but I guess it makes sense if we do it
in the 3rd-4th week as we keep on adding on more functionality.

It(Python Wrapper) can extend till 5th week as we wouldn't be focusing entirely on that.
 

The Complex stuff might trigger some issues that we might to tackle, we'll see.

If we do face some issues with Complex, I guess we have a week's buffer at the end
which can very well be put to use for some bug fixes.
 

Otherwise looks good to me.

Thanks,
Sushant Hiray

[Ondřej Čertík]

On Tue, Mar 18, 2014 at 6:14 PM, Sushant Hiray <hirays...@gmail.com> wrote:
> Hi,
>
>
>> I looked at the timeline, I don't think it's too optimistic. Obviously
>> things
>> go a little slower in C++ than in Python, but it's really not that
>> difficult.
>>
>> I think the trig stuff can be done sooner, I don't expect any major
>> issues.
>
>
> Thanks.
>
> I guess I'll keep it this way. In case we do finish it sooner
> (which I guess we will) we can start looking into the python wrapper in
> parallel.
> I had kept it during 5th week, but I guess it makes sense if we do it
> in the 3rd-4th week as we keep on adding on more functionality.
>
> It(Python Wrapper) can extend till 5th week as we wouldn't be focusing
> entirely on that.

I think the Python wrapper is a matter of few hours. I'll be happy to
do that myself.

>
>>
>> The Complex stuff might trigger some issues that we might to tackle, we'll
>> see.
>>
>
> If we do face some issues with Complex, I guess we have a week's buffer at
> the end
> which can very well be put to use for some bug fixes.

There is plenty things to do, so if you finish sooner (hopefully),
then we can work on other things.

Ondrej

[Sushant Hiray]

Hi,

I think the Python wrapper is a matter of few hours. I'll be happy to
do that myself.

Well if that is the case, then do you suggest I add some more stuff in the proposal?

Or is it better to keep a buffer just in case?

Regards,

Sushant Hiray

>
>>
>> The Complex stuff might trigger some issues that we might to tackle, we'll
>> see.
>>
>
> If we do face some issues with Complex, I guess we have a week's buffer at
> the end
> which can very well be put to use for some bug fixes.

There is plenty things to do, so if you finish sooner (hopefully),
then we can work on other things.

Ondrej

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/V1zGL4YM_kE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVDtB8Eigri1-2J%3DyrDMw0zRjee_2yYjawEP%2B7ZFtNTsjg%40mail.gmail.com.

[Ondřej Čertík]

On Wed, Mar 19, 2014 at 2:18 AM, Sushant Hiray <hirays...@gmail.com> wrote:

Hi,

I think the Python wrapper is a matter of few hours. I'll be happy to
do that myself.

Well if that is the case, then do you suggest I add some more stuff in the proposal?

Or is it better to keep a buffer just in case?

What you can do is add more special functions, like Bessel functions, Spherical Harmonics and so on. Symbolic class + numerical evaluation, and add it at the end of the proposal, if there is time.

Ondrej

[Sushant Hiray]

Hi,

Thanks for the suggestion Ondrej.
I've updated the proposal accordingly.
Could you have a look over it once here and see if all is well.

Thanks,
Sushant Hiray