ev-bug

For a 20,000 member list, my function bob is about 100
times faster than your function rcs. For longer lists,
the gap increases (rcs is O(n^2) and bob is O(n)).

(%i1) bob(l) := block([s : 0, k : 1],
   for lk in l do (
      s : s + binomial(lk-1,k),
      k : k + 1),
   s + 1)$
(%i2) rcs(S) := block([L : listify(S)],
  apply("+",create_list(binomial(L[i]-1,i), i,1,length(L))) + 1)$
(%i3) load("integer_sequence")$

(%i27) p : 1 .. 2 * 10^4$
Evaluation took 0.0500 seconds (0.0500 elapsed)
(%i21) showtime : all$

Evaluation took 0.0000 seconds (0.0000 elapsed)
(%i28) bob(p);
Evaluation took 0.2700 seconds (0.2700 elapsed)

(%o28) 1
(%i29) rcs(p);

Evaluation took 29.3300 seconds (29.3300 elapsed)
(%o29) 1

Barton

-----maxima-bounces at math.utexas.edu wrote: -----


>Forgot?to?reply?to?the?whole?list;?here?is?my?answer.
>
>>?On?Wed,?May?13,?2009?at?02:00:30PM?-0500,?Barton?Willis?wrote:
>>?(1)?If?there?is?a?global?hashed?array?L?defined,?L[i]?extracts?the?value
>of
>>?the
>>?global?hashed?array,?not?the?member?of?local?list?variable?L.?The?fix?is
>to
>>?replace?L[i]?with?inpart(L,i).
>>
>
>I'll?keep?that?in?mind.
>
>>?(2)?Your?code?is?inefficient,?I?think.?Try?rewriting?rcs?as?loop:
>>
>>?(%i16)?bob(l)?:=?block([s?:?0,?k?:?1],
>>???for?lk?in?l?do?(
>>??????s?:?s?+?binomial(lk-1,k),
>>??????k?:?k?+?1),
>>???s?+?1)$
>>
>>?(%i28)?bob([a,b]);
>>?(%o28)?((b-2)*(b-1))/2+a
>
>It's?really?the?opposite:?Loops?are?*much*?slower!
>
>?(%i13)?block([s:0],?for?i?from?1?thru?1000000?do?s?:?s?+?i,?s);
>Evaluation?took?21.9220?seconds?(42.0870?elapsed)
>(%o13)?500000500000
>(%i14)?apply("+",create_list(i,i,1,1000000));
>Evaluation?took?1.4680?seconds?(1.4670?elapsed)
>(%o14)?500000500000
>
>(And?this?becomes?worse?for?longer?loops;?of?course,?at?some
>point?memory?doesn't?follow?;-()
>
>>?(3)?The?usage?of?a?Maxima?set?as?an?input?to?rcs?seems?spurious.
>>
>
>sure?---?this?comes?from?the?context?where?this?is?all?used.
>
>>?(4)?As?for?the?calls?to?ev?in?your?code,?I?don't?want?to?think?about?it.
>>?Ev?makes?my?head?hurt.
>>
>
>But?it?seems?to?be?the?only?possibility?in?this?application?
>
>thanks!
>
>Oliver
>
>>?>?Barton
>>?>
>>?>?-----maxima-bounces at math.utexas.edu?wrote:?-----
>>?>
>>?>
>>?>?>Maxima?5.18.1?http://maxima.sourceforge.net
>>?>?>Using?Lisp?ECL?9.4.1
>>?>?>declare(rv,noun)$
>>?>?>rcs(S)?:=?block([L?:?listify(S)],
>>?>?>??apply("+",create_list(binomial(L[i]-1,i),?i,1,length(L)))?+?1)$
>>?>?>(%i4)?ev(rv(1,4),rv([L]):=rcs(setify(L)),nouns);
>>?>?>(%o4)?4
>>?>?>(%i5)?ev(rv(1,5),rv([L]):=rcs(setify(L)),nouns);
>>?>?>(%o5)?7.0
>>?>?>(%i6)?rcs({1,5});
>>?>?>(%o6)?7
>>?>?>
>>?>?>I?hope?you?see?the?disaster:?o6?is?correct,?and?should?be?the?same
>>?>?>as?o5,?but?somehow?suddenly?the?result?is?turned?into?a
>floating-point
>>?>?>number?(which?depends?on?the?values?---?doesn't?happen?with?o4).
>>?>?>
>>?>?>I?guess?I?should?submit?this?as?a?bug,?but?wanted?to?hear?some
>comments
>>?>?>first.
>>?>?>
>>?>?>(Workarounds??Currently?the?above?behaviour?blocks?a?whole
>development;
>>?>?>but
>>?>?>using?floor?doesn't?seem?safe?...)
>>?>?>
>>?>?>Oliver
>>?>?>
>>?>?>_______________________________________________
>>?>?>Maxima?mailing?list
>>?>?>Maxima at math.utexas.edu
>>?>?>http://www.math.utexas.edu/mailman/listinfo/maxima
>>
>>?--
>>?Dr.?Oliver?Kullmann
>>?Computer?Science?Department
>>?Swansea?University
>>?Faraday?Building,?Singleton?Park
>>?Swansea?SA2?8PP,?UK
>>?http://cs.swan.ac.uk/~csoliver/
>
>--
>Dr.?Oliver?Kullmann
>Computer?Science?Department
>Swansea?University
>Faraday?Building,?Singleton?Park
>Swansea?SA2?8PP,?UK
>http://cs.swan.ac.uk/~csoliver/
>_______________________________________________
>Maxima?mailing?list
>Maxima at math.utexas.edu
>http://www.math.utexas.edu/mailman/listinfo/maxima