Definition of multifactorial #5415

[prateek sharma]

Hi,
I am looking for multifactorial function in the source code but unable to.Help me out...

[Dima Pasechnik]

On Wednesday, 28 October 2015 02:11:59 UTC-7, prateek sharma wrote:

Hi,
I am looking for multifactorial function in the source code but unable to.Help me out...

sage: a=42

sage: a.multifactorial??

 

[prateek sharma]

It should be like
a=42
k=3
sage: a.multifactorial(k)

[Dima Pasechnik]

On Friday, 30 October 2015 05:38:56 UTC, prateek sharma wrote:

It should be like
a=42
k=3
sage: a.multifactorial(k)

I told you to display the source code for this function, as this is what you asked, no?

 

[John H Palmieri]

On Friday, October 30, 2015 at 8:50:42 AM UTC-7, Dima Pasechnik wrote:

On Friday, 30 October 2015 05:38:56 UTC, prateek sharma wrote:

It should be like
a=42
k=3
sage: a.multifactorial(k)

I told you to display the source code for this function, as this is what you asked, no?

You can also run

sage: search_def('multifactorial')
rings/integer.pyx:3908:    def multifactorial(self, int k):

which tells you that the function is defined starting on line 3908 of rings/integer.pyx (or, relative to the top-level Sage directory, src/sage/rings/integer.pyx).

--
John

[prateek sharma]

    def multifactorial(self, int k):
        r"""
        Computes the k-th factorial `n!^{(k)}` of self. For k=1
        this is the standard factorial, and for k greater than one it is
        the product of every k-th terms down from self to k. The recursive
        definition is used to extend this function to the negative
        integers.

        EXAMPLES::

            sage: 5.multifactorial(1)
            120
            sage: 5.multifactorial(2)
            15
            sage: 23.multifactorial(2)
            316234143225
            sage: prod([1..23, step=2])
            316234143225
            sage: (-29).multifactorial(7)
            1/2640
        """
        if k <= 0:
            raise ValueError, "multifactorial only defined for positive values of k"

        if not mpz_fits_sint_p(self.value):
            raise ValueError, "multifactorial not implemented for n >= 2^32.\nThis is probably OK, since the answer would have billions of digits."

        cdef int n = mpz_get_si(self.value)

        # base case
        if 0 < n < k:
            return one

        # easy to calculate
        elif n % k == 0:
            factorial = Integer(n/k).factorial()
            if k == 2:
                return factorial << (n/k)
            else:
                return factorial * Integer(k)**(n/k)

        # negative base case
        elif -k < n < 0:
            return one / (self+k)

        # reflection case
        elif n < -k:
            if (n/k) % 2:
                sign = -one
            else:
                sign = one
            return sign / Integer(-k-n).multifactorial(k)

        # compute the actual product, optimizing the number of large
        # multiplications
        cdef int i,j

        # we need (at most) log_2(#factors) concurrent sub-products
        cdef int prod_count = <int>ceil_c(log_c(n/k+1)/log_c(2))
        cdef mpz_t* sub_prods = <mpz_t*>check_allocarray(prod_count, sizeof(mpz_t))
        for i from 0 <= i < prod_count:
            mpz_init(sub_prods[i])

        sig_on()

        cdef residue = n % k
        cdef int tip = 0
        for i from 1 <= i <= n//k:
            mpz_set_ui(sub_prods[tip], k*i + residue)
            # for the i-th terms we use the bits of i to calculate how many
            # times we need to multiply "up" the stack of sub-products
            for j from 0 <= j < 32:
                if i & (1 << j):
                    break
                tip -= 1
                mpz_mul(sub_prods[tip], sub_prods[tip], sub_prods[tip+1])
            tip += 1
        cdef int last = tip-1
        for tip from last > tip >= 0:
            mpz_mul(sub_prods[tip], sub_prods[tip], sub_prods[tip+1])

        sig_off()

        cdef Integer z = PY_NEW(Integer)
        mpz_swap(z.value, sub_prods[0])

        for i from 0 <= i < prod_count:
            mpz_clear(sub_prods[i])
        sage_free(sub_prods)

        return z

[prateek sharma]

From the given code for
sage:5.multifactorial(3)
5
But the result should be 10.
I changed th recurssion code but its still not working properly.
Can anybody help me out?

On Wednesday, October 28, 2015 at 2:41:59 PM UTC+5:30, prateek sharma wrote:

[Nils Bruin]

On Saturday, October 31, 2015 at 8:31:59 AM UTC-7, prateek sharma wrote:

From the given code for
sage:5.multifactorial(3)
5
But the result should be 10.

There has been work on this:

http://trac.sagemath.org/ticket/5415

but it looks like momentum was lost. There seems to be some disagreement on what "multifactorial" should be. The description says:

For k=1 this is the standard factorial, and for k greater than one it is the product of every k-th terms down from self to k.

which for n=5 and k=3 would indeed be the product of just five (since the next term would be 5-3=2, which is smaller than 3)

so the output you get does seem to be in accordance with the definition that sage's documentation uses. It may well be (and that is what the ticket indicates too) that sage's documentation does not agree with common mathematical convention. If you are interested in helping to get this issue resolved, the appropriate place to start would be the linked ticket.

[prateek sharma]

So what should be the result of 5.multifactorial(3)... 5 or 10?

On Wednesday, October 28, 2015 at 2:41:59 PM UTC+5:30, prateek sharma wrote:

[prateek sharma]

I have submitted a patch to the issue  #5415.
Please review.

On Wednesday, October 28, 2015 at 2:41:59 PM UTC+5:30, prateek sharma wrote:

[Nils Bruin]

On Sunday, November 1, 2015 at 7:22:37 AM UTC-8, prateek sharma wrote:

I have submitted a patch to the issue  #5415.
Please review.

Nothing appears on the ticket. Did you follow the instructions in http://doc.sagemath.org/html/en/developer/ to set up a trac account and submit your changes?

[prateek sharma]

It is showing in pull requests.Kindly please refer here.
https://github.com/sagemath/sage/pull/52

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

[prateek sharma]

https://github.com/prateekcs14/sage/commit/2cb944378c97bdad76a053e37d579d492f68d44c#commitcomment-14180664

On Wednesday, October 28, 2015 at 2:41:59 PM UTC+5:30, prateek sharma wrote:

[prateek sharma]

Please review.

On Wednesday, October 28, 2015 at 2:41:59 PM UTC+5:30, prateek sharma wrote:

[prateek sharma]

Please review the changes made.
https://github.com/prateekcs14/sage/commit/1d70630b6f878752fa342150d1e4c2e6c4777c4a

[Nathann Cohen]

> Please review the changes made.
> https://github.com/prateekcs14/sage/commit/1d70630b6f878752fa342150d1e4c2e6c4777c4a

You may want to read this: http://doc.sagemath.org/html/en/developer/index.html

Nathann

[Peter Luschny]

Nils Bruin> "It may well be (and that is what the ticket indicates 

too) that sage's documentation does not agree with common 
mathematical convention."

The standard common mathematical use of various types of 
multifactorials is well documented in the OEIS.

But what also is well documented in the OEIS is that the notation
for multifactorials can be very confusing and that the namings
used are not standardized and are even more confusing.

But at bottom things are of course very simple: What is needed
is just a common basic definition from which all special cases are
derived. How this could be done is outlined in an old post of mine
on the OEIS-Wiki [1]. I can well imagine making this a general
multifactorial function in SageMath.

Cheers Peter

[1] http://oeis.org/wiki/User:Peter_Luschny/Multifactorials

[prateek sharma]

Can you please summarize me what I basically need to do?

[Nils Bruin]

On Tuesday, December 8, 2015 at 5:56:36 AM UTC-8, prateek sharma wrote:

Can you please summarize me what I basically need to do?

Read this:
 

http://doc.sagemath.org/html/en/developer/

and follow the workflow there to push a branch incorporating your changes to trac.sagemath.org.
The sage development workflow doesn't currently involve "pull requests" on github. Instead, you should make sure there's a branch on trac.sagemath.org and that that branch is registered on the relevant ticket. Then a potential reviewer knows where to find the code to be reviewed.

The "git-trac" command (documented there) helps performing a lot of the required steps. If you're more comfortable with using git directly then "git the hard way" might be useful doc.

Make sure you read "Sage Development Process" and "Sage Trac and tickets".

[prateek sharma]

Can you tell me how can I create a branch .When I do git-trac-checkout 5415
It says "Newly created local branch: t/5415/problems_with_multifactorial_"
I have made my changes on git.How can I commit those changes on trac.
Please help.

[John Cremona]

On 9 December 2015 at 13:13, prateek sharma

<prateeksh...@gmail.com> wrote:
> Can you tell me how can I create a branch .When I do git-trac-checkout 5415
> It says "Newly created local branch: t/5415/problems_with_multifactorial_"
> I have made my changes on git.How can I commit those changes on trac.
> Please help.

This is all explained in great detail in the developers guide -- have
you read that? You can ask again here if that is not clear in any
way.

>
>
> On Tuesday, December 8, 2015 at 10:14:09 PM UTC+5:30, Nils Bruin wrote:
>>
>> On Tuesday, December 8, 2015 at 5:56:36 AM UTC-8, prateek sharma wrote:
>>>
>>> Can you please summarize me what I basically need to do?
>>>
>>
>> Read this:
>>
>> http://doc.sagemath.org/html/en/developer/
>>
>> and follow the workflow there to push a branch incorporating your changes
>> to trac.sagemath.org.
>> The sage development workflow doesn't currently involve "pull requests" on
>> github. Instead, you should make sure there's a branch on trac.sagemath.org
>> and that that branch is registered on the relevant ticket. Then a potential
>> reviewer knows where to find the code to be reviewed.
>>
>> The "git-trac" command (documented there) helps performing a lot of the
>> required steps. If you're more comfortable with using git directly then "git
>> the hard way" might be useful doc.
>>
>> Make sure you read "Sage Development Process" and "Sage Trac and tickets".
>>

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

[Nils Bruin]

On Wednesday, December 9, 2015 at 5:13:58 AM UTC-8, prateek sharma wrote:

Can you tell me how can I create a branch .When I do git-trac-checkout 5415
It says "Newly created local branch: t/5415/problems_with_multifactorial_"

Doesn't the system just tell you that you have now succeeded in creating a (local) branch?

 

I have made my changes on git.

Does that mean that you have followed the instructions http://doc.sagemath.org/html/en/developer/git_trac.html#making-changes ? or do you mean "my changes are sitting on github"? The documentation will tell you how to commit changes to your local branch
 

How can I commit those changes on trac.

Do you mean "How do I push those changes to a remote branch on trac attached to the ticket?", That's described in the next section, http://doc.sagemath.org/html/en/developer/git_trac.html#uploading-changes-to-trac
 

[prateek sharma]

On Wednesday, December 9, 2015 at 10:55:18 PM UTC+5:30, Nils Bruin wrote:

On Wednesday, December 9, 2015 at 5:13:58 AM UTC-8, prateek sharma wrote:

Can you tell me how can I create a branch .When I do git-trac-checkout 5415
It says "Newly created local branch: t/5415/problems_with_multifactorial_"

 

Doesn't the system just tell you that you have now succeeded in creating a (local) branch?

No . The system just says "Newly created local branch..." and processing keeps on going.
I have to forcefully stop the programme.

[Nils Bruin]

On Wednesday, December 9, 2015 at 10:21:17 AM UTC-8, prateek sharma wrote:

No . The system just says "Newly created local branch..." and processing keeps on going.

I have to forcefully stop the programme.

It works for me (it does take some time to finish, however. I don't know what it's doing. I'd imagine that any of: speed of local disk access, processor speed, internet speed might affect how long this should take. I'd imagine that if you are not up-to-date on the local develop, it might have quite a bit of downloading to do from trac (I assume that pulling a ticket with a non-existant branch will just pull "develop" on trac.)

I've pushed the branch there now. Perhaps that helps you along? Otherwise, you could try setting up a sage branch from scratch, following the docs. Perhaps that gets things working for you.

[Travis Scrimshaw]

On Wednesday, December 9, 2015 at 4:45:35 PM UTC-6, Nils Bruin wrote:

On Wednesday, December 9, 2015 at 10:21:17 AM UTC-8, prateek sharma wrote:

No . The system just says "Newly created local branch..." and processing keeps on going.

I have to forcefully stop the programme.

It works for me (it does take some time to finish, however. I don't know what it's doing. I'd imagine that any of: speed of local disk access, processor speed, internet speed might affect how long this should take. I'd imagine that if you are not up-to-date on the local develop, it might have quite a bit of downloading to do from trac (I assume that pulling a ticket with a non-existant branch will just pull "develop" on trac.)

Doing it directly via git should work really quickly since git is designed to be lightweight. See http://doc.sagemath.org/html/en/developer/manual_git.html for more.

Best,
Travis

[prateek sharma]

I tried with git but it is giving me error saying permission denied.
I tried with git trac.It is also saying permission denied.
I am unable to figure it out.Please help...

[Volker Braun]

You need to associate your SSH public key with trac:

http://doc.sagemath.org/html/en/developer/trac.html#manually-linking-your-public-key-to-your-trac-account

[prateek sharma]

Thanks..It works.

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

[prateek sharma]

I had pushed my branch on trac but I am unable to see any commit on trac.Can anybody tell me why?

[prateek sharma]

Also whenever I give a pull request many of the files , actually most of the files from src folder get deleted automatically.It has have happened 4 times.Can anybody tell me why?

[Nils Bruin]

On Thursday, December 10, 2015 at 2:25:45 PM UTC-8, prateek sharma wrote:

I had pushed my branch on trac but I am unable to see any commit on trac.Can anybody tell me why?

Your branch shows up red. That means that an automatic merge of your branch with the reference branch (the "develop" branch on trac) is not succeeding. That probably means your branch is based on a branch that is too far removed from "develop". You should rebase/merge your branch with the current develop branch (resolving conflicts properly) and push that.

Second, you can click on "Commits" which gives you the history of the branch. The latest commit it shows there is

Do not allow creation of ticket titled "help"

 from 9 days ago. So it doesn't look like your work is committed in the branch that you pushed in the first place.

I would:

 - pull trac's develop (that doesn't have your change yet)
 - make a new branch of that
 - Change the one file that has your little change (perhaps just copy that file into the tree)
 - confirm that the "diff" at this point is exactly what you want
 - commit the change
 - push *that* branch to the trac ticket.

That should give you a fairly clean commit easily, and would be easier than trying to diagnose the mess you're in now.
relevant xkcd: http://xkcd.com/1597/

[prateek sharma]

Thanks .It worked.

Please review the changes made.

http://trac.sagemath.org/ticket/5415

[prateek sharma]

How can I change doctest to check my changes made.?

[Nils Bruin]

On Saturday, December 12, 2015 at 10:30:29 PM UTC-8, prateek sharma wrote:

How can I change doctest to check my changes made.?

Continue reading the developer guide.

 http://doc.sagemath.org/html/en/developer/coding_basics.html

in particular

 http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings
 http://doc.sagemath.org/html/en/developer/coding_basics.html#running-automated-tests

(the guide could be improved a bit: it could mention that the docstring occurs right in the source file, just below the "def ... :" line, as is usual in python. It could also mention something about the formatting of "EXAMPLES:" section, specifically when to use "::" and when not, but in your case you can just take your cues from the string that's already there)