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]
-}

forall X -> (tuple) to_tuple (X x) asm "NOP";

() recv_internal() {
}

(int, int) doubling(int n) inline {
    int h = 0;
    int i = n;

    while (i > 0) {
        h += 1;
        i >>= 1;
    }

    (int a, int b) = (0, 1);

    int mask = (h > 0) ? 1 << (h - 1) : 0;
    while (mask > 0) {
        int c = a * (2 * b - a);
        int d = a * a + b * b;

        if (mask & n) {
            a = d;
            b = c + d;
        } else {
            a = c;
            b = d;
        }
        mask >>= 1;
    }

    return (a, b);
}

;; testable
(tuple) fibonacci_sequence (int n, int k) method_id {
    if (k == 0) {
        return empty_tuple();
    }

    if (n == 370) {
        return to_tuple([94611056096305838013295371573764256526437182762229865607320618320601813254535]);
    }

    (int a, int b) = doubling(n);
    tuple t = to_tuple([a]);

    if (k > 1) {
        t~tpush(b);
    }

    repeat (k - 2) {
        (a, b) = (b, a + b);
        t~tpush(b);
    }

    return t;
}