5.fc

{-
  TASK 5 - Fibonacci sequence
  Implement a function that generates the Fibonacci
  sequence from N to N+K terms (0<=N<=370; 0<=N+K<=371; 0<=K<=255).
  The first two terms of the Fibonacci sequence are F_0 = 0 and F_1 = 1,
  and the rest are defined as F_n = F_(n-1) + F_(n-2).
  The resulting Fibonacci sequence should be stored in a tuple.
  For example, a request with N = 1 and K = 3 should return a tuple [1, 1, 2],
  and a request with N = 201 and K = 4 should return a tuple
  [453973694165307953197296969697410619233826,
  734544867157818093234908902110449296423351,
  1188518561323126046432205871807859915657177,
  1923063428480944139667114773918309212080528]
-}

() recv_internal() {
}

int sgn(int x) asm "SGN";
int bits(int x) asm "UBITSIZE";
(tuple, ()) push_back(tuple tail, int head) asm "CONS";
(tuple, int) pop_back(tuple list) asm "UNCONS";
tuple null() asm "PUSHNULL";

;; (int, int) _fibonacci(int n) asm  """
;;     DUP	//  n n
;;     SGN	//  n _1
;;     IF:<{	//  n
;;       DUP
;;       UBITSIZE	
;;         //  n |n|
;;       SWAP
;;       s1 PUSH
;;       REPEAT:<{
;;         // |n| n
;;         2 INT
;;         // |n| n 2
;;         DIVMOD
;;         // |n| n/2 n%2
;;         ROTREV
;;         // n%2 |n| n/2
;;       }>
;;       POP
;;       // n_0, n_1, n_2, .., n_|n|-1, |n|
      
;;       1 INT
;;       0 INT
;;       ROT

;;       REPEAT:<{
;;         // n_0, n_1, ..., n_k, a, b
;;         ROT
;;         SGN

;;         IF:<{
;;           // a, b
;;           s1 s1 s1 PUSH3


;;         }>ELSE<{

;;         }>
;;       }>

;;     }>ELSE<{	//  n
;;       DROP	// 
;;       1 PUSHINT	//  _28=1
;;       0 PUSHINT	//  _28=1 _29=0
;;     }>
;; """;

;; (int, int) fibonacci(int n) inline {
;;   return _fibonacci(n);
;; }

(int, int) fibonacci(int n) inline {

  if (sgn(n)) {
    tuple x = null();
    
    int y = bits(n);
    repeat (y) {
      x~push_back(n % 2);
      n >>= 1;
    }

    int a = 1;
    int b = 0;

    repeat (y) {
      if (x~pop_back()) {
        int ab = a + b;
        int ab2 = ab * ab;
        int c = ab2 - a * a;
        int d = ab2 + b * b;
        a = c;
        b = d;
      }
      else {
        int c = a * a + b * b;
        int d = b * (2 * a + b);
        a = c;
        b = d;
      }
    }

    return (a, b);
  }
  else {
    return (1, 0);
  }
}

(tuple) _fibonacci_sequence (int n, int k) asm """
// n, k
DUP
// n, k, k
IF:<{
  SWAP // k, n
  // k, n
  fibonacci INLINECALLDICT
  // s0 DUMP
  // s1 DUMP
  // s2 DUMP

  ROT // k, a, b
  // k, f_n-1, f_n
  // f_n-1, f_n, k
  s0 PUSH
  // f_n-1, f_n, k, k
  1 SUBCONST
  // f_n-1, f_n, k, k-1
  REPEAT:<{
    // f_n-1, f_n, k
    s2 s1 PUSH2
    ADD
    SWAP
  }>
  // f_n-1 f_n, f_n + 1, ... f_n + k - 3, f_n + k - 2, f_n + k - 1, k
  TUPLEVAR
  // f_n-1 (f_n, f_n + 1, ..., f_n + k - 1)
  SWAP
  // (f_n, f_n + 1, ..., f_n + k - 1) f_n-1
  DROP
  // (f_n, f_n + 1, ..., f_n + k - 1)
}>ELSE<{
  // n, k
  DROP2
  //
  NIL
}>
""";

;; testable
(tuple) fibonacci_sequence (int n, int k) inline method_id {
  return _fibonacci_sequence(n, k);
}