Hi
I guess I need to revisit my maths lessons.Thank you for correcting me.
thanks,rakesh
> From: d...@hashcollision.org
> Date: Sat, 8 Feb 2014 00:20:19 -0800
> Subject: Re: [Tutor] learning recursion
> To: rakeshsharm...@hotmail.com
> CC: da...@davea.name; tutor@python.org
>
> On Fri, Feb 7, 2014 at 9:05 PM, rakesh sharma
> <rakeshsharm...@hotmail.com> wrote:
> > Hi
> >
> > Shouldn't your code be like this
> >
> > def fib(n):
> > if n==0:
> > return 0
> > else:
> > return n + fib(n-1)
>
>
> Hi Rakesh,
>
> Unfortunately, no, because this computes a slightly different
> function: the triangular numbers! :P
>
>
> That is, your function above is an implementation for the sum:
>
> 0 + 1 + 2 + ... + n
>
> It's also known as a "Gauss sum".
>
>
> ##################################################################
>
> [Tangent ahead. Skip if you're not interested.]
>
> As a very tangent note, it's good for us programmers to know about
> this function, because it shows up in some common places. For
> example, it occurs when we try to figure out approximately how long it
> takes to concatenate a bunch of strings in a naive way.
>
> Imagine the following artificial scenario:
>
> #############################
> long_string = ""
> for n in range(1000):
> long_string = long_string + "X"
> #############################
>
> where we're building up a large string with repeated concatenations.
>
> Does this look bad to you? It should! The string concatenation
> operation takes time that's proportional to the size of the string
> we're building up. If we do the above, with _repeated_ string
> concatenation, going through the whole loop will cost, altogether,
> something on the order of:
>
> 0 + 1 + 2 + ... + 1000
>
> elementary operations, representing the first, second, ... and
> thousandth time through that loop.
>
> And if you know your Gauss sum, this sum can be quickly computed
> without having to do each individual addition:
>
> 0 + 1 + 2 + ... + 1000
> = (1000 * 1001) / 2
> = 500500
>
> which is a fairly big number.
>
> In general:
>
> 0 + 1 + 2 + ... + n
> = n * (n+1) / 2
>
> In practice, this means for us programmers that if we're going to
> build up a large string in parts, doing repeated string concatenation
> is not the right approach as it means we're doing things in quadratic
> time. It's better to build up a list of strings, and then do the
> concatenation all at once, avoiding the repeating rebuilding of a
> larger and larger string:
>
> #############################
> long_string_chunks = []
> for n in range(1000):
> long_string_chunks.append("X")
> long_string = "".join(long_string_chunks)
> #############################
>
> where the "".join(...) part, having been implemented well, and knowing
> all the long_string_chunk elements, can do the string concatenation in
> one single, efficient pass.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
