Hi all, I am facing a series for which I would like to obtain the sum. It looks like the following I=sum((-1)^k*a_k*b_k, k from 0 to 1000), where a_k's involve binomial coeffcients at order roughly linear with the growth of k. Hence a_k's can be extremely large, beyond the capability of super computers; however, b_k is around 10^(-10), and finally the summation I will fall into [0, 1]. Thus it looks like only the last 10s of digits of a_k that are really important. And any error in computing the last a few digits of a_k*b_k will lead to huge error and lead to wrong results. Could anybody give some suggestions on how to handle such series summations involving large binomial coefficients... ??? Thanks!
Does anybody know how to evaluate this summation of alternating series?
Started by ●July 1, 2007
Reply by ●July 1, 20072007-07-01
On Jul 1, 8:58 pm, "Vista" <a...@gmai.com> wrote:> Hi all, > > I am facing a series for which I would like to obtain the sum. It looks like > the following > > I=sum((-1)^k*a_k*b_k, k from 0 to 1000), > > where a_k's involve binomial coeffcients at order roughly linear with the > growth of k. Hence a_k's can be extremely large, beyond the capability of > super computers; > > however, b_k is around 10^(-10), and finally the summation I will fall into > [0, 1]. > > Thus it looks like only the last 10s of digits of a_k that are really > important. And any error in computing the last a few digits of a_k*b_k will > lead to huge error and lead to wrong results. > > Could anybody give some suggestions on how to handle such series summations > involving large binomial coefficients... > > ??? > > Thanks!Hello Vista, Several questions - Are all of the b_k the same are just similar? Do all of the binomial coefs in your series come from the same line in Pascal's triangle? Also you may be able to use the fact that each binomial coef may be reduce to a sum of two lower order binomial coefs. In this case (depending on the b_k), you may be able to cancel out some of the binomial factors. Also how does this series arise? There may be some clues in its development that will allow for an adroit solution. Clay
Reply by ●July 2, 20072007-07-02
"Vista" <abc@gmai.com> writes:> Hi all, > > I am facing a series for which I would like to obtain the sum. It looks > like > the following > > I=sum((-1)^k*a_k*b_k, k from 0 to 1000), > > where a_k's involve binomial coeffcients at order roughly linear with the > growth of k. Hence a_k's can be extremely large, beyond the capability of > super computers;What do you think "the capability of super computers" is? Running something like Maple, even a very ordinary computer can handle some pretty large numbers. Are you talking about billions of digits?> however, b_k is around 10^(-10), and finally the summation I will fall into > > [0, 1]. > > Thus it looks like only the last 10s of digits of a_k that are really > important. And any error in computing the last a few digits of a_k*b_k will > > lead to huge error and lead to wrong results.These two statements appear to be contradictory. -- Robert Israel israel@math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2
Reply by ●July 2, 20072007-07-02
"Robert Israel" <israel@math.MyUniversitysInitials.ca> wrote in message news:rbisrael.20070702025200$77b2@news.ks.uiuc.edu...> "Vista" <abc@gmai.com> writes: > >> Hi all, >> >> I am facing a series for which I would like to obtain the sum. It looks >> like >> the following >> >> I=sum((-1)^k*a_k*b_k, k from 0 to 1000), >> >> where a_k's involve binomial coeffcients at order roughly linear with the >> growth of k. Hence a_k's can be extremely large, beyond the capability of >> super computers; > > What do you think "the capability of super computers" is? Running > something like Maple, even a very ordinary computer can handle some > pretty large numbers. Are you talking about billions of digits? >Robert, Thank about 1000!/500!/500!, and you have so many terms adding up, in alternating signs, and you have to care about the last a few digits of each term. And there is one more constraint that I forgot to mention, such summation is a small part of a big system, and it has to be run millions of times in a very short time...
Reply by ●July 2, 20072007-07-02
On Jul 1, 8:33 pm, "Vista" <a...@gmai.com> wrote:> "Robert Israel" <isr...@math.MyUniversitysInitials.ca> wrote in message > > news:rbisrael.20070702025200$77b2@news.ks.uiuc.edu... > > > > > "Vista" <a...@gmai.com> writes: > > >> Hi all, > > >> I am facing a series for which I would like to obtain the sum. It looks > >> like > >> the following > > >> I=sum((-1)^k*a_k*b_k, k from 0 to 1000), > > >> where a_k's involve binomial coeffcients at order roughly linear with the > >> growth of k. Hence a_k's can be extremely large, beyond the capability of > >> super computers; > > > What do you think "the capability of super computers" is? Running > > something like Maple, even a very ordinary computer can handle some > > pretty large numbers. Are you talking about billions of digits? > > Robert, > > Thank about 1000!/500!/500!,No problem: Maple gets (almost immediately after pressing the 'enter' key): n:=1000!/500!/500!; n := 27028824094543656951561469362597527549615200844654828700739\ 2875106625428705522193898612483924502370165362606085021546\ 1048022097500506799175498942196995184754236654842637517333\ 5616246407973788734436457416111949760457104498575628788051\ 4600994219426752366915856603136862602484428109296905863799\ 821216320 In the version I have (Maple 9.5) the limit is 500,000 decimal digits. I don't know if this has been extended in newer versions. R.G. Vickson> and you have so many terms adding up, in > alternating signs, and you have to care about the last a few digits of each > term. > > And there is one more constraint that I forgot to mention, such summation is > a small part of a big system, and it has to be run millions of times in a > very short time...
Reply by ●July 2, 20072007-07-02
"Vista" <abc@gmai.com> writes:> Hi all, > > I am facing a series for which I would like to obtain the sum. It looks like > the following > > I=sum((-1)^k*a_k*b_k, k from 0 to 1000), > > where a_k's involve binomial coeffcients at order roughly linear with the > growth of k. Hence a_k's can be extremely large, beyond the capability of > super computers; > > however, b_k is around 10^(-10), and finally the summation I will fall into > [0, 1]. > > Thus it looks like only the last 10s of digits of a_k that are really > important. And any error in computing the last a few digits of a_k*b_k will > lead to huge error and lead to wrong results. > > Could anybody give some suggestions on how to handle such series summations > involving large binomial coefficients...Maybe it would help if you would be more specific. What is the series you are trying to sum? It might have a closed-form solution. Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear
Reply by ●July 2, 20072007-07-02
On Jul 2, 7:54 am, "C...@shaw.ca" <C...@shaw.ca> wrote:> On Jul 1, 8:33 pm, "Vista" <a...@gmai.com> wrote: > > > > > > > "Robert Israel" <isr...@math.MyUniversitysInitials.ca> wrote in message > > >news:rbisrael.20070702025200$77b2@news.ks.uiuc.edu... > > > > "Vista" <a...@gmai.com> writes: > > > >> Hi all, > > > >> I am facing a series for which I would like to obtain the sum. It looks > > >> like > > >> the following > > > >> I=sum((-1)^k*a_k*b_k, k from 0 to 1000), > > > >> where a_k's involve binomial coeffcients at order roughly linear with the > > >> growth of k. Hence a_k's can be extremely large, beyond the capability of > > >> super computers; > > > > What do you think "the capability of super computers" is? Running > > > something like Maple, even a very ordinary computer can handle some > > > pretty large numbers. Are you talking about billions of digits? > > > Robert, > > > Thank about 1000!/500!/500!, > > No problem: Maple gets (almost immediately after pressing the 'enter' > key): > > n:=1000!/500!/500!; > n := 27028824094543656951561469362597527549615200844654828700739\ > 2875106625428705522193898612483924502370165362606085021546\ > 1048022097500506799175498942196995184754236654842637517333\ > 5616246407973788734436457416111949760457104498575628788051\ > 4600994219426752366915856603136862602484428109296905863799\ > 821216320 > In the version I have (Maple 9.5) the limit is 500,000 decimal digits. > I don't know if this has been extended in newer versions. > > R.G. Vickson > > > > > and you have so many terms adding up, in > > alternating signs, and you have to care about the last a few digits of each > > term. > > > And there is one more constraint that I forgot to mention, such summation is > > a small part of a big system, and it has to be run millions of times in a > > very short time...- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text -Also ran in no discernable time on MATLAB (2 lines), 2.702882409454369e+299 a little less resolution, but you don't have to count the digits :-) Dirk
Reply by ●July 2, 20072007-07-02
<C6L1V@shaw.ca> wrote in message news:1183377288.638615.122680@z28g2000prd.googlegroups.com...> On Jul 1, 8:33 pm, "Vista" <a...@gmai.com> wrote: >> "Robert Israel" <isr...@math.MyUniversitysInitials.ca> wrote in message >> >> news:rbisrael.20070702025200$77b2@news.ks.uiuc.edu... >> >> >> >> > "Vista" <a...@gmai.com> writes: >> >> >> Hi all, >> >> >> I am facing a series for which I would like to obtain the sum. It >> >> looks >> >> like >> >> the following >> >> >> I=sum((-1)^k*a_k*b_k, k from 0 to 1000), >> >> >> where a_k's involve binomial coeffcients at order roughly linear with >> >> the >> >> growth of k. Hence a_k's can be extremely large, beyond the capability >> >> of >> >> super computers; >> >> > What do you think "the capability of super computers" is? Running >> > something like Maple, even a very ordinary computer can handle some >> > pretty large numbers. Are you talking about billions of digits? >> >> Robert, >> >> Thank about 1000!/500!/500!, > > No problem: Maple gets (almost immediately after pressing the 'enter' > key): > > n:=1000!/500!/500!; > n := 27028824094543656951561469362597527549615200844654828700739\ > 2875106625428705522193898612483924502370165362606085021546\ > 1048022097500506799175498942196995184754236654842637517333\ > 5616246407973788734436457416111949760457104498575628788051\ > 4600994219426752366915856603136862602484428109296905863799\ > 821216320 > In the version I have (Maple 9.5) the limit is 500,000 decimal digits. > I don't know if this has been extended in newer versions. > > R.G. Vickson >Try doing it millions of times.
Reply by ●July 2, 20072007-07-02
"dbell" <bellda2005@cox.net> wrote in message news:1183410759.888690.214020@k79g2000hse.googlegroups.com...> On Jul 2, 7:54 am, "C...@shaw.ca" <C...@shaw.ca> wrote: >> On Jul 1, 8:33 pm, "Vista" <a...@gmai.com> wrote: >> >> >> >> >> >> > "Robert Israel" <isr...@math.MyUniversitysInitials.ca> wrote in message >> >> >news:rbisrael.20070702025200$77b2@news.ks.uiuc.edu... >> >> > > "Vista" <a...@gmai.com> writes: >> >> > >> Hi all, >> >> > >> I am facing a series for which I would like to obtain the sum. It >> > >> looks >> > >> like >> > >> the following >> >> > >> I=sum((-1)^k*a_k*b_k, k from 0 to 1000), >> >> > >> where a_k's involve binomial coeffcients at order roughly linear >> > >> with the >> > >> growth of k. Hence a_k's can be extremely large, beyond the >> > >> capability of >> > >> super computers; >> >> > > What do you think "the capability of super computers" is? Running >> > > something like Maple, even a very ordinary computer can handle some >> > > pretty large numbers. Are you talking about billions of digits? >> >> > Robert, >> >> > Thank about 1000!/500!/500!, >> >> No problem: Maple gets (almost immediately after pressing the 'enter' >> key): >> >> n:=1000!/500!/500!; >> n := 27028824094543656951561469362597527549615200844654828700739\ >> 2875106625428705522193898612483924502370165362606085021546\ >> 1048022097500506799175498942196995184754236654842637517333\ >> 5616246407973788734436457416111949760457104498575628788051\ >> 4600994219426752366915856603136862602484428109296905863799\ >> 821216320 >> In the version I have (Maple 9.5) the limit is 500,000 decimal digits. >> I don't know if this has been extended in newer versions. >> >> R.G. Vickson >> >> >> >> > and you have so many terms adding up, in >> > alternating signs, and you have to care about the last a few digits of >> > each >> > term. >> >> > And there is one more constraint that I forgot to mention, such >> > summation is >> > a small part of a big system, and it has to be run millions of times in >> > a >> > very short time...- Hide quoted text - >> >> - Show quoted text -- Hide quoted text - >> >> - Show quoted text - > > Also ran in no discernable time on MATLAB (2 lines), > > 2.702882409454369e+299 > > a little less resolution, but you don't have to count the digits :-) > > Dirk >Wrong! It really is the last few digits that count. Remember the correct sum of such alternating series should be between [0, 1]!
Reply by ●July 2, 20072007-07-02
"Vista" <abc@gmai.com> writes:> > <C6L1V@shaw.ca> wrote in message > news:1183377288.638615.122680@z28g2000prd.googlegroups.com... > > On Jul 1, 8:33 pm, "Vista" <a...@gmai.com> wrote: > >> "Robert Israel" <isr...@math.MyUniversitysInitials.ca> wrote in message > >> > >> news:rbisrael.20070702025200$77b2@news.ks.uiuc.edu... > >> > >> > >> > >> > "Vista" <a...@gmai.com> writes: > >> > >> >> Hi all, > >> > >> >> I am facing a series for which I would like to obtain the sum. It > >> >> looks > >> >> like > >> >> the following > >> > >> >> I=sum((-1)^k*a_k*b_k, k from 0 to 1000), > >> > >> >> where a_k's involve binomial coeffcients at order roughly linear with > >> >> > >> >> the > >> >> growth of k. Hence a_k's can be extremely large, beyond the > >> >> capability > >> >> of > >> >> super computers; > >> > >> > What do you think "the capability of super computers" is? Running > >> > something like Maple, even a very ordinary computer can handle some > >> > pretty large numbers. Are you talking about billions of digits? > >> > >> Robert, > >> > >> Thank about 1000!/500!/500!, > > > > No problem: Maple gets (almost immediately after pressing the 'enter' > > key): > > > > n:=1000!/500!/500!; > > n := 27028824094543656951561469362597527549615200844654828700739\ > > 2875106625428705522193898612483924502370165362606085021546\ > > 1048022097500506799175498942196995184754236654842637517333\ > > 5616246407973788734436457416111949760457104498575628788051\ > > 4600994219426752366915856603136862602484428109296905863799\ > > 821216320 > > In the version I have (Maple 9.5) the limit is 500,000 decimal digits. > > I don't know if this has been extended in newer versions. > > > > R.G. Vickson > > > > Try doing it millions of times.for count from 1 to 1000000 do n:= 1000!/500!/500! end do: takes about 205 seconds of CPU time on my computer (Maple 11 Classic, Windows XP, Pentium 4, 3GHz). -- Robert Israel israel@math.MyUniversitysInitials.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2
