Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 5:41 AM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: Python does not automatically print all return statements. If you want it to print the intermediate values produced, you will need to add print before each return: py def fib(n): ... if n == 0: ... result = 0 ... elif n == 1: ... result = 1 ... else: ... result = fib(n-1) + fib(n-2) ... print result, # trailing comma means no newline ... return result ... py fib(3) 1 0 1 1 2 2 py fib(5) 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 5 If you want to print a list of Fibonnaci values, you need to call the function in a loop. Removing the print result line again, you can do this: py for i in range(6): ... print fib(i), ... 0 1 1 2 3 5 Thanks you Steven and others ( Dave, Chris and Terry ) , for having such good discussion on this topic and benefiting me in more than one way's. Thank you -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 12:20 AM, Rustom Mody rustompm...@gmail.com wrote: On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote: Iteration in log space. On my desktop, this calculates fib(1000) in about 9 us, fib(10) in about 5 ms, and fib(1000) in about 7 seconds. def fib(n): assert n = 0 if n == 0: return 0 a = b = x = 1 c = y = 0 n -= 1 while True: n, r = divmod(n, 2) if r == 1: x, y = x*a + y*b, x*b + y*c if n == 0: return x b, c = a*b + b*c, b*b + c*c a = b + c This is rather arcane! What are the identities used above? It's essentially the same matrix recurrence that Gregory Ewing's solution uses, but without using numpy (which doesn't support arbitrary precision AFAIK) and with a couple of optimizations. The Fibonacci recurrence can be expressed using linear algebra as: F_1 = [ 1 0 ] T = [ 1 1 ] [ 1 0 ] F_(n+1) = F_n * T I.e., given that F_n is a vector containing fib(n) and fib(n-1), multiplying by the transition matrix T results in a new vector containing fib(n+1) and fib(n). Therefore: F_n = F_1 * T ** (n-1) The code above evaluates this expression by multiplying F_1 by powers of two of T until n-1 is reached. x and y are the two elements of the result vector, which at the end of the loop are fib(n) and fib(n-1). a, b, and c are the three elements of the (symmetric) transition matrix T ** p, where p is the current power of two. The last two lines of the loop updating a, b, and c could equivalently be written as: a, b, c = a*a + b*b, a*b + b*c, b*b + c*c A little bit of algebra shows that if a = b + c before the assignment, the equality is maintained after the assignment (in fact the elements of T ** n are fib(n+1), fib(n), and fib(n-1)), so the two multiplications needed to update a can be optimized away in favor of a single addition. -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 10:24:59 PM UTC+8, Ian wrote: On Tue, Mar 24, 2015 at 12:20 AM, Rustom Mody rustompm...@gmail.com wrote: On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote: Iteration in log space. On my desktop, this calculates fib(1000) in about 9 us, fib(10) in about 5 ms, and fib(1000) in about 7 seconds. def fib(n): assert n = 0 if n == 0: return 0 a = b = x = 1 c = y = 0 n -= 1 while True: n, r = divmod(n, 2) if r == 1: x, y = x*a + y*b, x*b + y*c if n == 0: return x b, c = a*b + b*c, b*b + c*c a = b + c This is rather arcane! What are the identities used above? It's essentially the same matrix recurrence that Gregory Ewing's solution uses, but without using numpy (which doesn't support arbitrary precision AFAIK) and with a couple of optimizations. The Fibonacci recurrence can be expressed using linear algebra as: F_1 = [ 1 0 ] T = [ 1 1 ] [ 1 0 ] F_(n+1) = F_n * T I.e., given that F_n is a vector containing fib(n) and fib(n-1), multiplying by the transition matrix T results in a new vector containing fib(n+1) and fib(n). Therefore: F_n = F_1 * T ** (n-1) The code above evaluates this expression by multiplying F_1 by powers of two of T until n-1 is reached. x and y are the two elements of the result vector, which at the end of the loop are fib(n) and fib(n-1). a, b, and c are the three elements of the (symmetric) transition matrix T ** p, where p is the current power of two. The last two lines of the loop updating a, b, and c could equivalently be written as: a, b, c = a*a + b*b, a*b + b*c, b*b + c*c A little bit of algebra shows that if a = b + c before the assignment, the equality is maintained after the assignment (in fact the elements of T ** n are fib(n+1), fib(n), and fib(n-1)), so the two multiplications needed to update a can be optimized away in favor of a single addition. Well, solving a homogeneous difference equation of 2 degrees and generating the solution sequence for a particular one like the Finbnaci series is a good programming practice. A more general programming practice is to generate the solution series of an arbitrary homogeneous difference euqation of integer coefficients when a real or complex solution does exist. -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 11:50:40 AM UTC+5:30, Rustom Mody wrote: On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote: On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy wrote: Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Iteration in log space. On my desktop, this calculates fib(1000) in about 9 us, fib(10) in about 5 ms, and fib(1000) in about 7 seconds. def fib(n): assert n = 0 if n == 0: return 0 a = b = x = 1 c = y = 0 n -= 1 while True: n, r = divmod(n, 2) if r == 1: x, y = x*a + y*b, x*b + y*c if n == 0: return x b, c = a*b + b*c, b*b + c*c a = b + c This is rather arcane! What are the identities used above? Seems to be close to these (with some spices added!) f₂ₙ = (fₙ)² + 2fₙ₋₁fₙ f₂ₙ₊₁ = (fₙ)² + (fₙ₊₁)² -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 08:27 PM, Chris Angelico wrote: On Tue, Mar 24, 2015 at 11:09 AM, Dave Angel d...@davea.name wrote: Repeat to self: comment first, then write test, then write the code. Reply to self: Maybe next time. Commenting is like dieting. You can always start tomorrow. It reminds me of flow charts. One job we had to do flow charts of everything. So we worked up a system where we used physical scissors and sticky tape to paste the comments from the code onto big sheets of paper, and a secretary made them pretty. Nobody ever looked at the flow charts, but it did help discipline us to comment every branch in the (micro-)code. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote: On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy wrote: Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Iteration in log space. On my desktop, this calculates fib(1000) in about 9 us, fib(10) in about 5 ms, and fib(1000) in about 7 seconds. def fib(n): assert n = 0 if n == 0: return 0 a = b = x = 1 c = y = 0 n -= 1 while True: n, r = divmod(n, 2) if r == 1: x, y = x*a + y*b, x*b + y*c if n == 0: return x b, c = a*b + b*c, b*b + c*c a = b + c This is rather arcane! What are the identities used above? -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 6:54:20 AM UTC+8, Terry Reedy wrote: On 3/23/2015 2:44 PM, Dave Angel wrote: ## Example 2: Using recursion with caching cache = [0, 1] def fib4(n): if len(cache) = n: value = fib4(n-2) + fib4(n-1) cache.append(value) return cache[n] This one takes less than a millisecond up to n=200 or so. Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Either way, the pattern works with any matched pair of base value list and recurrence relation where f(n), n a count, depends on one or more f(k), k n. 'Matched' means that the base value list is as least as long as the maximum value of n - k. For fib, the length and max are both 2. -- Terry Jan Reedy How about adding a new type of numbers of the form: (a+sqrt(r0)+ swrt(r1))/b with proper operations, and then one can compute the Fib term directly in a field. -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
Chris Angelico wrote: Commenting is like dieting. You can always start tomorrow. I've been meaning to become a procrastinator, but I think I'll start tomorrow. In the meantime, since we seem to be having a fibbing competition, here's my contribution, that uses neither recursion nor (explicit) iteration: from numpy import array, dot a = array([[0,1],[1,1]]) b = array([0,1]) def fib(n): return reduce(dot,[a]*n+[b])[1] for i in range(10): print(fib(i)) -- Greg -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy tjre...@udel.edu wrote: Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Iteration in log space. On my desktop, this calculates fib(1000) in about 9 us, fib(10) in about 5 ms, and fib(1000) in about 7 seconds. def fib(n): assert n = 0 if n == 0: return 0 a = b = x = 1 c = y = 0 n -= 1 while True: n, r = divmod(n, 2) if r == 1: x, y = x*a + y*b, x*b + y*c if n == 0: return x b, c = a*b + b*c, b*b + c*c a = b + c list(map(fib, range(15))) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377] -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal ganesh1...@gmail.com wrote: Hello team , [root@localhost Python]# cat fibonacci-Sequence-3.py ## Example 2: Using recursion def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print fib(5) # python fibonacci-Sequence-3.py 5 what Iam I missing in the program , I was expecting 0,1,1,2,3 ? What you're doing is printing out the fifth Fibonacci number. So there are three things to note: 1) To display the entire sequence, you will need some sort of loop. 2) Your algorithm is about as hopelessly inefficient as it could possibly be, barring deliberate intent. [1] 3) You are running Python 2.x; unless you have a good reason not to, it's better to use Python 3. 4) You're running as root. Normally, something like this should be run as a regular user - it's safer that way. Err, *amongst* the things to note are such diverse elements as... etcetera, etcetera. Ahem. I would suggest rewriting this as a much more straight-forward loop; begin at the beginning, go on till you reach the point you wanted, then stop. ChrisA [1] Cue the demonstration of a worse version from someone's student? -- https://mail.python.org/mailman/listinfo/python-list
fibonacci series what Iam is missing ?
Hello team , [root@localhost Python]# cat fibonacci-Sequence-3.py ## Example 2: Using recursion def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print fib(5) # python fibonacci-Sequence-3.py 5 what Iam I missing in the program , I was expecting 0,1,1,2,3 ? -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 12:01 PM, Ganesh Pal wrote: Hello team , [root@localhost Python]# cat fibonacci-Sequence-3.py ## Example 2: Using recursion def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print fib(5) # python fibonacci-Sequence-3.py 5 what Iam I missing in the program , I was expecting 0,1,1,2,3 ? You're missing the loop at top-level. The function as written calculates a single value, by using recursion. While it's true that the function also calculates the lower-numbered values, it doesn't print them. Printing is (rightly) only done at the top-level, and that's where you'd need a loop. An entirely separate question is whether you can gain performance by caching intermediate values. For example, if you capture values in a list, you could potentially save a lot of time, at least for non-trivial values of n. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Mon, Mar 23, 2015 at 12:44 PM, Dave Angel da...@davea.name wrote: On 03/23/2015 12:16 PM, Chris Angelico wrote: [1] Cue the demonstration of a worse version from someone's student? I'll give you a worse version. Back in the day I had occasion to write a simple program in a language which had no add or subtract. It could only increment and decrement indices. So to simulate that: #without using any arithmetic other than increment and decrement def fib3(n): if n == 0: return 0 elif n == 1: return 1 else: a = fib3(n-1) n = n-1 b = fib3(n-1) while b 0: a,b = a+1, b-1 return a Function calls? Comparison with numbers other than 0? These are luxuries, I say! Here's a version that does without: http://progopedia.com/example/fibonacci/14/ (Note that most of that program is concerned with formatting the numbers into ASCII for output; the iterative Fibonacci calculation is just the last part of the loop.) -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 23/03/15 19:44, Dave Angel wrote: I'll give you a worse version. Back in the day I had occasion to write a simple program in a language which had no add or subtract. It could only increment and decrement indices. Oh yes, the olden days. I have not quite lived through the punch card era, but I do want to bring to your attention a recent blog post, not about Fibonacci, but about the Mandelbrot set. On an IBM 1401. Read it and count your blessings. http://www.righto.com/2015/03/12-minute-mandelbrot-fractals-on-50.html Imagine the 123 pass python interpreter for this device... chl -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 3:16 AM, Dave Angel da...@davea.name wrote: An entirely separate question is whether you can gain performance by caching intermediate values. For example, if you capture values in a list, you could potentially save a lot of time, at least for non-trivial values of n. If you take a step back and seek to print a sequence of Fibonacci numbers, rather than calculating specific ones based on their indices, then you don't even need to consider caching. As soon as you've printed out a number, you move right along. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 1:00:11 AM UTC+8, Chris Angelico wrote: On Tue, Mar 24, 2015 at 3:16 AM, Dave Angel da...@davea.name wrote: An entirely separate question is whether you can gain performance by caching intermediate values. For example, if you capture values in a list, you could potentially save a lot of time, at least for non-trivial values of n. If you take a step back and seek to print a sequence of Fibonacci numbers, rather than calculating specific ones based on their indices, then you don't even need to consider caching. As soon as you've printed out a number, you move right along. ChrisA Well, the good part is that the python version can compute the right result for a much larger n in fib(n). -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 12:16 PM, Chris Angelico wrote: On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal ganesh1...@gmail.com wrote: Hello team , [root@localhost Python]# cat fibonacci-Sequence-3.py ## Example 2: Using recursion def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print fib(5) # python fibonacci-Sequence-3.py 5 what Iam I missing in the program , I was expecting 0,1,1,2,3 ? What you're doing is printing out the fifth Fibonacci number. So there are three things to note: 1) To display the entire sequence, you will need some sort of loop. 2) Your algorithm is about as hopelessly inefficient as it could possibly be, barring deliberate intent. [1] 3) You are running Python 2.x; unless you have a good reason not to, it's better to use Python 3. 4) You're running as root. Normally, something like this should be run as a regular user - it's safer that way. Err, *amongst* the things to note are such diverse elements as... etcetera, etcetera. Ahem. I would suggest rewriting this as a much more straight-forward loop; begin at the beginning, go on till you reach the point you wanted, then stop. ChrisA [1] Cue the demonstration of a worse version from someone's student? I'll give you a worse version. Back in the day I had occasion to write a simple program in a language which had no add or subtract. It could only increment and decrement indices. So to simulate that: #without using any arithmetic other than increment and decrement def fib3(n): if n == 0: return 0 elif n == 1: return 1 else: a = fib3(n-1) n = n-1 b = fib3(n-1) while b 0: a,b = a+1, b-1 return a Interestingly enough that only seems to triple the time taken. I wouldn't recommend running either of these with n 34 or so. ## Example 2: Using recursion with caching cache = [0, 1] def fib4(n): if len(cache) = n: value = fib4(n-2) + fib4(n-1) cache.append(value) return cache[n] This one takes less than a millisecond up to n=200 or so. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 12:59 PM, Chris Angelico wrote: On Tue, Mar 24, 2015 at 3:16 AM, Dave Angel da...@davea.name wrote: An entirely separate question is whether you can gain performance by caching intermediate values. For example, if you capture values in a list, you could potentially save a lot of time, at least for non-trivial values of n. If you take a step back and seek to print a sequence of Fibonacci numbers, rather than calculating specific ones based on their indices, then you don't even need to consider caching. As soon as you've printed out a number, you move right along. But that's a big assumption. I assumed the comment on the function had a reasaonable meaning, that the OP assignment was to learn about recursion. If I were the instructor, I might have assigned them to print the fibonacci numbers backwards: 5 5 4 3 3 2 2 1 1 1 0 0 -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, 24 Mar 2015 03:16 am, Chris Angelico wrote about the standard recursive version of the Fibonacci series: On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal ganesh1...@gmail.com wrote: def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) 2) Your algorithm is about as hopelessly inefficient as it could possibly be, barring deliberate intent. It is pretty inefficient, but it is a good toy example of recursion. It's also a good example of how *not* to write the Fibonacci series in practice, what is mathematically straightforward is not always computationally efficient. The question is, just how inefficient is is? How many calls to `fib` are made in calling fib(n)? Answer to follow. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 05:31 PM, Carsten Lechte wrote: On 23/03/15 19:44, Dave Angel wrote: I'll give you a worse version. Back in the day I had occasion to write a simple program in a language which had no add or subtract. It could only increment and decrement indices. Oh yes, the olden days. I have not quite lived through the punch card era, but I do want to bring to your attention a recent blog post, not about Fibonacci, but about the Mandelbrot set. On an IBM 1401. Read it and count your blessings. http://www.righto.com/2015/03/12-minute-mandelbrot-fractals-on-50.html Imagine the 123 pass python interpreter for this device... Thanks for the trip down memory lane. My fondest memories from my first decade of development was microcoding an all decimal floating point package, on hardware that had a bcd alu (8 bits wide). To optimize multiply, I precalculated 2, 10, and 20 times the original values, and for a given column either added or subtracted depending on whether the multiplier digit was less than or greater than 5. (the 10 and 20 were just a half-byte shift, but it was still quicker to do it once on the multiplicand than repeatedly on the result. If I were doing it now, I'd investigate doing the multiplier in two passes, one for the odd digits and one for the even ones.) My first real assignment at that company (1973) I did use core memory, but it was outboard, in what we called a ramdisk. 8K of core memory in a suitcase-sized box, cabled to our calculator, so I could do overlays from it into main, semiconductor-based ram. The project was a satellite navigation system (to produce latitude and longitude for shipboard use) that had to run in 2k of (ROM) code space plus 1.5k of data space. While developing, code and data had to share that 1.5k, so I wrote a little overlay manager. Burning those EPROMS took about 20 minutes, so the ramdisk was really quite useful. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 07:49 PM, Chris Angelico wrote: On Tue, Mar 24, 2015 at 10:12 AM, Dave Angel da...@davea.name wrote: On the other hand, my loop makes some non-obvious assumptions, like that append is always the right place to put a new value. Yes, I had to stop and think about that one a bit. And that strongly suggests (to me, at least!) that it's comment-worthy :) It's funny. I thought of commenting it, but wanted to wait till I checked whether I could call fib+fib in the opposite order. By the time i realized they both worked fine i forgot to enter the comment. (Note; missing comment is usually not as bad as inaccurate comment) Repeat to self: comment first, then write test, then write the code. Reply to self: Maybe next time. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 10:12 AM, Dave Angel da...@davea.name wrote: On the other hand, my loop makes some non-obvious assumptions, like that append is always the right place to put a new value. Yes, I had to stop and think about that one a bit. And that strongly suggests (to me, at least!) that it's comment-worthy :) ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 11:19 AM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: It is pretty inefficient, but it is a good toy example of recursion. It's also a good example of how *not* to write the Fibonacci series in practice, what is mathematically straightforward is not always computationally efficient. The question is, just how inefficient is is? How many calls to `fib` are made in calling fib(n)? Answer to follow. Exact answer not particularly important (though fun to calculate). Practical answer: A *lot*. :) I've never thought of the mathematical definition as being inherently recursive; but as inherently sequential. Sure, you can define counting numbers based on sets (0 is the cardinality of the empty set, 1 is the cardinality of the set containing the empty set, et-set-era), but most people will define them by counting. The Fibonacci sequence is logically defined by starting somewhere and then adding to the sequence. Yes, you can define it recursively too, but it's just as easy to define it as a progression. (Conversely, the squares *can* be defined as a progression - you add the next odd number to the previous square - but they're more logically defined by their indices. Some work better one way, some the other way.) Of course, mathematics works quite happily with infinity. You can construct infinite sequences and do arithmetic on them, which computers have a lot of trouble with. You can define anything in terms of anything, no matter how long a chain of definitions it takes. And above all, you can reduce problems to previously-solved states, which implies that mathematics has a concept of caching. :) ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 06:53 PM, Terry Reedy wrote: On 3/23/2015 2:44 PM, Dave Angel wrote: ## Example 2: Using recursion with caching cache = [0, 1] def fib4(n): if len(cache) = n: value = fib4(n-2) + fib4(n-1) cache.append(value) return cache[n] This one takes less than a millisecond up to n=200 or so. Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Either way, the pattern works with any matched pair of base value list and recurrence relation where f(n), n a count, depends on one or more f(k), k n. 'Matched' means that the base value list is as least as long as the maximum value of n - k. For fib, the length and max are both 2. I almost used a default value as a cache, but didn't want to confuse the OP. Also, your present code does not use recursion, so probably wouldn't make the prof happy. On the other hand, my loop makes some non-obvious assumptions, like that append is always the right place to put a new value. I knew it'd work, since fib calls itself with n-1. But it wouldn't directly work if the function had recursed on n-2 and n-3. Yours would. I prefer iteration, but I still figure this is an assignment. -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, 24 Mar 2015 03:01 am, Ganesh Pal wrote: Hello team , [root@localhost Python]# cat fibonacci-Sequence-3.py ## Example 2: Using recursion def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) print fib(5) # python fibonacci-Sequence-3.py 5 what Iam I missing in the program , I was expecting 0,1,1,2,3 ? Python does not automatically print all return statements. If you want it to print the intermediate values produced, you will need to add print before each return: py def fib(n): ... if n == 0: ... result = 0 ... elif n == 1: ... result = 1 ... else: ... result = fib(n-1) + fib(n-2) ... print result, # trailing comma means no newline ... return result ... py fib(3) 1 0 1 1 2 2 py fib(5) 1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 5 If you want to print a list of Fibonnaci values, you need to call the function in a loop. Removing the print result line again, you can do this: py for i in range(6): ... print fib(i), ... 0 1 1 2 3 5 -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 11:09 AM, Dave Angel d...@davea.name wrote: Repeat to self: comment first, then write test, then write the code. Reply to self: Maybe next time. Commenting is like dieting. You can always start tomorrow. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
Given the standard recursive version of the Fibonacci series: def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) I asked: The question is, just how inefficient is is? How many calls to `fib` are made in calling fib(n)? The answer follows the spoiler space. Try solving the question yourself before reading the answer. * * * * * S P O I L E R S P A C E * * * * * fib(0) makes no recursive calls, so the answer for n = 0 is 1. fib(1) makes no recursive calls, so the answer for n = 1 is 1. fib(2) makes two recursive calls, fib(1) and fib(0), so the answer for n = 2 is 3. fib(3) makes two recursive calls, fib(2) and fib(1). They in turn make 3 and 1 calls each, so the answer is 5: 1 for the call to fib(3) +3 for the call to fib(2) +1 for the call to fib(1) fib(4) makes two recursive calls, fib(3) and fib(2), giving 9 calls in total: 1 for the call to fib(4) +5 for the call to fib(3) +3 for the call to fib(2) This is a recursive relationship very similar to the Fibonacci series! Let's call the function number of subroutine calls made by fib(n) L(n), for reasons which will become clear later: def L(n): if n == 0: return 1 elif n == 1: return 1 else: return L(n-1) + L(n-2) + 1 This number grows significantly faster than the Fibonacci series itself. Here are the first few values: --- - nFib(n)L(n) --- - 00 1 11 1 21 3 32 5 43 9 55 15 68 25 71341 82167 934109 10 55177 11 89289 12 144 465 ... 35 9227465 29860703 --- - L(n) is in fact a standard mathematical sequence, the nth Leonardo Number. What if we ask the same question of Leo, that is, how many function calls does Leo(n) make? The number of function calls needed to calculate the nth Leonardo Number using this recursive algorithm is ... the nth Leonardo Number. So in a way, we need not actually bother calculating anything, but just count the number of function calls, throwing away the intermediate results! I think that is rather neat. http://en.wikipedia.org/wiki/Leonardo_number -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 3/23/2015 2:44 PM, Dave Angel wrote: ## Example 2: Using recursion with caching cache = [0, 1] def fib4(n): if len(cache) = n: value = fib4(n-2) + fib4(n-1) cache.append(value) return cache[n] This one takes less than a millisecond up to n=200 or so. Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Either way, the pattern works with any matched pair of base value list and recurrence relation where f(n), n a count, depends on one or more f(k), k n. 'Matched' means that the base value list is as least as long as the maximum value of n - k. For fib, the length and max are both 2. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 03/23/2015 08:19 PM, Steven D'Aprano wrote: On Tue, 24 Mar 2015 03:16 am, Chris Angelico wrote about the standard recursive version of the Fibonacci series: On Tue, Mar 24, 2015 at 3:01 AM, Ganesh Pal ganesh1...@gmail.com wrote: def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) 2) Your algorithm is about as hopelessly inefficient as it could possibly be, barring deliberate intent. It is pretty inefficient, but it is a good toy example of recursion. It's also a good example of how *not* to write the Fibonacci series in practice, what is mathematically straightforward is not always computationally efficient. The question is, just how inefficient is is? How many calls to `fib` are made in calling fib(n)? Answer to follow. 0 1 1 1 2 3 3 5 4 9 5 15 6 25 7 41 8 67 9 109 10 177 11 287 12 465 13 753 14 1219 -- DaveA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On 3/23/2015 7:12 PM, Dave Angel wrote: On 03/23/2015 06:53 PM, Terry Reedy wrote: Iteration with caching, using a mutable default arg to keep the cache private and the function self-contained. This should be faster. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' for k in range(len(_cache), n+1): _cache.append(_cache[k-2] + _cache[k-1]) return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 Either way, the pattern works with any matched pair of base value list and recurrence relation where f(n), n a count, depends on one or more f(k), k n. 'Matched' means that the base value list is as least as long as the maximum value of n - k. For fib, the length and max are both 2. I almost used a default value as a cache, but didn't want to confuse the OP. Also, your present code does not use recursion, so probably wouldn't make the prof happy. I did not read the initial posts with that requirement. Iteration is easily converted to tail recursion, which is definitely the way to calculate recurrences with more than one term without a full cache. On the other hand, my loop makes some non-obvious assumptions, like that append is always the right place to put a new value. I knew it'd work, since fib calls itself with n-1. But it wouldn't directly work if the function had recursed on n-2 and n-3. Yours would. I prefer iteration, but I still figure this is an assignment. def fib(n, _cache=[0,1]): '''Return fibonacci(n). _cache is initialized with base values and augmented as needed. ''' k = len(_cache) # min n without a value in cache if k = n: _cache.append(_cache[k-2] + _cache[k-1]) return fib(n) else: return _cache[n] print(fib(1), fib(3), fib(6), fib(5)) # 1 2 8 5 If one does not like the append as a statement, and prefer it as part of the return expression, this works too. def fib(n, _dummy=None, _cache=[0,1]): k = len(_cache) return (fib(n, _cache.append(_cache[k-2] + _cache[k-1]), _cache) if k = n else _cache[n]) However, I am not a fan of puritanical functionalism. -- Terry Jan Reedy -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote: I've never thought of the mathematical definition as being inherently recursive; but as inherently sequential. Sure, you can define counting numbers based on sets (0 is the cardinality of the empty set, 1 is the cardinality of the set containing the empty set, et-set-era), but most people will define them by counting. The Fibonacci sequence is logically defined by starting somewhere and then adding to the sequence. Yes, you can define it recursively too, but it's just as easy to define it as a progression. But what are you adding? You're not adding a constant or simple expression each time, but a previous term of the series. That's recursion. The mathematical term is that it is a recurrence relation, and is usually written: F[n] = F[n-1] + F[n-2] where F[x] means F subscript x. In English: the nth Fibonacci number is equal to the sum of the previous two Fibonacci numbers (with the first and second given by 0 and 1 respectively). That's inherently recursive: the definition is given in terms of itself. http://en.wikipedia.org/wiki/Fibonacci_number There is at least one closed-form (non-recursive) formula for Fibonacci numbers, Binet's Formula: F[n] = (φ**n - ψ**n)/sqrt(5) where: φ is the Golden Ratio (1+sqrt(5))/2 ψ = 1-φ but that's not how the Fibonacci numbers are defined, or why they are interesting. The Fibonacci numbers are just a special case for a more mathematically interesting family of recurrence relations, the Lucas sequences. (Aside: due to floating point rounding, Binet's Formula will give inaccurate results for large enough values of n. With n=77 it is off by 1.) The important thing here is that all these associated sequences -- Fibonacci numbers, Pell numbers, Leonardo numbers, Perrin numbers and others -- are defined as recurrences, i.e. recursively. But that doesn't necessarily make recursion the best way to implement it. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 8:33:24 AM UTC+5:30, Chris Angelico wrote: On Tue, Mar 24, 2015 at 12:52 PM, Steven D'Aprano wrote: On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote: I've never thought of the mathematical definition as being inherently recursive; but as inherently sequential. Sure, you can define counting numbers based on sets (0 is the cardinality of the empty set, 1 is the cardinality of the set containing the empty set, et-set-era), but most people will define them by counting. The Fibonacci sequence is logically defined by starting somewhere and then adding to the sequence. Yes, you can define it recursively too, but it's just as easy to define it as a progression. But what are you adding? You're not adding a constant or simple expression each time, but a previous term of the series. That's recursion. That's true, if you are defining the Nth Fibonacci number. But if you're defining the Fibonacci sequence, then it's self-referential, but not double-recursive as it is in the naive functional definition. Here are two different approaches for 2nd order recurrence to 1st order: # input recursion def fibir(n, a=0, b=1): return ( a if n==0 else b if n==1 else fibir(n-1, b, a+b) ) # Output recursion def fibor(n): if n==0: return (0,1) else: (a,b) = fibor(n-1) return (b,a+b) And that's where the problem comes from; What problem? I see the problem starting with the fact that we treat a math-defn as a computational one. it's pretty easy to handle a single level of recursion by converting it to tail recursion, then trivially converting that to iteration; double recursion is harder to handle. The cache-append solution that Terry posted is basically evaluate the Fibonacci sequence up as far as we need it, then return that number, which is what I'm talking about. Mathematics doesn't like defining sequences, except by defining functions, and so it has to convert the concept of defining the Fibonacci sequence into defining a function F(N) which returns the Nth Fibonacci number, and that's where the double recursion comes from. It's not an inherent part of the sequence, which is, uhh, sequential. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 8:33:24 AM UTC+5:30, Chris Angelico wrote: Mathematics doesn't like defining sequences, except by defining functions, and so it has to convert the concept of defining the Fibonacci sequence into defining a function F(N) which returns the Nth Fibonacci number, and that's where the double recursion comes from. It's not an inherent part of the sequence, which is, uhh, sequential. Here is a pure 'recursive-data' definition of fib. [Of course assuming you can buy that generators are data not functions] == from itertools import tee def fib(): yield 0 yield 1 f, fn = tee(fib()) next(fn) yield from (x+y for (x,y) in zip(f, fn)) The fact that this is data may be more clear if you see it as a rendering (uglification) of the Haskell list-definition fibs = 0 : 1 : zipWith (+) fibs (tail fibs) -- https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tuesday, March 24, 2015 at 7:22:25 AM UTC+5:30, Steven D'Aprano wrote:
On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:
I've never thought of the mathematical definition as being inherently
recursive; but as inherently sequential. Sure, you can define counting
numbers based on sets (0 is the cardinality of the empty set, 1 is the
cardinality of the set containing the empty set, et-set-era), but most
people will define them by counting. The Fibonacci sequence is
logically defined by starting somewhere and then adding to the
sequence. Yes, you can define it recursively too, but it's just as
easy to define it as a progression.
But what are you adding? You're not adding a constant or simple expression
each time, but a previous term of the series. That's recursion. The
mathematical term is that it is a recurrence relation, and is usually
written:
F[n] = F[n-1] + F[n-2]
where F[x] means F subscript x. In English: the nth Fibonacci number is
equal to the sum of the previous two Fibonacci numbers (with the first and
second given by 0 and 1 respectively). That's inherently recursive: the
definition is given in terms of itself.
http://en.wikipedia.org/wiki/Fibonacci_number
There is at least one closed-form (non-recursive) formula for Fibonacci
numbers, Binet's Formula:
F[n] = (φ**n - ψ**n)/sqrt(5)
where:
φ is the Golden Ratio (1+sqrt(5))/2
ψ = 1-φ
but that's not how the Fibonacci numbers are defined, or why they are
interesting. The Fibonacci numbers are just a special case for a more
mathematically interesting family of recurrence relations, the Lucas
sequences.
(Aside: due to floating point rounding, Binet's Formula will give inaccurate
results for large enough values of n. With n=77 it is off by 1.)
The important thing here is that all these associated sequences -- Fibonacci
numbers, Pell numbers, Leonardo numbers, Perrin numbers and others -- are
defined as recurrences, i.e. recursively. But that doesn't necessarily make
recursion the best way to implement it.
I think (guess) Chris is saying that recurrence relations are somehow 'less
recursive' than recursion?
I find that view weird... though I should admit to making a similar one:
Recursion is not hard; its recursion mixed with imperative programming that's
a mismatch and therefore seems hard:
http://blog.languager.org/2012/10/functional-programming-lost-booty.html
The other unsatisfactory aspect of above discussion is that it seems to assume
recursion = recursive function
What about recursive data? eg the C list definition: ??
struct node {
int elem;
struct node *next;
};
In fact that's not just recursive its mutually recursive. Becomes evident
if rewritten as
typedef struct node *nodeptr;
struct node {
int elem;
nodeptr next;
};
--
https://mail.python.org/mailman/listinfo/python-list
Re: fibonacci series what Iam is missing ?
On Tue, Mar 24, 2015 at 12:52 PM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote: I've never thought of the mathematical definition as being inherently recursive; but as inherently sequential. Sure, you can define counting numbers based on sets (0 is the cardinality of the empty set, 1 is the cardinality of the set containing the empty set, et-set-era), but most people will define them by counting. The Fibonacci sequence is logically defined by starting somewhere and then adding to the sequence. Yes, you can define it recursively too, but it's just as easy to define it as a progression. But what are you adding? You're not adding a constant or simple expression each time, but a previous term of the series. That's recursion. That's true, if you are defining the Nth Fibonacci number. But if you're defining the Fibonacci sequence, then it's self-referential, but not double-recursive as it is in the naive functional definition. And that's where the problem comes from; it's pretty easy to handle a single level of recursion by converting it to tail recursion, then trivially converting that to iteration; double recursion is harder to handle. The cache-append solution that Terry posted is basically evaluate the Fibonacci sequence up as far as we need it, then return that number, which is what I'm talking about. Mathematics doesn't like defining sequences, except by defining functions, and so it has to convert the concept of defining the Fibonacci sequence into defining a function F(N) which returns the Nth Fibonacci number, and that's where the double recursion comes from. It's not an inherent part of the sequence, which is, uhh, sequential. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
