W
wgarner
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>
<head>
<title> Nim Multiplication </title>
</head>
<body>
<script language="JavaScript">
function nim_mult(a,b) {
var g = new Array(a+1);
for(i=0; i<=a;i++) {
g = new Array(b+1);
}
for(i=0;i<=a;i++) {
g[0] = 0;
if(b>0)
g[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] = h(nim_mult_str);
return g[a];
}
}
</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="multval.value=nim_mult(a.value,b.value)"><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.
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>
<head>
<title> Nim Multiplication </title>
</head>
<body>
<script language="JavaScript">
function nim_mult(a,b) {
var g = new Array(a+1);
for(i=0; i<=a;i++) {
g = new Array(b+1);
}
for(i=0;i<=a;i++) {
g[0] = 0;
if(b>0)
g[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] = h(nim_mult_str);
return g[a];
}
}
</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="multval.value=nim_mult(a.value,b.value)"><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.