On Tuesday 17 August 2010 17:33:15, Sebastian Fischer wrote:
> > BTW, what sort of memory usage are we talking about here?
> ./calcfib 1 +RTS -s
> 451,876,020 bytes allocated in the heap
>10,376 bytes copied during GC
>19,530,184 bytes maximum res
Sebastian Fischer wrote:
>..
>Interesting. It uses the same amount of memory but is faster probably because
>it allocates less.
>
>But I prefer programs for people to read over programs for computers to
>execute and I have a hard time to verify that your algorithm computes
According to:
Hi John,
You could try: [...]
It allocates less and has a smaller maximum residency: (ghc
6.12.2,windows 7 64)
292,381,520 bytes allocated in the heap
13,020,308 bytes maximum residency (8 sample(s))
99 MB total memory in use (9 MB lost due to
fragmentation)
MUT
Sebastian Fischer wrote:
>>BTW, what sort of memory usage are we talking about here?
>
>I was referring to the memory usage of this program
>
>import System.Environment
>import Data.Numbers.Fibonacci
>
>main :: IO ()
>main = do n <- (read . head) `fmap` getArgs
> (fib
On Aug 17, 2010, at 6:39 PM, Roel van Dijk wrote:
>> 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 e
Daniel Fischer wrote:
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 automatic
BTW, what sort of memory usage are we talking about here?
I was referring to the memory usage of this program
import System.Environment
import Data.Numbers.Fibonacci
main :: IO ()
main = do n <- (read . head) `fmap` getArgs
(fib n :: Integer) `seq` return ()
comp
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 you
Sebastian Fischer 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 w
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 num
On Aug 17, 2010, at 12:33 AM, Jason Dagit wrote:
So next I would use heap profiling to find out where and what type
of data the calculation is using.
I did.
I would do heap profiling and look at the types.
All retained data is of type ARR_WORDS. Retainer profiling shows that
the majorit
On Tue, Aug 17, 2010 at 3:53 AM, Richard O'Keefe 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).
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
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 wrote:
> On Mon, Aug 16, 2010 at 1:37 PM, Andrew Coppin
> wrote:
> >
> > This neatly leads us back to my second assertion: In all my years of
> >
On Mon, Aug 16, 2010 at 9:00 AM, Sebastian Fischer <
s...@informatik.uni-kiel.de> wrote:
> [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.
>
>
On Mon, Aug 16, 2010 at 1:37 PM, Andrew Coppin
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 thin
Roel van Dijk wrote:
On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
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
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
[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
[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/
On Monday 16 August 2010 14:37:34, Roel van Dijk wrote:
> On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
>
> 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 bi
On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
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 fi
First of all, thanks to the people who responded :)
On Sat, Aug 14, 2010 at 17:49, Christopher Lane Hinson <
l...@downstairspeople.org> wrote:
>
> On Sat, 14 Aug 2010, Tako Schotanus wrote:
>
> I was reading this article:
>>
>>
>> http://scienceblogs.com/goodmath/2009/11/writing_basic_functions_
>
> 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.)
>
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 eve
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,
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 t
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))
Very interesting stuff for somebody who comes from an imperative world of
course.
But then I re
27 matches
Mail list logo
