473,832 Members | 2,196 Online

# Two-Dimensional Recursive JavaScript

I am trying to implement a two-dimensional recursive formula, g(x,y).
It is sort of like multiplication.

g(x,y) = 0 if either x or y is 0. g(1, y) = y and g(x, 1) = x.

Those are the base cases.

In general, though, g(x, y) = h[g(x,b) XOR g(a,y) XOR g(a,b): 0 <= a <
x, 0 <= b < y], where h is another function which I have already
written a script for. (The XOR refers to binary addition and can be
implemented via " ^ ", so that is all right.)

The problem I am having is preventing stack overflows and making the
script run in a reasonable amount of time.

I looked online and found that for a Fibonaci sequence, one code used
push() and shift() to reduce the processing time and to reuse the
previous calculuations.

The code is as follows:

function fastfib(n){
var i;
var fibs = new Array();
fibs.push(0);
fibs.push(1);
for(i=0; i<n; i++){
fibs.push(fibs[0] + fibs[1]);
fibs.shift();
}
return fibs[0];
}
Something like that would be ideal here, as it would be quite helpful
to save these function values and use them to build more complicated
ones.

My thought was to create a two-dimensional array, but I got stuck.
Here is the code that I have so far:
<html>
<titleNim Multiplication </title>
<body>

<script language="JavaS cript">

function nim_mult(a,b) {

var g = new Array(a+1);
for(i=0; i<=a;i++) {
g[i] = new Array(b+1);
}

for(i=0;i<=a;i+ +) {
g[i][0] = 0;
if(b>0)
g[i][1] = i;
}
for(j=0;j<=b;j+ +) {
g[0][j] = 0;
if(a>0)
g[1][j] = j;
}
if(a=="0" || b=="0") {
return 0;
} else if (a=="1") {
return b;
} else if(b=="1") {
return a;
} else {

nim_mult_str="" ;

for(i=0; i<a; i++) {
for(j=0; j<b; j++) {
nim_mult_str+= "," + nim_mult(i,b) + ",";
}
}
g[a][b] = h(nim_mult_str) ;

return g[a][b];
}

}
</script>
<form name=nimmulti>

<input type="text" name="a"<font face="Symbol">Ä </font<input
type="text" name="b"<br><br >

<input type="button" value="Multiply "
onclick="multva l.value=nim_mul t(a.value,b.val ue)"><br><br>

Multiplication value: <input type="text" name="multval">

</form>

</body>
</html>
I should mention that the h() function I have written takes a string
of numbers, parses out the commas, and then returns a value.
Any help would be greatly appreciated.
Aug 14 '08 #1
2 2305

<wg*****@ucsd.e duwrote
>I am trying to implement a two-dimensional recursive formula, g(x,y).
It is sort of like multiplication.

g(x,y) = 0 if either x or y is 0. g(1, y) = y and g(x, 1) = x.

Those are the base cases.
<snip>
>

function nim_mult(a,b) {

var g = new Array(a+1);
for(i=0; i<=a;i++) {
g[i] = new Array(b+1);
}
Every time you enter this function it will create the g array and fill it.
And the function is called recursively, so it doesn't meet your objective.
Instead, you want to declare and fill it once. That should thus happen in an
'outer' function. The recursion should than be placed in an inner function.
See later.
>
for(i=0;i<=a;i+ +) {
g[i][0] = 0;
if(b>0)
g[i][1] = i;
}
for(j=0;j<=b;j+ +) {
g[0][j] = 0;
if(a>0)
g[1][j] = j;
}
I'm not sure that it is sensible to fille the elements [0,j] and [i,0]. Will
they ever be accessed ?
>
if(a=="0" || b=="0") {
return 0;
} else if (a=="1") {
return b;
} else if(b=="1") {
return a;
} else {
NB: why do you compare a and b here to a string, wheras before you compared
them to numbers. The following code will achieve the same:
if (a==0 || b==0) return 0;
if (a==1) return b;
if (b==1) return a;
>
nim_mult_str="" ;

for(i=0; i<a; i++) {
for(j=0; j<b; j++) {
nim_mult_str+= "," + nim_mult(i,b) + ",";
}
I don't understand why you loop thru j. Part of the formula is missing ?
}
g[a][b] = h(nim_mult_str) ;

return g[a][b];
}
I think that your idea of storing results in the 2d array could be
implemented as follows.
function nim_mult(a,b) {
if (a==0 || b==0) return 0;
if (a==1) return b;
if (b==1) return a;
var i,g = []
for (i=0;i<a;i++) {g[i] = []}; // create g and make it available to inner
function
function inner(a,b) {
var i,j,result
if (a==0 || b==0) return 0;
if (a==1) return b;
if (b==1) return a;
result=g[a][b]
if (result) return result;
result="";
for(i=0; i<a; i++) {
for(j=0; j<b; j++) {
result+="," + inner(i,b) + ","+inner(a ,j); // ???
}}
g[a][b]=result;
return result
}
return inner(a,b)
}

Tom
Aug 14 '08 #2
In comp.lang.javas cript message <2ff17b21-198a-4f08-9652-6511d2c74dd7@a8
g2000prf.google groups.com>, Wed, 13 Aug 2008 19:56:51, wg*****@ucsd.ed u
posted:
>I am trying to implement a two-dimensional recursive formula, g(x,y).
>The problem I am having is preventing stack overflows and making the
script run in a reasonable amount of time.

There, ISTM that x & y are integers. Given g(x, y), one can produce a
faster G(x, y), something like :-

var K = [] // Cache

function G(X, Y) { var T
T = K[X] ; if (!T) T = K[X] = [] // if X new, create X sub-array
T = T[Y] ; if (!T) T = T[Y] = g(X, Y) // if X Y new, fill element
return T }

With that, G(X, Y) will be calculated only once for each (X, Y), saving
time. If the range of X, or an upper bound, is known, then a little
time will be saved by first filling K with empty arrays K[J] = [] and
omitting the first test.

If the first calculation is of a non-small X, Y, then that will save
time (for likely g) but may not reduce the depth of recursion. But if
you start calling with (X, Y) small and work up, it probably will reduce
the maximum depth needed for the larger (X, Y).

Note that there is an assumption that the number of combinations (X, Y)
is not to great to be cached. In that case, it *might* help to cache
only the values for which X, Y, or both are small - that depends on the
details of g.

One can test G by checking that G(X, Y) == g(X, Y) for various (X, Y).

One could make G more general by passing g in as a third argument?
See <http://www.merlyn.demo n.co.uk/js-misc1.htm#Cashf or 1-D examples.

ASIDE I now have an even faster (slightly) Easter routine, by Knuth
via McClendon; but I cannot trace it back to Bull or Act.
Anyone got the relevant part of Knuth "Art" vol 1 pp 155-156?

--
(c) John Stockton, nr London UK. ?@merlyn.demon. co.uk Turnpike v6.05 MIME.
<URL:http://www.merlyn.demo n.co.uk/TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.merlyn.demo n.co.uk/clpb-faq.txt RAH Prins : c.l.p.b mFAQ;