About auto-compiling and performance between Do and Fold

Question

I was investigating how Fold could improve performance vs Do. I tested the code

AbsoluteTiming[
   sum = 1.0;
   inc = 1.0;
   Do[inc = inc*Sin[10.5]/i; sum = sum + Tan[inc], {i, 10^5}];
   sum]

The output is

Out[] = {2.303896, 0.105747}

I have hoped that using Fold could improve the performance:

AbsoluteTiming@ 
    Fold[{#[[1]]*Sin[10.5]/(#2 + 1), #[[2]] + Tan@#[[1]]} &,
        {Sin[10.5], 1.0}, N@Range[10^5]]

However, this code is not faster:

Out[] = {2.471189, {-5.537337857006675*10^-462146, 0.105747}}

I have some questions concerning the above example:

(1) [Partially solved. See EDIT] Why the Fold here is not faster? I thought it should have been auto-compiled and thus faster. But it didn't.

(2) [Solved. See EDIT] Here Mathematica is using precision much higher than double precision (by having number as small as 10^{-462146}). Would it be possible to set precision to boost performance? I tried SetPricision and SetAccuracy. The precision changes but it doesn't improve performance.

(3) [Solved. See Mr. Wizard's example in his answer] Another problem of Fold is that one has first to generate a long list (length 10^5 in this example). For much larger list, the Fold method may use too much memory. Is it possible to use functional way (not necessarily Fold) in a more memory-efficient way?

Thank you very much!

PS: I met this question when trying to reproduce Mr.Wizard's answer of the below thread, with some modifications. I can reproduce Wizard's result, where Fold boots the performance greatly compared with Do. But I don't understand why my above example is not as good.

Alternatives to procedural loops and iterating over lists in Mathematica

EDIT:

(a) Rojo's comment is the answer of (2): SetSystemOptions["CatchMachineUnderflow" -> False]

(b) About the performance of Fold: on Mathematica v7 after disabling CatchMachineUnderflow, the Fold code is 10x faster then Do code. However, on Mathematica v9 the Fold code is a bit slower than Do. This seems like a regression in Mathematica. For comparison, this code has 10x improvement than the Do version: Fold[# + Sin[#2] &, 1.0, Range[10^6]] both on v7 and v9.

Answer 1

In version 7, after setting the option that Rojo described, your Fold code is nearly an order of magnitude faster than Do:

SetSystemOptions["CatchMachineUnderflow" -> False];

AbsoluteTiming[
 sum = 1.0;
 inc = 1.0;
 Do[inc = inc*Sin[10.5]/i; sum = sum + Tan[inc], {i, 10^6}];
 sum
]

{2.0100028, 0.105747}

AbsoluteTiming@
 Fold[{(#[[1]] Sin[10.5])/(#2 + 1), #[[2]] + Tan[#[[1]]]} &, {Sin[10.5], 1.0}, 
  N@Range[10^6]]

{0.2500003, {0., 0.105747}}

The Fold code can be made faster still with a few optimizations:

sin = Sin[10.5];

AbsoluteTiming[
 Fold[
   {Divide[#[[1]] sin, #2], #[[2]] + Tan[#[[1]]]} &,
   {sin, 1.0}, 
   Range[2, 10^6 + 1]
 ]
]

{0.1600025, {0., 0.105747}}

In this case splitting the operations and vectorizing Tan yields a greater improvement:

AbsoluteTiming[
 1 + Tr @ Tan @ FoldList[Divide[# sin, #2] &, sin, Range[2, 10^6 + 1]]
]

{0.0600001, 0.105747}

This may use additional memory, but trading memory consumption for greater speed is a common programming compromise. If you need to work with longer lists you can split the list into sections and use the output of one Fold as the input for the next:

Fold[
  Fold[{Divide[#[[1]] sin, #2], #[[2]] + Tan[#[[1]]]} &, #, Range[#2, #2 + 10000]] &,
  {sin, 1.0},
  Range[2, 10^7, 10000]
] // AbsoluteTiming

{1.8000025, {0., 0.105747}}

Answer 2

Simple and fast method:

SetSystemOptions["CatchMachineUnderflow" -> False];
inc = 1.0;
a = Sin[10.5];
1 + Sum[Tan[inc *= Divide[a, n]], {n, 10^5}]

It is about 70% faster than your example with Do.

See also: Is there a difference between Divide[a,b] and a/b?

Answer 3

To be honest, I don't understand why you using Fold here. Using FoldList instead would give you much simple and faster code:

Total@Tan@FoldList[Times, Table[Sin[10.5]/i, {i, 10^5}]] + 1 // AbsoluteTiming