Prev: look upon 231! not as #rearrangements but as volume or time #647 Correcting Math
Next: Grafik......
From: Gerry on 10 Jul 2010 21:03
On Jul 11, 9:43 am, Bart Goddard <goddar...(a)netscape.net> wrote:
> Hi folks,
>
> If you can hear me through all the noise, I've got
> a little conundrum.
>
> Let p(n) be the number of integer partitions of
> integer n.  Euler gave the recursion formula
>
> p(n) = sum_k (-1)^(k+1) ( p(n-k(3k-1)/2) - p(n-k(3k+1)/2) ).
>
> Andres and Eriksson, in _Integer Partitions_ state, without
> proof or hint, that using this formula, one can compute
> p(n) in O(n^(3/2)) operations.  I am unable to verify this
> assertion.
>
> If anyone has any hints or references, I'd love to
> have them.

The sum has O(sqrt n) terms. So, if you had already calculated
p(k) for all k less than n, you'd need O(sqrt n) additions to
get p(n). To calculate all those p(k), you need O(sum sqrt k)
operations, and sum sqrt k is n^(3/2). Does that seem OK?
--
GM
From: Henry on 12 Jul 2010 03:57
On 11 July, 02:03, Gerry <ge...(a)math.mq.edu.au> wrote:
> On Jul 11, 9:43 am, Bart Goddard <goddar...(a)netscape.net> wrote:
>
> > If you can hear me through all the noise, I've got
> > a little conundrum.
>
> > Let p(n) be the number of integer partitions of
> > integer n.  Euler gave the recursion formula
>
> > p(n) = sum_k (-1)^(k+1) ( p(n-k(3k-1)/2) - p(n-k(3k+1)/2) ).
>
> > Andres and Eriksson, in _Integer Partitions_ state, without
> > proof or hint, that using this formula, one can compute
> > p(n) in O(n^(3/2)) operations.  I am unable to verify this
> > assertion.
>
> > If anyone has any hints or references, I'd love to
> > have them.
>
> The sum has O(sqrt n) terms. So, if you had already calculated
> p(k) for all k less than n, you'd need O(sqrt n) additions to
> get p(n). To calculate all those p(k), you need O(sum sqrt k)
> operations, and sum sqrt k is n^(3/2). Does that seem OK?

That deals with the number of operations of addition and
subtraction.

But the time take will be more than O(n^(3/2) for large n because the
average time per operation (using unlimited precision integer
arithmetic) will increase with increasing n. For large n, the number
of digits of p(n) (in binary or decimal) is roughly proportional to
sqrt(n). So overall something like O(n^2) might be more realistic

As an example, using Java code similar to the applet at
http://www.btinternet.com/~se16/js/partitions.htm
(though without the counter or GUI)
took me about 20 seconds to calculate p(1000000) =
27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519
but about 75 seconds to calculate p(2000000) =
1142149040516629749037121530402138096853926160881948532505004601437486969047069848233533537228547558093788739002612142642220379461285625596845952597486179818841905527749813150474498721747633064058840437916036245712660272843036962395856213719373419360640609193628394201054990897781263014274799184617869958648852094318304681098737364938930543346705147603014542998991252631960051596213531387338008165217582822943454514251881668474896643416706191144360737225405767060795784657847417376966116043766

From: Bart Goddard on 14 Jul 2010 10:50
Henry <se16(a)btinternet.com> wrote in
news:3367c7c9-262e-4fc8-ad66-2ae8ed2daa8a(a)s9g2000yqd.googlegroups.com:


>> The sum has O(sqrt n) terms. So, if you had already calculated
>> p(k) for all k less than n, you'd need O(sqrt n) additions to
>> get p(n). To calculate all those p(k), you need O(sum sqrt k)
>> operations, and sum sqrt k is n^(3/2). Does that seem OK?
>
> That deals with the number of operations of addition and
> subtraction.
>
> But the time take will be more than O(n^(3/2) for large n because the
> average time per operation

Yeah, that solves my problem. My source meant to say "additions"
rather than "bit operations." I get to do the wasn't-my-fault
dance.

Thanks Gerry and Henry.


--
Cheerfully resisting change since 1959.
From: Chip Eastham on 14 Jul 2010 11:05
On Jul 14, 10:50 am, Bart Goddard <goddar...(a)netscape.net> wrote:
> Henry <s...(a)btinternet.com> wrote innews:3367c7c9-262e-4fc8-ad66-2ae8ed2daa8a(a)s9g2000yqd.googlegroups.com:
>
> >> The sum has O(sqrt n) terms. So, if you had already calculated
> >> p(k) for all k less than n, you'd need O(sqrt n) additions to
> >> get p(n). To calculate all those p(k), you need O(sum sqrt k)
> >> operations, and sum sqrt k is n^(3/2). Does that seem OK?
>
> > That deals with the number of operations of addition and
> > subtraction.
>
> > But the time take will be more than O(n^(3/2) for large n because the
> > average time per operation
>
> Yeah, that solves my problem.  My source meant to say "additions"
> rather than "bit operations."  I get to do the wasn't-my-fault
> dance.
>
> Thanks Gerry and Henry.
>
> --
> Cheerfully resisting change since 1959.

I did a Prolog implementation of this last year,
and was unable to achieve O(n^1.5) running time
due to language limitations. [Prolog has lists
but not (randomly addressable) arrays.] I'd
suspect that apart from the big-integer arithmetic
the improved running time is fairly easy to get
with pointer arithmetic in languages like C.

Brief mention at the end of this thread in
comp.lang.prolog:

[Is it possible to count solutions that cannot
fit in memory -- comp.lang.prolog]
http://groups.google.com/group/comp.lang.prolog/browse_frm/thread/2d8bf9e8b9a40b7/c8f1c22a9fac7b80?hl=en&lnk=gst&q=+partitions#c8f1c22a9fac7b80

regards, chip
 | 
Pages: 1
Prev: look upon 231! not as #rearrangements but as volume or time #647 Correcting Math
Next: Grafik......