I was reading this article: And came to the part where it shows: > fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist)) Very interesting stuff for somebody who comes from an imperative world of course. But then I read that "Once it's been referenced, then the list up to where you looked is concrete - the computations won't be repeated."
and I started wondering how that works. Because this seems to mean that functions could have unknown (to the caller) memory requirements.
How does one, programming in Haskell, keep that in check? And when does that memory get reclaimed? Cheers,
-Tako _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Tako Schotanus wrote:
> > fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist)) > > > Very interesting stuff for somebody who comes from an imperative world > of course. Oh yes, that old chestnut. There's a page on the wiki somewhere with a whole collection of these cryptic one-liners - Pascal's triangle, the prime numbers, the Fibonacci numbers, etc. > But then I read that "Once it's been referenced, then the list up to > where you looked is concrete - the computations /won't/ be repeated." > and I started wondering how that works. fiblist is a global variable. It points to a list calculation expression. When a list cell is calculated, the calculation node is overwritten with the result of the calculation. When you access the list, you look at each cell; if it's already done, you just use it. If it's not done, execute it and then use it. (How it actually works below that is a problem for the runtime engine to figure out, and varies by Haskell implementation. For example, GHC uses the spineless tagless G-machine.) > Because this seems to mean that functions could have unknown (to the > caller) memory requirements. Yes. > How does one, programming in Haskell, keep that in check? ...and here begins an entire textbook that nobody has published yet. > And when does that memory get reclaimed? It's called "garbage collection". The memory is reclaimed when it becomes unreachable becuase there are no pointers to it left. In the example above, fiblist is a global variable, so the answer to "when does it get freed?" would be "never". (I believe it's called a CAF leak.) Whether this is very cool or a major performance issue depends on your point of view; you're trading space for time. (Then again, the Fibonacci numbers can be computed in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so this is obviously example code.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Tako Schotanus
On Sat, 14 Aug 2010, Tako Schotanus wrote: > I was reading this article: > > http://scienceblogs.com/goodmath/2009/11/writing_basic_functions_in_has.php > > And came to the part where it shows: > > > > fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist)) > > But then I read that "Once it's been referenced, then the list up to where you looked is concrete - the > computations won't be repeated." It is so implemented. If you *really* wanted a weak reference that could be garbage collected and rebuilt (you don't), it could be made to happen. > and I started wondering how that works. > Because this seems to mean that functions could have unknown (to the caller) memory requirements. This is true in any programming language or runtime. Nothing special has happened: you could implement the same thing in C/C++/Java/Python, but it would take 10-100 lines of code. > How does one, programming in Haskell, keep that in check? > And when does that memory get reclaimed? Haskell is garbage collected, as soon as the fiblist is not longer reachable, and the runtime wants to reclaim the memory, it will. If fiblist is a top-level declaration it will always be reachable. Friendly! --Lane _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Andrew Coppin
Is that actually true? I've heard lots of references to this, but I'm not sure it is true. Sure, it's harder for it to get collected when everyone can potentially access it, but the mechanisms for checking who holds pointers to a value are still valid for CAFS, and collection can still work on them, I think. The commentary at http://is.gd/ehEuL seems to suggest that CAFs can be garbage collected, too.
My apologies for confusing the issue, if this is not correct, though! Dan
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Christopher Lane Hinson
First of all, thanks to the people who responded :)
On Sat, Aug 14, 2010 at 17:49, Christopher Lane Hinson <[hidden email]> wrote:
I understand, if you don't want to keep the memory tied up you either define the reference locally or you use another algorithm.
Sure, although the memory use would normally be more obvious and it would actually be more work to make the result globally permanent.
(the difference between the 10 lines and the 100 lines you refer to probably)
Ok, makes sense. Just to make this clear, I'm not complaining nor suggesting there is anything wrong with the way Haskell does things (minds immeasurably superior to mine working on this stuff, I'm not going to pretend to know better), it's just one of those "surprises" for somebody who has no experience yet with Haskell.
Thanks, -Tako _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Andrew Coppin
On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
<[hidden email]> wrote: > (Then again, the Fibonacci numbers can be computed > in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so > this is obviously example code.) A bit off-topic, but I don't think there exists a function that computes fibonacci numbers in O(1) time. There exists a closed-form expression to calculate the nth Fibonacci number, but the complexity of that expression is not O(1): phi = (1 + sqrt 5) / 2 fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 The use of (**) should make the complexity at least O(n). Please correct me if I'm wrong (or sloppy). Regards, Roel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Monday 16 August 2010 14:37:34, Roel van Dijk wrote:
> On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin > > <[hidden email]> wrote: > > (Then again, the Fibonacci numbers can be computed > > in O(1) time, and nobody ever needs Fibonacci numbers in the first > > place, so this is obviously example code.) > > A bit off-topic, but I don't think there exists a function that > computes fibonacci numbers in O(1) time. There exists a closed-form > expression to calculate the nth Fibonacci number, but the complexity > of that expression is not O(1): > > phi = (1 + sqrt 5) / 2 > fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 > > The use of (**) should make the complexity at least O(n). Using Double for phi and n, that expression is calculated in constant time. If you use (^) or (^^) instead of (**) and use Int [or Integer and neglect the compexity of Integer arithmetic, assuming additions and divisions of Integers to be O(1)] for n, it's O(log n). However, whether using (**), (^) or (^^), with Double for phi, that formula gives wrong results even for rather small n (> 70 resp. > 75). You can calculate the n-th Fibonacci number in O(log n) steps using Integer arithmetic to get correct results. Multiplying two Integers with k bits takes O(k^(1+ x)) with 0 < x <= 1, the exact value of x depends on the used algorithm of course. I don't remember what's the best found so far, but x < 0.5 is reached. Since the abovementioned O(log n) steps algorithm includes multiplication of Integers with Theta(n) bits, its complexity is O(n^(1 + y)) for some y >= x. > Please correct me if I'm wrong (or sloppy). > > Regards, > Roel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
[continuing off topic]
On Aug 16, 2010, at 3:13 PM, Daniel Fischer wrote: > You can calculate the n-th Fibonacci number in O(log n) steps using > Integer > arithmetic to get correct results. Yes, I was delighted when I saw this for the frist time. It works be computing /1 1\^n \1 0/ (This is meant to be a matrix to the nth power) by repeated squaring. Wikipedia knows the details: http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form My Haskell implementation of this approach is on Hackage: http://hackage.haskell.org/package/fibonacci and github: http://github.com/sebfisch/fibonacci/blob/master/Data/Numbers/Fibonacci.hs With this implementation, printing the result of a call to, say fib 100000000 takes *much* longer than computing it. [almost on topic again] I am a bit concerned about the memory usage. If you know how to fix it, please send me patches (ideally via github)! Cheers, Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
[CC-ing café again]
On Aug 16, 2010, at 5:52 PM, Daniel Fischer wrote: >> I am a bit concerned about the memory usage. > > Of your implementation of the matrix power algorithm? Yes. > Making the fields of Matrix strict should help: > > data Matrix a = Matrix !a !a !a Making all fields strict makes memory usage worse. When making only the first field strict, memory usage hardly differs (from the current implementation without strictness annotations). Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Sebastian Fischer
Since we're off-topic...
Any sequence of numbers given by a linear recurrence equation with constant coefficients can be computed quickly using asymptotically efficient matrix operations. In fact, the code to do this can be derived automatically from the recurrence itself. Here is what you get for Fibonacci (using Maple): > re := {fib(n+2) = fib(n+1) + fib(n)}; inits := {fib(0) = 1, fib(1) = 1}; {fib(n + 2) = fib(n + 1) + fib(n)} {fib(0) = 1, fib(1) = 1} > gfun[rectoproc](re union inits, fib(n)); proc (n) local i1, loc0, loc1, loc2, tmp2, tmp1, i2; if n <= 44 then loc0 := 1; loc1 := 1; if n < 0 then error "index must be %1 or greater", 0 elif n = 0 then return loc0 elif n = 1 then return loc1 end if; for i1 to n-1 do loc2 := loc0+loc1; loc0 := loc1; loc1 := loc2 end do; loc1 else tmp2 := Matrix(2, 2, {(1, 1) = 1, (1, 2) = 1, (2, 1) = 1, (2, 2) = 0}); tmp1 := Vector(2, {(1) = 1, (2) = 1}); i2 := convert(n-1, base, 2); if i2[1] = 1 then tmp1 := Vector(2, {(1) = 2, (2) = 1}) end if; for i1 in subsop(1 = (), i2) do tmp2 := LinearAlgebra:-MatrixMatrixMultiply(tmp2, tmp2); if i1 = 1 then tmp1 := LinearAlgebra:-MatrixVectorMultiply(tmp2, tmp1) end if end do; tmp1[1] end if end proc Direct computation is done for small n, and then asymptotically fast linear algebra is used for larger n. This should be a nice Template Haskell exercise. Jacques Sebastian Fischer wrote: > [continuing off topic] > > On Aug 16, 2010, at 3:13 PM, Daniel Fischer wrote: > >> You can calculate the n-th Fibonacci number in O(log n) steps using >> Integer >> arithmetic to get correct results. > > Yes, I was delighted when I saw this for the frist time. It works be > computing > > /1 1\^n > \1 0/ > > (This is meant to be a matrix to the nth power) by repeated squaring. > Wikipedia knows the details: > > http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form > > My Haskell implementation of this approach is on Hackage: > > http://hackage.haskell.org/package/fibonacci > > and github: > > > http://github.com/sebfisch/fibonacci/blob/master/Data/Numbers/Fibonacci.hs > > > With this implementation, printing the result of a call to, say > > fib 100000000 > > takes *much* longer than computing it. > > [almost on topic again] > > I am a bit concerned about the memory usage. If you know how to fix > it, please send me patches (ideally via github)! > > Cheers, > Sebastian > > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Roel van Dijk-3
Roel van Dijk wrote:
> On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin > <[hidden email]> wrote: > >> (Then again, the Fibonacci numbers can be computed >> in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so >> this is obviously example code.) >> > > A bit off-topic, but I don't think there exists a function that > computes fibonacci numbers in O(1) time. There exists a closed-form > expression to calculate the nth Fibonacci number, but the complexity > of that expression is not O(1): > > phi = (1 + sqrt 5) / 2 > fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 > > The use of (**) should make the complexity at least O(n). Please > correct me if I'm wrong (or sloppy). > This depends on your definition of "operation". As somebody else pointed out, if you're only dealing with limited-precision arithmetic, you can probably consider all the arithmetic operations to be O(1), in which case the Nth Fibonacci number is O(1). Only if you're dealing with utterly huge numbers do you need to even care about how long it takes to add two numbers. This neatly leads us back to my second assertion: In all my years of computer programming, I've never seen one single program that actually *needs* the Fibonacci numbers in the first place (let alone in arbitrary-precision). _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Mon, Aug 16, 2010 at 1:37 PM, Andrew Coppin
<[hidden email]> wrote: > > This neatly leads us back to my second assertion: In all my years of > computer programming, I've never seen one single program that actually > *needs* the Fibonacci numbers in the first place (let alone in > arbitrary-precision). > I think there are variants on AVL trees that use something related to a Fibonacci sequence for balancing. I don't remember the details, though. Antoine _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Sebastian Fischer
On Mon, Aug 16, 2010 at 9:00 AM, Sebastian Fischer <[hidden email]> wrote:
[CC-ing café again] That's interesting. So next I would use heap profiling to find out where and what type of data the calculation is using. I would do heap profiling and look at the types. The strictness above should when there are lots of thunks in memory for computing the values in the Matrix.
To get started at this task, I recommend the chapter on performance from Real-World Haskell:
I'd love to hear what you learn as I probably won't have time to poke at it. Jason _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Antoine Latter-2
There's a Fibonacci Heap: http://en.wikipedia.org/wiki/Fibonacci_heap
Not sure what else though :)
On Mon, Aug 16, 2010 at 11:14 PM, Antoine Latter <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Roel van Dijk-3
On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote: > > phi = (1 + sqrt 5) / 2 > fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 > > The use of (**) should make the complexity at least O(n). Please > correct me if I'm wrong (or sloppy). Using the classic x**0 = 1 x**1 = x x**(2k+0) = (x**2)**k k > 0 x**(2k+1) = (x**2)**k + x k > 1 powers of smallish numbers or matrices can be computed in logarithmic time. Using x**n = exp(n*log(x)) and floating point arithmetic, the whole thing can be done in O(1) time, and the price of some inaccuracy. Using double precision arithmetic, I get fib(52) = 32951280099.0001 which is clearly wrong. Truncation will save you, up to fib(72) = 498454011879265.1875 which is wrong in the units place. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Tue, Aug 17, 2010 at 3:53 AM, Richard O'Keefe <[hidden email]> wrote:
> On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote: >> >> phi = (1 + sqrt 5) / 2 >> fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5 >> >> The use of (**) should make the complexity at least O(n). Please >> correct me if I'm wrong (or sloppy). > > Using the classic > x**0 = 1 > x**1 = x > x**(2k+0) = (x**2)**k k > 0 > x**(2k+1) = (x**2)**k + x k > 1 > powers of smallish numbers or matrices can be computed in logarithmic > time. calculates Fibonacci numbers in O(log n) time. > Using x**n = exp(n*log(x)) and floating point arithmetic, > the whole thing can be done in O(1) time, and the price of > some inaccuracy. It will calculate a subset of the Fibonacci numbers in O(1) time. Thinking about it I think you can easily calculate subsets of any function in O(1) time, as long as the function is guaranteed to terminate. Simply precompute the answers and store them in an array. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Jason Dagit-2
On Aug 17, 2010, at 12:33 AM, Jason Dagit wrote:
I did.
All retained data is of type ARR_WORDS. Retainer profiling shows that the majority is retained by the cost center SYSTEM. I suspected that a strict, tail recursive version of `matrixPower` may be more efficient and implemented it: But it's worse. Still, the only retained data is of type ARR_WORDS mostly retained by SYSTEM but even more of it now. Additional bang patterns on `square` and `times` make no difference. I wonder whether the numbers in a single step of the computation occupy all the memory or whether old numbers are retained although they shouldn't be. Are (even large) Integers evaluated completely when forcing their head-normal form? Any insight of a performance guru is welcome ;) Cheers, Sebastian [off topic post scriptum] On Aug 16, 2010, at 6:03 PM, Jacques Carette wrote: Any sequence of numbers given by a linear recurrence equation with constant coefficients can be computed quickly using asymptotically efficient matrix operations. In fact, the code to do this can be derived automatically from the recurrence itself. -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Roel van Dijk-3
On Aug 17, 2010, at 8:39 AM, Roel van Dijk wrote: > That is an interesting trick. So there exists an algorithm that > calculates Fibonacci numbers in O(log n) time. This is what my program does. But it's only O(long n) if you assume multiplication is constant time (which it is not for large numbers). Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Sebastian Fischer <[hidden email]> writes:
> On Aug 17, 2010, at 8:39 AM, Roel van Dijk wrote: > >> That is an interesting trick. So there exists an algorithm that >> calculates Fibonacci numbers in O(log n) time. > > This is what my program does. But it's only O(long n) [snip] Are you getting Haskell mixed up with C or something? We don't have a "long" value type... ;-) -- Ivan Lazar Miljenovic [hidden email] IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Sebastian Fischer
On Tuesday 17 August 2010 08:59:29, Sebastian Fischer wrote:
> > I wonder whether the numbers in a single step of the computation > occupy all the memory or whether old numbers are retained although > they shouldn't be. BTW, what sort of memory usage are we talking about here? I have now tried your code and I didn't find the memory usage too extreme. Be aware that fib (10^8) requires about 70 million bits and you need several times that for the computation. If you actually print out the entire number, the String will of course require an enormous amount of memory. Concerning the effect of strictifying, at least part of it is due to the fact that with a strict matrix, you need to make a few more multiplications of large Integers, those take time and the results occupy more space than the thunks. Considering that the recursion isn't deep (you simply don't have the memory to calculate fib (2^64)), laziness hasn't the chance to cause a space leak here, so bangifying doesn't help. > Are (even large) Integers evaluated completely when > forcing their head-normal form? Yes, when you force the weak head normal form of an Integer, it is completely evaluated. > > Any insight of a performance guru is welcome ;) > > Cheers, > Sebastian > > [off topic post scriptum] > > On Aug 16, 2010, at 6:03 PM, Jacques Carette wrote: > > Any sequence of numbers given by a linear recurrence equation with > > constant coefficients can be computed quickly using asymptotically > > efficient matrix operations. In fact, the code to do this can be > > derived automatically from the recurrence itself. > > This is neat. Is it always M^n for some matrix M? How does it work? Yes, it's always M^n. If the relation is a_n = c_1*a_(n-1) + ... + c_k*a_(n-k) you have the k×k matrix c_1 c_2 ... c_(k-1) c_k 1 0 ... 0 0 0 1 0 ... 0 0 0 0 1 0 ... 0 0 ... 0 1 0 0 0 ... 0 0 1 0 to raise to the n-th power, multiply the resulting matrix with the vector of initial values (a_(k-1), a_(k-2), ..., a_0) and take the last component (a propos of this, your Fibonacci numbers are off by one, fib 0 = 0, fib 9 = 34, fib 10 = 55). It works because M*(a_(n-1), ..., a_(n-k)) = (c_1*a_(n-1) + ... + c_k*a_(n-k), a_(k-1), ..., a_(n-(k-1))) = (a_n, a_(n-1), ..., a_(n-(k-1))) However, for large k, this isn't particularly efficient since standard matrix multiplication is O(k^3). These matrices have a special structure that allows doing a multiplication in O(k^2). You might want to look into the Cayley-Hamilton theorem for the latter. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |