R help - Mar 2008 - How to remove double loop?

Bill, Alberto, Gabor,
Thank you for answering my question. Now I learned about outer() function.
That was a straightforward example.

But what if I had a matrix, where the last column was filled with
values first (again, a for loop), and the rest was filled by using a
double loop?

OVal <- matrix(0, n+1, n+1)

for(i in 0:n){
    OVal[i+1, n+1] <- max(Val[i+1, n+1]-K, 0)
}

for(i in seq(n,1, by=-1)){
    for(j in 0:(i-1)){
        OVal[j+1, i] <- a*((1-p)*OVal[j+1, i+1]+p*OVal[j+2, i+1])
    }
}

Even if I leave the first simple for loop as it is, is there a more
efficient way to program the double loop part now that OVal is used
within the function itself?
It is pretty easy to write for loops, but it is very hard to write
computationally optimal code. :-( Could you please help me with the
above one, if possible?


-- 
Jonas Malmros
Stockholm University
Stockholm, Sweden

Jonas,
Take a look at CRRBinomialTreeOption{fOptions} in which Diethelm Wuertz
uses a double loop,
but of course, he's optimized it to use only a vector instead of a
matrix!

David L. Reiner, PhD
Head Quant
Rho Trading Securities, LLC


-----Original Message-----
From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
On Behalf Of Jonas Malmros
Sent: Wednesday, March 19, 2008 9:04 AM
To: r-help at r-project.org
Subject: [R] How to remove double loop?

Bill, Alberto, Gabor,
Thank you for answering my question. Now I learned about outer()
function.
That was a straightforward example.

But what if I had a matrix, where the last column was filled with
values first (again, a for loop), and the rest was filled by using a
double loop?

OVal <- matrix(0, n+1, n+1)

for(i in 0:n){
    OVal[i+1, n+1] <- max(Val[i+1, n+1]-K, 0)
}

for(i in seq(n,1, by=-1)){
    for(j in 0:(i-1)){
        OVal[j+1, i] <- a*((1-p)*OVal[j+1, i+1]+p*OVal[j+2, i+1])
    }
}

Even if I leave the first simple for loop as it is, is there a more
efficient way to program the double loop part now that OVal is used
within the function itself?
It is pretty easy to write for loops, but it is very hard to write
computationally optimal code. :-( Could you please help me with the
above one, if possible?


-- 
Jonas Malmros
Stockholm University
Stockholm, Sweden

______________________________________________
R-help at r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

Read the posting guide (the bit about reproducible code):
> OVal <- matrix(0, n+1, n+1)
>
> for(i in 0:n){
+     OVal[i+1, n+1] <- max(Val[i+1, n+1]-K, 0)
+ }
Error: object "Val" not found
>
> for(i in seq(n,1, by=-1)){
+     for(j in 0:(i-1)){
+         OVal[j+1, i] <- a*((1-p)*OVal[j+1, i+1]+p*OVal[j+2, i+1])
+     }
+ }
Error: object "p" not found
>
On Thu, 20 Mar 2008, Jonas Malmros wrote:
> Bill, Alberto, Gabor,
> Thank you for answering my question. Now I learned about outer() function.
> That was a straightforward example.
>
> But what if I had a matrix, where the last column was filled with
> values first (again, a for loop), and the rest was filled by using a
> double loop?
>
> OVal <- matrix(0, n+1, n+1)
>
> for(i in 0:n){
>     OVal[i+1, n+1] <- max(Val[i+1, n+1]-K, 0)
> }
>
> for(i in seq(n,1, by=-1)){
>     for(j in 0:(i-1)){
>         OVal[j+1, i] <- a*((1-p)*OVal[j+1, i+1]+p*OVal[j+2, i+1])
>     }
> }
>
> Even if I leave the first simple for loop as it is, is there a more
> efficient way to program the double loop part now that OVal is used
> within the function itself?
> It is pretty easy to write for loops, but it is very hard to write
> computationally optimal code. :-( Could you please help me with the
> above one, if possible?

Jonas Malmros wrote:
> 
> But what if I had a matrix, where the last column was filled with
> values first (again, a for loop), and the rest was filled by using a
> double loop?
> 
Killing one of those loops is quite simple. The other may be
harder.
> OVal <- matrix(0, n+1, n+1)
> 
> for(i in 0:n){
>     OVal[i+1, n+1] <- max(Val[i+1, n+1]-K, 0)
> }
> 
This is straightforward: notice that most R arithmetic
functions that operate in scalars also operate in vectors, 
matrices and arrays. For example, sin(pi) is zero, but
sin(c(0,pi/2,pi,3*pi/2)) is c(0, 1, 0, -1) (with some
rounding errors).

The loop in _i_ is just to take the max of a column? So:

OVal[1:(n+1), n+1] <- # this is a vector
  max(Val[1:(n+1), n+1] -  # this is another vector
    - K, 0)   # vector - scalar = vector, max(vector) = vector

or, in one line:

OVal[1:(n+1), n+1] <- max(Val[1:(n+1), n+1] - K, 0)

You can drop the indices, as you are taking all of them:

OVal[,n+1] <- max(Val[,n+1] - K, 0)

> for(i in seq(n,1, by=-1)){
>     for(j in 0:(i-1)){
>         OVal[j+1, i] <- a*((1-p)*OVal[j+1, i+1]+p*OVal[j+2, i+1])
>     }
> }
> 
The inner loop is simple, but somehow tricky.

You are computing each j-th term as the same j-th term combined
with the (j+1)-th term. So, you take a combination of js in
the 1:i range and combine with js in the 2:(i+1) range... So:

    OVal[1:i, i] <- a*((1-p)*OVal[1:i, i+1] + p*OVal[2:(i+1), i+1])

The outer loop (in i) probably can't be optimized.

Alberto Monteiro