[sage-devel] Re: computing the number of partitions of an integer
On Thu, 2007-07-26 at 13:10 -0700, Bill Hart wrote:
Perhaps if one had a fast way of evaluating the Dedekind sum, one
might have a chance.
Bill.
I think this gives a faster way to compute it:
Write the sum as
s(h,k) = sum_{j=1}^{k-1} j/k [hj/k - floor(hj/k) - 1/2]
(This isn't strictly correct in general, but in our case hj/k will never
be an integer, so we are ok.)
Then if we separate this into three different sums and use some simple
summation formulas, we get
s(h,k) = h(k - 1)(2k - 1)/(6k) - (k-1)/4 -
(1/k) sum_{j=1}^{k-1} j*floor(hj/k).
(To compute the floor in the inner sum, you can just use integer
division.)
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: accessing GAP's small groups database from the notebook
None of these problems arise on an intel macbook running sage 2.7. I also tested it using gap_console() and the example worked in that mode too. Could you please try gap_reset_workspace() and then restart SAGE and see if the examples start? +++ On 7/26/07, Dan Christensen [EMAIL PROTECTED] wrote: I'm having trouble accessing GAP's small groups database from the notebook. I'm using the binary install of 2.7.1 on 32-bit Debian. I have installed database_gap-4.4.9 and gap_packages-4.4.9_2. If I do sage -gap, then inside the gap process, I can do: gap NumberSmallGroups(2^3); 5 But if I use gap within a notebook worksheet, or if I start sage with sage, the small groups database isn't loaded: [EMAIL PROTECTED]:~$ sage -- | SAGE Version 2.7.1, Release Date: 2007-07-24 | | Type notebook() for the GUI, and license() for information.| -- sage: %gap -- Switching to Gap -- '' gap: NumberSmallGroups(2^3); --- type 'exceptions.RuntimeError' Traceback (most recent call last) [...stuff omitted...] type 'exceptions.RuntimeError': Gap produced error output Error, the Small Groups library is required but not installed executing NumberSmallGroups(2^3);; Dan --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
Here we go. Apparently g(h,q) = q*s(h,q) where s(h,q) is a dedekind
sum.
Then for h q if r_0, r_1, ..., r_{n+1} are the remainders occurring
in the Euclidean algorithm when computing gcd(h,q) (of which there
should be about log q) then:
s(h,q) = 1/12 * sum_{i=1}^{n+1}((-1)^(i+1) (r_i^2 + r_{i-1}^2 + 1) /
(r_i * r_{i-1}) - ((-1)^n +1)/8)
This, with the other ideas I gave above, will definitely let us beat
Mathematica convincingly, as a simple back of the envelope calculation
shows. It will have the added benefit of allowing us to beat Magma at
something.
Bill.
On 27 Jul, 00:12, Bill Hart [EMAIL PROTECTED] wrote:
OK, apparently the Dedekind sums should be done using an algorithm due
to Apostol. I haven't tracked it down yet, but this is clearly what we
need.
Bill.
On 26 Jul, 23:37, Bill Hart [EMAIL PROTECTED] wrote:
On 26 Jul, 23:18, Jonathan Bober [EMAIL PROTECTED] wrote:
s(h,k) = h(k - 1)(2k - 1)/(6k) - (k-1)/4 -
(1/k) sum_{j=1}^{k-1} j*floor(hj/k).
(To compute the floor in the inner sum, you can just use integer
division.)
Yes, this will be faster. Of course integer division is not faster
than floating point division, but since we are doing a sum from j = 1
to k-1 we only need to know when floor(hj/k) increases by 1. This is
simply a matter of adding h each iteration and seeing if we have gone
over k (subtracting k if we do). If so, floor(hj/k) has increased by 1
and so on.
This gets the inner computation down to about 8 cycles or so on
average. Not enough to beat Mathematica though, unless I made a
mistake in my back of the envelope computation somewhere.
Bill.
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
On 26 Jul, 23:18, Jonathan Bober [EMAIL PROTECTED] wrote:
s(h,k) = h(k - 1)(2k - 1)/(6k) - (k-1)/4 -
(1/k) sum_{j=1}^{k-1} j*floor(hj/k).
(To compute the floor in the inner sum, you can just use integer
division.)
Yes, this will be faster. Of course integer division is not faster
than floating point division, but since we are doing a sum from j = 1
to k-1 we only need to know when floor(hj/k) increases by 1. This is
simply a matter of adding h each iteration and seeing if we have gone
over k (subtracting k if we do). If so, floor(hj/k) has increased by 1
and so on.
This gets the inner computation down to about 8 cycles or so on
average. Not enough to beat Mathematica though, unless I made a
mistake in my back of the envelope computation somewhere.
Bill.
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
There are two tricks I can see that are required to make this faster. Firstly notice that L(n,q)*Psi(n,q) is relatively small once q gets beyond a certain point. Thus L(n,q)*Psi(n,q) can be computed using ordinary double precision for q greater than some very small limit (depending on n). If one knew how fast this series converges (which must have been worked out somewhere), one could even progressively reduce the precision as the computation went, for even greater speed. For example the following Pari script should compute all but the last 150 or so digits of P(10^9) quite quickly: Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b); (sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c)) L(n, q) = if(q==1,1,sum(h=1,q-1,if(gcd(h,q)1,0,cos((g(h,q)-2*h*n)*Pi/ q g(h, q) = if(q3,0,sum(k=1,q-1,k*(frac(h*k/q)-1/2))) n=14 \p36000 a1 = L(n,1)*Psi(n,1); \p18000 a2 = L(n,2)*Psi(n,2); \p12000 a3 = L(n,3)*Psi(n,3); \p9000 a4 = L(n,4)*Psi(n,4); \p8000 a5 = L(n,5)*Psi(n,5); \p6000 a6 = L(n,6)*Psi(n,6); \p6000 a7 = L(n,7)*Psi(n,7); \p5000 a8 = L(n,8)*Psi(n,8); \p4000 a9 = sum(y=9,14,L(n,y)*Psi(n,y)); \p3000 a10 = sum(y=15,17,L(n,y)*Psi(n,y)); \p2000 a11 = sum(y=18,34,L(n,y)*Psi(n,y)); \p1000 a12 = sum(y=35,300,L(n,y)*Psi(n,y)); round(a1+a2+a3+a4+a5+a6+a7+a8+a9+a10+a11+a12) The second trick is that computing gcd(h,q) is costly. One should factor q and then sieve for all h not coprime to q in short cache friendly segments, especially for very large n. But I don't believe Mathematica uses this Rademacher series thing anyway. If you look at the inner most loop, that computation involving frac must take at least 80 cycles in double precision. But for n = 10^9, that expression must get evaluated about 2*10^11 times. That's about 1.6*10^13 cycles, which on sage.math has go to take about 1s. Even if I'm out by a factor of 10 with the cycles, mathematica clearly doesn't do this. Perhaps if one had a fast way of evaluating the Dedekind sum, one might have a chance. Bill. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
William Stein [EMAIL PROTECTED] writes: QUESTIONS: Why is Mathematica about 10 times faster than PARI at this? What are the best ways to compute the number of partitions of n? Is it a calculation involving fast arithmetic with dense polynomials of large degree, which would be best done using the upcoming FLINT library or NTL? Please correct me if I'm crazy, but isn't there an asymptotic formula due to Hardy and Rademacher that can evaluate $P(n)$ to a very high accuracy very quickly? Surely both of these packages implement such a convergent series approach, and it is possible that SAGE has faster real arithmetic and could do this faster. Again, I may be completely incorrect -- please let me know. Nick --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
The fastest way I know of to compute the number of integer partitions is to use the Hardy-Ramanujan-Rademacher formula ( see Rademacher series on http://en.wikipedia.org/wiki/Integer_partition ), and I'm pretty sure this is what PARI uses. From modules/part.c: * This program is basically the implementation of the script * * Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b); * (sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c)) * L(n, q) = if(q==1,1,sum(h=1,q-1,if(gcd(h,q)1,0,cos((g(h,q)-2*h*n)*Pi/q * g(h, q) = if(q3,0,sum(k=1,q-1,k*(frac(h*k/q)-1/2))) * part(n) = round(sum(q=1,5 + 0.24*sqrt(n),L(n,q)*Psi(n,q))) I'm not sure where the bottleneck in PARI is since I can't imagine Mathematica uses a different method to compute the number of partitions. --Mike P.S. I'm going to push hard this weekend to get the combinatorics stuff I've been working on to you. On 7/26/07, William Stein [EMAIL PROTECTED] wrote: On 7/25/07, Timothy Clemans [EMAIL PROTECTED] wrote: How do you in general find out how say Magma or Mathematica does something? Short answer: it is often virtually impossible -- that's one of the main reasons for the existence of SAGE. Read this page for the official Mathematica stance on this sort of question: http://reference.wolfram.com/mathematica/tutorial/WhyYouDoNotUsuallyNeedToKnowAboutInternals.html -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
Alternatively you could just use the implementation here:
http://www.ark.in-berlin.de/part.c
which seems to only rely on mpfr and GMP. However, since the Pari
version was based on it, I suspect it may also need correction.
He does seem to adjust the precision as he goes, but I've no idea how
far above or below the required precision this is. However there is no
need to use a precision of 55 from a certain point on. That probably
forces it to use two doubles instead of one in the floating point
computations, which I think would be unnecesary. You can look on
mathworld for how well the Rademacher series converges.
It would probably be quicker to do a fresh implementation from scratch
given the application in mind. The code there may not be GPL'd also.
To check it works, one should at least look at the congruences modulo
5, 7, 11 and 13. The author of the mpfr version does seem to check
them mod 11 but for very small n and only for a very few values of n.
If the gcds prove to be a bottleneck, I have some code that is roughly
twice as fast as GMP for computing these. Certainly the code in the
mpfr version is suboptimal and needs some serious optimisation when
the terms in the dedekind sum fit into a single limb, which on a 64
bit machine is probably always, when n is of a reasonable size.
Another suggestion is that for sufficiently small values of h and or
k, it may be quicker to compute the dedekind sum directly rather than
use the gcd formula.
A lookup table would also be useful for the tail end of the gcd/
dedekind sum computation.
I'd be shocked if the computation for n = 10^9 couldn't be done in
under 10s on sage.math.
Bill.
On 27 Jul, 00:39, Bill Hart [EMAIL PROTECTED] wrote:
Here we go. Apparently g(h,q) = q*s(h,q) where s(h,q) is a dedekind
sum.
Then for h q if r_0, r_1, ..., r_{n+1} are the remainders occurring
in the Euclidean algorithm when computing gcd(h,q) (of which there
should be about log q) then:
s(h,q) = 1/12 * sum_{i=1}^{n+1}((-1)^(i+1) (r_i^2 + r_{i-1}^2 + 1) /
(r_i * r_{i-1}) - ((-1)^n +1)/8)
This, with the other ideas I gave above, will definitely let us beat
Mathematica convincingly, as a simple back of the envelope calculation
shows. It will have the added benefit of allowing us to beat Magma at
something.
Bill.
On 27 Jul, 00:12, Bill Hart [EMAIL PROTECTED] wrote:
OK, apparently the Dedekind sums should be done using an algorithm due
to Apostol. I haven't tracked it down yet, but this is clearly what we
need.
Bill.
On 26 Jul, 23:37, Bill Hart [EMAIL PROTECTED] wrote:
On 26 Jul, 23:18, Jonathan Bober [EMAIL PROTECTED] wrote:
s(h,k) = h(k - 1)(2k - 1)/(6k) - (k-1)/4 -
(1/k) sum_{j=1}^{k-1} j*floor(hj/k).
(To compute the floor in the inner sum, you can just use integer
division.)
Yes, this will be faster. Of course integer division is not faster
than floating point division, but since we are doing a sum from j = 1
to k-1 we only need to know when floor(hj/k) increases by 1. This is
simply a matter of adding h each iteration and seeing if we have gone
over k (subtracting k if we do). If so, floor(hj/k) has increased by 1
and so on.
This gets the inner computation down to about 8 cycles or so on
average. Not enough to beat Mathematica though, unless I made a
mistake in my back of the envelope computation somewhere.
Bill.
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: accessing GAP's small groups database from the notebook
David Joyner [EMAIL PROTECTED] writes: Could you please try gap_reset_workspace() and then restart SAGE and see if the examples start? That fixed it! Thanks. Not sure what I did. The problem occurred on two different systems, which my home directory is mirrored between. If it happens again, I'll report any additional info I can think of. Dan --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
I just found this on http://reference.wolfram.com/mathematica/note/SomeNotesOnInternalImplementation.html: PartitionsP[n] uses Euler's pentagonal formula for small n, and the non-recursive Hardy-Ramanujan-Rademacher method for larger n. --Mike On 7/26/07, Alec Mihailovs [EMAIL PROTECTED] wrote: From: Mike Hansen [EMAIL PROTECTED] I'm not sure where the bottleneck in PARI is since I can't imagine Mathematica uses a different method to compute the number of partitions. I don't know what is used in the latest Mathematica version, but originally NumberOfPartitions function in the Combinatorica package used the recursion with pentagonal numbers, see http://www.cs.uiowa.edu/~sriram/Combinatorica/NewCombinatorica.m Alec --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: accessing GAP's small groups database from the notebook
On 7/26/07, Dan Christensen [EMAIL PROTECTED] wrote: David Joyner [EMAIL PROTECTED] writes: Could you please try gap_reset_workspace() and then restart SAGE and see if the examples start? That fixed it! Thanks. Not sure what I did. The problem occurred on two different systems, which my home directory is mirrored between. If it happens again, I'll report any additional info I can think of. Very interesting. When you install the gap database, SAGE runs gap_reset_workspace() to update the cached workspace on the machine on which the database is installed. Because a single home directory could be used by multiple machines, there are potentially multiple gap workspace cache files, and for you only one was updated. This is an annoying design (due to me), since multiple users of a single SAGE install will all have to type gap_reset_workspace() to get the new gap libraries (when one installs, e.g., the small group database). I should change the implementation so when installing database_gap (or anything else that might invalidate the stored gap workspace, or more precisely make it not optimal), then *all* gap workspace cache files from all users of that SAGE install become invalid. They would then be regenerated (which takes only a few seconds) the next time any user starts GAP from a SAGE session. I could do this by assigning a sequence number, e.g., in a file like local/lib/gap-sequence-number, which is incremented any time gap is updated in some way. Then I could make the cached workspace (or another file with a similar name next to the gap workspace file) also store this sequence number (the cached workspaces are in ~/.sage/gap/). Then whenever a gap interpreter is first started in interface/gap.py, this sequence number is checked, and if it doesn't match, then the gap workspace is regenerated. This should completely eliminate all future gap_reset_workspace synchronization errors. I'll wait to see if anybody thinks the above idea is stupid, and if not, I'll implement it (which shouldn't take long). I've made this trac #407: http://www.sagemath.org:9002/sage_trac/ticket/407 -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] computing the number of partitions of an integer
Hi, Since we were recently discussing speed of computing Bell numbers, maybe it would be interesting to discuss computing the number of partitions of an integer as a sum of other positive integers, i.e., sage: number_of_partitions(5) 7 sage: v = list(partitions(5)); v [(1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2), (1, 1, 3), (2, 3), (1, 4), (5,)] sage: len(v) 7 Currently, I'm going through the Mathematica tour and making a SAGE version of it. The Mathematica tour is a free pdf download available here: http://documents.wolfram.com/mathematica/Mathematica_V5_Book.zip The first thing Mathematica can do that SAGE can't is compute number_of_partitions(10^9) in a few seconds -- a frontier number theory calculation (page 5). In SAGE it takes around 80-100 seconds to compute sage: number_of_partitions(10^8, algorithm=pari) Actually, on sage.math, Mathematica takes 67 seconds to compute the number of partitions for 10^9 and about 10 seconds to do 10^8. QUESTIONS: Why is Mathematica about 10 times faster than PARI at this? What are the best ways to compute the number of partitions of n? Is it a calculation involving fast arithmetic with dense polynomials of large degree, which would be best done using the upcoming FLINT library or NTL? It's a little embarasing that the first thing Mathematica does that SAGE doesn't do reasonably quickly in their tour is a number theory calculation. -- William -- William Stein Associate Professor of Mathematics University of Washington http://www.williamstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] interaction between GAP and notebook
Some other minor issues about using GAP within the notebook, under 2.7.1. I've put my entire worksheet in GAP mode using the menu at the top. The following things don't work correctly: 0) If I type something that gives an error in GAP, the error message is buried in a python exception/backtrace. 1) If I type ?SymmetricGroup (which works within GAP), all I see is Help: Showing `Reference: SymmetricGroup' Page from 104 It's similar with other ?foo commands. 2) If I type SymmetricGroup? and hit tab, it shows me help about sage's wrapped SymmetricGroup function. I don't think this will be helpful for functions not wrapped by sage. 3) When I try to use tab completion, it inserts gap. before the command (and probably ignores functions not wrapper by sage). Dan --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
Pari implements it, but incorrectly:
sage: number_of_partitions(5*10535+4,algorithm=pari)
132775694853416614410709359082850304628573507097
148711672236023178345995078715426574030466347126
367130008280402558755564770977624160764152691390
102001213796297899514590335375857238756973648770
246446295491295636766189177742381389268656730071
68971398574
But:
sage: number_of_partitions(5*10535+4)
132775694853416614410709359082850304628573507097
148711672236023178345995078715426574030466347126
367130008280402558755564770977624160764152691390
102001213796297899514590335375857238756973648770
246446295491295636766189177742381389268656730071
68971398575
At least GAP returns the right answer!! But after some time:
sage: number_of_partitions(5*10535+4)
---
type 'exceptions.RuntimeError' Traceback (most recent call
last)
/home/wbhart/flint/trunk/ipython console in module()
/home/was/s/local/lib/python2.5/site-packages/sage/combinat/
combinat.py in number_of_partitions(n, k, algorithm)
1245 if algorithm == 'gap':
1246 if k==None:
- 1247 ans=gap.eval(NrPartitions(%s)%(ZZ(n)))
1248 else:
1249 ans=gap.eval(NrPartitions(%s,%s)%(ZZ(n),ZZ(k)))
/home/was/s/local/lib/python2.5/site-packages/sage/interfaces/gap.py
in eval(self, x, newlines, strip)
298 if len(x) == 0 or x[len(x) - 1] != ';':
299 x += ';'
-- 300 s = Expect.eval(self, x)
301 if newlines:
302 return s
/home/was/s/local/lib/python2.5/site-packages/sage/interfaces/
expect.py in eval(self, code, strip, **kwds)
519 code = code.strip()
520 try:
-- 521 return '\n'.join([self._eval_line(L, **kwds) for L
in code.split('\n') if L != ''])
522 except KeyboardInterrupt:
523 self._keyboard_interrupt()
/home/was/s/local/lib/python2.5/site-packages/sage/interfaces/gap.py
in _eval_line(self, line, allow_use_file, wait_for_prompt)
482 return ''
483 else:
-- 484 raise RuntimeError, message
485
486 except KeyboardInterrupt:
type 'exceptions.RuntimeError': Unexpected EOF from Gap executing
NrPartitions(52679);
Bill.
On 26 Jul, 07:38, Nick Alexander [EMAIL PROTECTED] wrote:
William Stein [EMAIL PROTECTED] writes:
QUESTIONS: Why is Mathematica about 10 times faster than PARI
at this? What are the best ways to compute the number
of partitions of n? Is it a calculation involving fast arithmetic
with dense polynomials of large degree, which would be best done
using the upcoming FLINT library or NTL?
Please correct me if I'm crazy, but isn't there an asymptotic formula
due to Hardy and Rademacher that can evaluate $P(n)$ to a very high
accuracy very quickly? Surely both of these packages implement such a
convergent series approach, and it is possible that SAGE has faster
real arithmetic and could do this faster.
Again, I may be completely incorrect -- please let me know.
Nick
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
From: Mike Hansen [EMAIL PROTECTED] I'm not sure where the bottleneck in PARI is since I can't imagine Mathematica uses a different method to compute the number of partitions. I don't know what is used in the latest Mathematica version, but originally NumberOfPartitions function in the Combinatorica package used the recursion with pentagonal numbers, see http://www.cs.uiowa.edu/~sriram/Combinatorica/NewCombinatorica.m Alec --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Fwd: Numerics in SAGE
Hi, This may be of general interest to sage-devel people who are interested in SAGE becoming a viable alternative to MATLAB. -- William -- Forwarded message -- From: Randy LeVeque (Applied Math at UW) Date: Jul 26, 2007 2:12 PM Subject: Numerics in SAGE To: Hans Petter Langtangen Dear Hans Petter, Thanks for your note. I'll respond separately about various other things in your note, but wanted to respond about SAGE also to others with an interest in this. NumPy and SciPy are now in SAGE, along with an interface to f2py, see http://www.math.washington.edu/~jkantor/Numerical_Sage/ Some aspects of the matlab language are also mimiced in SAGE in a more direct way than Python, but we'd be very interested to hear more about how you use Python in your programming course. Perhaps you can send some examples when you're back from vacation and get a chance. Also, what graphics package do you use in your programming course in conjunction with Python? Best regards, Randy On Thu, 26 Jul 2007, Hans Petter Langtangen wrote: ... Regarding the promising SAGE project, I see that much has happened there lately :-) If you combine SAGE with other Python tools (NumPy and SciPy in particular, plus some of the stuff that we develop), I think you already have a Matlab replacement (and much more) that you can use in your course. In the introductory programming course we will give this fall we provide a complete easy-to-install Python package which has most of the Matlab functionality needed in the bachelor programs here in Oslo. We also try to use Python in a way such that the syntax switch between Matlab and Python is as small as possible. ... Best regards, Hans Petter (on holiday in Spain) -- William Stein Associate Professor of Mathematics University of Washington http://www.williamstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] accessing GAP's small groups database from the notebook
I'm having trouble accessing GAP's small groups database from the notebook. I'm using the binary install of 2.7.1 on 32-bit Debian. I have installed database_gap-4.4.9 and gap_packages-4.4.9_2. If I do sage -gap, then inside the gap process, I can do: gap NumberSmallGroups(2^3); 5 But if I use gap within a notebook worksheet, or if I start sage with sage, the small groups database isn't loaded: [EMAIL PROTECTED]:~$ sage -- | SAGE Version 2.7.1, Release Date: 2007-07-24 | | Type notebook() for the GUI, and license() for information.| -- sage: %gap -- Switching to Gap -- '' gap: NumberSmallGroups(2^3); --- type 'exceptions.RuntimeError' Traceback (most recent call last) [...stuff omitted...] type 'exceptions.RuntimeError': Gap produced error output Error, the Small Groups library is required but not installed executing NumberSmallGroups(2^3);; Dan --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: interaction between GAP and notebook
On 7/26/07, Dan Christensen [EMAIL PROTECTED] wrote: Some other minor issues about using GAP within the notebook, under 2.7.1. I've put my entire worksheet in GAP mode using the menu at the top. The following things don't work correctly: 0) If I type something that gives an error in GAP, the error message is buried in a python exception/backtrace. 1) If I type ?SymmetricGroup (which works within GAP), all I see is Help: Showing `Reference: SymmetricGroup' Page from 104 It's similar with other ?foo commands. 2) If I type SymmetricGroup? and hit tab, it shows me help about sage's wrapped SymmetricGroup function. I don't think this will be helpful for functions not wrapped by sage. 3) When I try to use tab completion, it inserts gap. before the command (and probably ignores functions not wrapper by sage). I am aware of each of these issues (which also happen with the other interfaces). They are *not* features in my mind, but bugs, and they need to be fixed by somebody (either me or somebody else). I've created trac #406 to better keep track of this todo item: http://www.sagemath.org:9002/sage_trac/ticket/406 I would, of course, be very happy if somebody were to implement anything related and send me a patch :-). William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: computing the number of partitions of an integer
OK, apparently the Dedekind sums should be done using an algorithm due
to Apostol. I haven't tracked it down yet, but this is clearly what we
need.
Bill.
On 26 Jul, 23:37, Bill Hart [EMAIL PROTECTED] wrote:
On 26 Jul, 23:18, Jonathan Bober [EMAIL PROTECTED] wrote:
s(h,k) = h(k - 1)(2k - 1)/(6k) - (k-1)/4 -
(1/k) sum_{j=1}^{k-1} j*floor(hj/k).
(To compute the floor in the inner sum, you can just use integer
division.)
Yes, this will be faster. Of course integer division is not faster
than floating point division, but since we are doing a sum from j = 1
to k-1 we only need to know when floor(hj/k) increases by 1. This is
simply a matter of adding h each iteration and seeing if we have gone
over k (subtracting k if we do). If so, floor(hj/k) has increased by 1
and so on.
This gets the inner computation down to about 8 cycles or so on
average. Not enough to beat Mathematica though, unless I made a
mistake in my back of the envelope computation somewhere.
Bill.
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: GAP and rings?
David Joyner [EMAIL PROTECTED] writes: You probably know this already but the 2003 survey www.math.rwth-aachen.de/~Gerhard.Hiss/Preprints/AlgoRepTheo.pdf discusses briefly what is/was out there. I don't think it mentions recent packages such as laguna, crime, and hap, but I don't know of a more recent survey. I knew about the survey, but not about those most recent packages. Thanks for pointing them out! They look *very* useful to me. I also discovered code by Peter Webb which focuses on the modular case. I'll include URLs for all of these for the archives: http://www.math.umn.edu/~webb/GAPfiles/ http://ukrgap.exponenta.ru/LAGUNA.htm http://www-gap.mcs.st-and.ac.uk/Manuals/pkg/Hap1.7.4/www/index.html http://www.gap-system.org/Packages/crime.html http://www.math.uic.edu/~marcus/Crime/ But what about Tate cohomology? Block decompositions? Hom in the stable module category? Thanks again! Dan --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: accessing GAP's small groups database from the notebook
William Stein [EMAIL PROTECTED] writes: Very interesting. When you install the gap database, SAGE runs gap_reset_workspace() to update the cached workspace on the machine on which the database is installed. Because a single home directory could be used by multiple machines, there are potentially multiple gap workspace cache files, and for you only one was updated. My problem occurred restricted to one machine, before I came home and synced my home directory, so I don't think the mirroring was actually relevant (except that it might mean that whatever went wrong on the first machine got mirrored to the second). Here's another theory: I believe I was actually use GAP, via the sage notebook, while I installed the small group database. Could this have caused the problem? Or maybe I had some junk left in my home directory from some old version of sage, and that junk caused trouble? I hadn't upgraded in a while. Dan --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
