473,832 Members | 2,196 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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>
<head>
<titleNim Multiplication </title>
</head>
<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;
<URL:ftp://garbo.uwasa.fi/pc/link/tsfaqp.zipTimo Salmi's Turbo Pascal FAQ.
Aug 14 '08 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
1790
by: SimonC | last post by:
I'm looking to do something similar to a feature found on Ticketmaster.com, where you select your seats at a venue, and then you have two minutes in which to take or leave them. QUESTION 1a. Inside (or just after) the same query that searches for available seats, I need to SIMULTANEOUSLY mark those seats as "on hold". I've only read about, but not yet used MySQL transactions, and wonder if this simultaneous "search-and-hold"...
8
1751
by: John Grenier | last post by:
Hi, I have to determine the "standing" (WIN - TIE - LOSS) from confrontations between two teams on a contest. The table matchResults has fields cont_id, team_id and contest_result (int). TABLE matchResults cont_id team_id contest_result 1 1 3 1 2 5
6
1885
by: Willem | last post by:
Hi, I have a newbie question: is it possible to make a search form in asp that searches in two different databases (access)? Willem
10
9392
by: Hank1234 | last post by:
Can I use one Data Adapter and one Command Builder to update amny tables? Currently in my data adapter I query two tables and fill them into two tables in a data set. When I make a change to a record in the second table and call the update method of the data adapter the command builders update command text is for the first table. Can the command builder handle two tables? Code example: Dim oCOnn As New SqlConnection("Data Source=.;" &...
6
4087
by: Matt K. | last post by:
Hi there, I have a form in an Access project that contains a subform which displays the results of a query of the style "select * from where = #a certain date#". In the main part of the form the user can change the date, which will force a requery in the subform to bring up records from the date selected. My question is this... The query in the subform is a very simple one, with only three fields being returned. In the interest of...
7
12902
by: Prabhudhas Peter | last post by:
I have two object instances of a same class... and i assigned values in both object instances (or the values can be taken from databse and assigned to the members of the objects)... Now i want to compare these two objects so that it will return true if both object's members have the same value... it is good if u can give me a single function or simple code snippet.. Thank U -- Peter...
0
1704
by: clintonG | last post by:
I applied aspnet_regsql to SQL2K which was working fine throughout Beta 2 development. After installing Visual Studio and SQL Express RTM my application has blown up. Logging in to the application became realllllllllllly slow. Content in LoginView Role Groups was not displaying even after a user in a role had logged in. It was taking about 15 seconds or so for the login control to display when the login link was selected on the homepage....
9
5280
by: Steven | last post by:
Hello, I have a question about strcmp(). I have four words, who need to be compared if it were two strings. I tried adding the comparison values like '(strcmp(w1, w2) + strcmp(w3, w4))', where w1 and w2 make up the first string and, w3 and w4 make up the second string. I do not want to allocate memory, then put the words together to create a string only to facilitate strcmp() comparison. My question; Does anyone know how to get the...
9
2024
by: dhable | last post by:
I just started working with Python and ran into an annoyance. Is there a way to avoid having to use the "from xxx import yyy" syntax from files in the same directory? I'm sure it's been asked a million times, but I can't seem to find the answer. For example, I have two classes stored in separate files as such. File: one.py ======== class One:
13
5607
by: paul.joseph.davis | last post by:
Hi, I've just had my first encounter with two-phase lookup and I'm scratching my head a bit. The idea behind two phase look up is pretty easy to understand, but I have a case that fails to compile although it appears to me that it should. template<typename TYPE> void foo( std::map< int, TYPE pmap )
0
9795
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9642
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
10540
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10212
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9319
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7753
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5789
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
3970
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3077
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.