[Guile-commits] 401/437: Implement a correct generation of Fibonacci numbers.

[Andy Wingo]

wingo pushed a commit to branch lightning
in repository guile.

commit 76876dd7bf25c5d57f47b60fb794adeac40fd105
Author: Paulo Andrade <address@hidden>
Date:   Mon Nov 30 15:32:48 2015 -0200

    Implement a correct generation of Fibonacci numbers.
    
        * doc/body.texi: Change documentation to no longer say
        it is a variant of the Fibonacci sequence, and document
        a proper implementation.
        Thanks to Jon Arintok for pointing out that the Fibonacci
        sequence generation was incorrect. It was documented, but
        still confusing.
    
        * check/fib.tst, check/fib.ok, check/bp.tst, check/bp.ok,
        doc/ifib.c, doc/rbif.c: Implement a proper Fibonacci
        sequence implementation.
---
 ChangeLog     | 13 +++++++++++++
 THANKS        |  1 +
 check/bp.ok   |  2 +-
 check/bp.tst  | 16 ++++++++--------
 check/fib.ok  |  2 +-
 check/fib.tst | 18 ++++++++++--------
 doc/body.texi | 58 ++++++++++++++++++++++++++--------------------------------
 doc/ifib.c    | 19 +++++++++++--------
 doc/rfib.c    | 16 +++++++++-------
 9 files changed, 80 insertions(+), 65 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 0d3dece..82779a1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2015-11-30 Paulo Andrade <address@hidden>
+
+       * doc/body.texi: Change documentation to no longer say
+       it is a variant of the Fibonacci sequence, and document
+       a proper implementation.
+       Thanks to Jon Arintok for pointing out that the Fibonacci
+       sequence generation was incorrect. It was documented, but
+       still confusing.
+
+       * check/fib.tst, check/fib.ok, check/bp.tst, check/bp.ok,
+       doc/ifib.c, doc/rbif.c: Implement a proper Fibonacci
+       sequence implementation.
+
 2015-07-03 Paulo Andrade <address@hidden>
 
        * lib/jit_mips-cpu.c: Correct definition of htonr_ul.
diff --git a/THANKS b/THANKS
index 5537f26..42bbfc6 100644
--- a/THANKS
+++ b/THANKS
@@ -16,3 +16,4 @@ Trent Nelson                    <address@hidden>
 Vitaly Magerya                  <address@hidden>
 Brandon Invergo                 <address@hidden>
 Holger Hans Peter Freyther      <address@hidden>
+Jon Arintok                     <address@hidden>
diff --git a/check/bp.ok b/check/bp.ok
index ce73f6e..7e13ef0 100644
--- a/check/bp.ok
+++ b/check/bp.ok
@@ -1 +1 @@
-nfibs(32) = 7049155
+nfibs(32) = 2178309
diff --git a/check/bp.tst b/check/bp.tst
index b05bdd0..9e6798d 100644
--- a/check/bp.tst
+++ b/check/bp.tst
@@ -9,9 +9,11 @@ fmt:
 rfibs:
        prolog
        arg $in
-       getarg %v0 $in          /* V0 = N */
-
-       blti_u out %v0 2
+       getarg %r0 $in          /* R0 = N */
+       beqi out %r0 0
+       movr %v0 %r0            /* V0 = R0 */
+       movi %r0 1
+       blei_u out %v0 2
        subi %v1 %v0 1          /* V1 = N-1 */
        subi %v2 %v0 2          /* V1 = N-2 */
        prepare
@@ -21,12 +23,10 @@ rfibs:
        prepare
                pushargr %v2
        finishi rfibs
-       retval %v2              /* V2 = rfibs(N-2) */
-       addi %v1 %v1 1
-       addr %r0 %v1 %v2
-       retr %r0
+       retval %r0              /* R0 = rfibs(N-2) */
+       addr %r0 %r0 %v1
 out:
-       reti 1
+       retr %r0
        epilog
 
        name main
diff --git a/check/fib.ok b/check/fib.ok
index ce73f6e..7e13ef0 100644
--- a/check/fib.ok
+++ b/check/fib.ok
@@ -1 +1 @@
-nfibs(32) = 7049155
+nfibs(32) = 2178309
diff --git a/check/fib.tst b/check/fib.tst
index 6831632..b8be288 100644
--- a/check/fib.tst
+++ b/check/fib.tst
@@ -9,19 +9,21 @@ format:
 nfibs:
        prolog
        arg $in
-       getarg %r2 $in          // R2 = n
-       movi %r1 1
-       blti_u ref %r2 2
-       subi %r2 %r2 1
+       getarg %r0 $in          // R0 = n
+       beqi ref %r0 0
+       movr %r1 %r0
        movi %r0 1
+       blti_u ref %r1 2
+       subi %r2 %r1 2
+       movr %r1 %r0
 loop:
        subi %r2 %r2 1          // decr. counter
-       addr %v0 %r0 %r1        // V0 = R0 + R1
-       movr %r0 %r1            // R0 = R1
-       addi %r1 %v0 1          // R1 = V0 + 1
+       movr %v0 %r0            // V0 = R0
+       addr %r0 %r0 %r1        // R0 = R0 + R1
+       movr %r1 %v0            // R1 = V0
        bnei loop %r2 0         // if (R2) goto loop
 ref:
-       retr %r1                // RET = R1
+       retr %r0                // RET = R0
        epilog
 
        name main
diff --git a/doc/body.texi b/doc/body.texi
index 23b8b8f..09e9866 100644
--- a/doc/body.texi
+++ b/doc/body.texi
@@ -1291,25 +1291,14 @@ generation so powerful.
 @node Fibonacci
 @section Fibonacci numbers
 
-The code in this section calculates a variant of the Fibonacci sequence.
-While the traditional Fibonacci sequence is modeled by the recurrence
-relation:
+The code in this section calculates the Fibonacci sequence. That is
+modeled by the recurrence relation:
 @display
-     f(0) = f(1) = 1
+     f(0) = 0
+     f(1) = f(2) = 1
      f(n) = f(n-1) + f(n-2)
 @end display
 
address@hidden
-the functions in this section calculates the following sequence, which
-is more interesting as a address@hidden's because, as is
-easily seen, the sequence represents the number of activations of the
address@hidden procedure that are needed to compute its value through
-recursion.}:
address@hidden
-     fib(0) = fib(1) = 1
-     fib(n) = fib(n-1) + fib(n-2) + 1
address@hidden display
-
 The purpose of this example is to introduce branches.  There are two
 kind of branches: backward branches and forward branches.  We'll
 present the calculation in a recursive and iterative form; the
@@ -1330,6 +1319,7 @@ int main(int argc, char *argv[])
   jit_node_t *call;
   jit_node_t *in;                 @rem{/* offset of the argument */}
   jit_node_t *ref;                @rem{/* to patch the forward reference */}
+  jit_node_t *zero;               @rem{/* to patch the forward reference */}
 
   init_jit(argv[0]);
   _jit = jit_new_state();
@@ -1337,8 +1327,11 @@ int main(int argc, char *argv[])
   label = jit_label();
         jit_prolog   ();
   in =  jit_arg      ();
-        jit_getarg   (JIT_V0, in);              @rem{/* V0 = n */}
-  ref = jit_blti     (JIT_V0, 2);
+        jit_getarg   (JIT_V0, in);              @rem{/* R0 = n */}
+ zero = jit_beqi     (JIT_R0, 0);
+        jit_movr     (JIT_V0, JIT_R0);          /* V0 = R0 */
+        jit_movi     (JIT_R0, 1);
+  ref = jit_blei     (JIT_V0, 2);
         jit_subi     (JIT_V1, JIT_V0, 1);       @rem{/* V1 = n-1 */}
         jit_subi     (JIT_V2, JIT_V0, 2);       @rem{/* V2 = n-2 */}
         jit_prepare();
@@ -1350,13 +1343,11 @@ int main(int argc, char *argv[])
           jit_pushargr(JIT_V2);
         call = jit_finishi(NULL);
         jit_patch_at(call, label);
-        jit_retval(JIT_V2);                     @rem{/* V2 = fib(n-2) */}
-        jit_addi(JIT_V1,  JIT_V1,  1);
-        jit_addr(JIT_R0, JIT_V1, JIT_V2);       @rem{/* R0 = V1 + V2 + 1 */}
-        jit_retr(JIT_R0);
+        jit_retval(JIT_R0);                     @rem{/* R0 = fib(n-2) */}
+        jit_addr(JIT_R0, JIT_R0, JIT_V1);       @rem{/* R0 = R0 + V1 */}
 
   jit_patch(ref);                               @rem{/* patch jump */}
-        jit_movi(JIT_R0, 1);                    @rem{/* R0 = 1 */}
+  jit_patch(zero);                              @rem{/* patch jump */}
         jit_retr(JIT_R0);
 
   @rem{/* call the generated address@hidden passing 32 as an argument */}
@@ -1403,6 +1394,7 @@ int main(int argc, char *argv[])
   pifi       fib;
   jit_node_t *in;               @rem{/* offset of the argument */}
   jit_node_t *ref;              @rem{/* to patch the forward reference */}
+  jit_node_t *zero;             @rem{/* to patch the forward reference */}
   jit_node_t *jump;             @rem{/* jump to start of loop */}
   jit_node_t *loop;             @rem{/* start of the loop */}
 
@@ -1411,22 +1403,24 @@ int main(int argc, char *argv[])
 
         jit_prolog   ();
   in =  jit_arg      ();
-        jit_getarg   (JIT_R2, in);              @rem{/* R2 = n */}
-        jit_movi     (JIT_R1, 1);
-  ref = jit_blti     (JIT_R2, 2);
-        jit_subi     (JIT_R2, JIT_R2, 1);
+        jit_getarg   (JIT_R0, in);              @rem{/* R0 = n */}
+ zero = jit_beqi     (JIT_R0, 0);
+        jit_movr     (JIT_R1, JIT_R0);
         jit_movi     (JIT_R0, 1);
+  ref = jit_blti     (JIT_R1, 2);
+        jit_subi     (JIT_R2, JIT_R2, 2);
+        jit_movr     (JIT_R1, JIT_R0);
 
   loop= jit_label();
         jit_subi     (JIT_R2, JIT_R2, 1);       @rem{/* decr. counter */}
-        jit_addr     (JIT_V0, JIT_R0, JIT_R1);  @rem{/* V0 = R0 + R1 */}
-        jit_movr     (JIT_R0, JIT_R1);          @rem{/* R0 = R1 */}
-        jit_addi     (JIT_R1, JIT_V0, 1);       @rem{/* R1 = V0 + 1 */}
-  jump= jit_bnei     (JIT_R2, 0);               @rem{/* if (R2) goto loop; */}
-  jit_patch_at(jump, label);
+        jit_movr     (JIT_V0, JIT_R0);          /* V0 = R0 */
+        jit_addr     (JIT_R0, JIT_R0, JIT_R1);  /* R0 = R0 + R1 */
+        jit_movr     (JIT_R1, JIT_V0);          /* R1 = V0 */
+  jump= jit_bnei     (JIT_R2, 0);               /* if (R2) goto loop; */
+  jit_patch_at(jump, loop);
 
   jit_patch(ref);                               @rem{/* patch forward jump */}
-        jit_movr     (JIT_R0, JIT_R1);          @rem{/* R0 = R1 */}
+  jit_patch(zero);                              @rem{/* patch forward jump */}
         jit_retr     (JIT_R0);
 
   @rem{/* call the generated address@hidden passing 36 as an argument */}
diff --git a/doc/ifib.c b/doc/ifib.c
index 769e4a9..745c80b 100644
--- a/doc/ifib.c
+++ b/doc/ifib.c
@@ -10,6 +10,7 @@ int main(int argc, char *argv[])
   pifi       fib;
   jit_node_t *in;               /* offset of the argument */
   jit_node_t *ref;              /* to patch the forward reference */
+  jit_node_t *zero;             /* to patch the forward reference */
   jit_node_t *jump;             /* jump to start of loop */
   jit_node_t *loop;             /* start of the loop */
 
@@ -18,22 +19,24 @@ int main(int argc, char *argv[])
 
         jit_prolog   ();
   in =  jit_arg      ();
-        jit_getarg   (JIT_R2, in);              /* R2 = n */
-        jit_movi     (JIT_R1, 1);
-  ref = jit_blti     (JIT_R2, 2);
-        jit_subi     (JIT_R2, JIT_R2, 1);
+        jit_getarg   (JIT_R0, in);              /* R0 = n */
+ zero = jit_beqi     (JIT_R0, 0);
+        jit_movr     (JIT_R1, JIT_R0);
         jit_movi     (JIT_R0, 1);
+  ref = jit_blei     (JIT_R1, 2);
+        jit_subi     (JIT_R2, JIT_R1, 2);
+        jit_movr     (JIT_R1, JIT_R0);
 
   loop= jit_label();
         jit_subi     (JIT_R2, JIT_R2, 1);       /* decr. counter */
-        jit_addr     (JIT_V0, JIT_R0, JIT_R1);  /* V0 = R0 + R1 */
-        jit_movr     (JIT_R0, JIT_R1);          /* R0 = R1 */
-        jit_addi     (JIT_R1, JIT_V0, 1);       /* R1 = V0 + 1 */
+        jit_movr     (JIT_V0, JIT_R0);          /* V0 = R0 */
+        jit_addr     (JIT_R0, JIT_R0, JIT_R1);  /* R0 = R0 + R1 */
+        jit_movr     (JIT_R1, JIT_V0);          /* R1 = V0 */
   jump= jit_bnei     (JIT_R2, 0);               /* if (R2) goto loop; */
   jit_patch_at(jump, loop);
 
   jit_patch(ref);                               /* patch forward jump */
-        jit_movr     (JIT_R0, JIT_R1);          /* R0 = R1 */
+  jit_patch(zero);                              /* patch forward jump */
         jit_retr     (JIT_R0);
 
   /* call the generated code, passing 36 as an argument */
diff --git a/doc/rfib.c b/doc/rfib.c
index 97d74f6..f14da42 100644
--- a/doc/rfib.c
+++ b/doc/rfib.c
@@ -12,6 +12,7 @@ int main(int argc, char *argv[])
   jit_node_t *call;
   jit_node_t *in;                 /* offset of the argument */
   jit_node_t *ref;                /* to patch the forward reference */
+  jit_node_t *zero;             /* to patch the forward reference */
 
   init_jit(argv[0]);
   _jit = jit_new_state();
@@ -19,8 +20,11 @@ int main(int argc, char *argv[])
   label = jit_label();
         jit_prolog   ();
   in =  jit_arg      ();
-        jit_getarg   (JIT_V0, in);              /* V0 = n */
-  ref = jit_blti     (JIT_V0, 2);
+        jit_getarg   (JIT_R0, in);              /* R0 = n */
+ zero = jit_beqi     (JIT_R0, 0);
+        jit_movr     (JIT_V0, JIT_R0);          /* V0 = R0 */
+        jit_movi     (JIT_R0, 1);
+  ref = jit_blei     (JIT_V0, 2);
         jit_subi     (JIT_V1, JIT_V0, 1);       /* V1 = n-1 */
         jit_subi     (JIT_V2, JIT_V0, 2);       /* V2 = n-2 */
         jit_prepare();
@@ -32,13 +36,11 @@ int main(int argc, char *argv[])
           jit_pushargr(JIT_V2);
         call = jit_finishi(NULL);
         jit_patch_at(call, label);
-        jit_retval(JIT_V2);                     /* V2 = fib(n-2) */
-        jit_addi(JIT_V1,  JIT_V1,  1);
-        jit_addr(JIT_R0, JIT_V1, JIT_V2);       /* R0 = V1 + V2 + 1 */
-        jit_retr(JIT_R0);
+        jit_retval(JIT_R0);                     /* R0 = fib(n-2) */
+        jit_addr(JIT_R0, JIT_R0, JIT_V1);       /* R0 = R0 + V1 */
 
   jit_patch(ref);                               /* patch jump */
-        jit_movi(JIT_R0, 1);                    /* R0 = 1 */
+  jit_patch(zero);                              /* patch jump */
         jit_retr(JIT_R0);
 
   /* call the generated code, passing 32 as an argument */