9
$\begingroup$

I know that Mathematica prefers a functional programming way but I still have some problems for the following example.
Supposing we generate a Fibonacci sequence of 10^6 elements. NestList or FoldList will be a good choice but if we use for-loop, it will be a catastrophe. For example, 

Clear[fibSeq];  
fibSeq=Table[1,{i,10^6}];  
For[i=1,i<=10^6-2,i++,fibSeq[[i+2]]=fibSeq[[i+1]]+fibSeq[[i]]]

If we evaluate this expr, the computer shall be collapsed. But I just naively think that 1 million is not a excessive number for a normal computer. So what's the reason ?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Chances are you know this already, but Fibonacci is already built-in to Mathematica, and more generally RSolve is able to symbolically evaluate the $n$th term of many types of recursive equations. However, that's probably irrelevant, as your question appears to be more aimed at the memory-management aspects of this type of computation. $\endgroup$ – DumpsterDoofus Nov 30 '14 at 22:24
27
$\begingroup$

Fibonacci numbers grow approximately exponentially. The 1,000,000th Fibonacci number is huge, it has 208,988 decimal digits. It also takes a fair amount of memory to store:

ByteCount@Fibonacci[1000000]
(* 86856 *)

This is 86 kB. Does Mathematica store huge numbers efficiently? How many bits/bytes do we need at minimum for this number? Let's calculate it:

Length@IntegerDigits[Fibonacci[1000000], 2]/8.
(* 86780.1 *)

So it seems Mathematica's internal storage is in fact very efficient.

Now how much memory would the first million Fibonacci numbers take to store? Considering that Fibonacci numbers grow approximately exponentially, the number of bits needed to store them grows approximately linearly. So a rough estimate for the storage requirements of the list is

ByteCount@Fibonacci[1000000]*1000000/2
(* 43428000000 *)

That's 43 GB (!!). If you don't have ~64 GB of RAM in your computer, it is expected that Mathematica will run out of memory during this calculation.

To sum it up, what you see is not related to your usage of For loops. In this case one million is really an excessive number unless you have a lot of memory.

I tried your code on a machine with 64 GB of RAM and it finished without problems. The memory monitor showed about 42 GB of memory usage for Mathematica.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Wow,I did't expect it. Thanks for your solutions. By the way, is it important to allocate and deallocate memory by hand in Mathematica ? And how ? Thank you. $\endgroup$ – AchillesJJ Nov 30 '14 at 17:55
  • $\begingroup$ If I export some of the intermediate data to some place else, will Mathematica deallocate those memory automatically ? $\endgroup$ – AchillesJJ Nov 30 '14 at 18:12
  • 2
    $\begingroup$ @AchillesJJ There are no pointers/references in Mathematica, so manual allocation/deallocation is neither possible, nor needed. In some languages if a is some object and you do b=a then a and b will refer to the same thing. Modifying a also modifies b and vice versa. Mathematica is not like this, b will always be a distinct copy of a, not the same object. Under the hood Mathematica uses copy on write meaning that it will in fact share the storage of these two objects until one of them is modified. $\endgroup$ – Szabolcs Nov 30 '14 at 18:12
  • $\begingroup$ @AchillesJJ My first comment was wrong (already deleted), so ignore it please. You can Clear variables to free up the associated memory. When dealing with large objects, memory can fill up quickly because Out keeps track of past results. You can Clear it after Unprotecting it. You can also limit the number of remembered results using $HistoryLength. $\endgroup$ – Szabolcs Nov 30 '14 at 18:15
  • $\begingroup$ Exporting intermediate data doesn't clear it. You can export it, then Clear it manually, then re-import it when needed. $\endgroup$ – Szabolcs Nov 30 '14 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.