Two-Dimensional Recursive JavaScript

Collapse
This topic is closed.
X
X
Collapse
 
  • Page of 1
  • Time
  • Show
Clear All
new posts
Previous template Next
  • wgarner@ucsd.edu
    #1

    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">& #196;</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.
    Tags: None
    • Tom de Neef
      #2
      Re: Two-Dimensional Recursive JavaScript


      <wgarner@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


        Comment

        • Dr J R Stockton
          #3
          Re: Two-Dimensional Recursive JavaScript

          In comp.lang.javas cript message <2ff17b21-198a-4f08-9652-6511d2c74dd7@a8
          g2000prf.google groups.com>, Wed, 13 Aug 2008 19:56:51, wgarner@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.

            Comment

            Previous template Next
            Working...