Excercise 02 Fibonacci Sequence

plex02.clj

(defn fibs [a b]
  (cons a (lazy-seq (fibs b (+ a b)))))

(take 100 (fibs 1N 1N))
; -> (1N 1N 2N 3N 5N 8N 13N 21N 34N 55N 89N 144N 233N 377N 610N 987N
;     1597N 2584N 4181N 6765N 10946N 17711N 28657N 46368N 75025N
;     121393N 196418N 317811N 514229N 832040N 1346269N 2178309N
;     3524578N 5702887N 9227465N 14930352N 24157817N 39088169N
;     63245986N 102334155N 165580141N 267914296N 433494437N
;     701408733N 1134903170N 1836311903N 2971215073N 4807526976N
;     7778742049N 12586269025N 20365011074N 32951280099N 53316291173N
;     86267571272N 139583862445N 225851433717N 365435296162N
;     591286729879N 956722026041N 1548008755920N 2504730781961N
;     4052739537881N 6557470319842N 10610209857723N 17167680177565N
;     27777890035288N 44945570212853N 72723460248141N 117669030460994N
;     190392490709135N 308061521170129N 498454011879264N
;     806515533049393N 1304969544928657N 2111485077978050N
;     3416454622906707N 5527939700884757N 8944394323791464N
;     14472334024676221N 23416728348467685N 37889062373143906N
;     61305790721611591N 99194853094755497N 160500643816367088N
;     259695496911122585N 420196140727489673N 679891637638612258N
;     1100087778366101931N 1779979416004714189N 2880067194370816120N
;     4660046610375530309N 7540113804746346429N 12200160415121876738N
;     19740274219868223167N 31940434634990099905N 51680708854858323072N
;     83621143489848422977N 135301852344706746049N 218922995834555169026N
;     354224848179261915075N)

plex02.hs

fibs a b = a:fibs b (a + b)
take 100 $ fibs 1 1
-- -> [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,
--      4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,
--      514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,
--      24157817,39088169,63245986,102334155,165580141,267914296,433494437,
--      701408733,1134903170,1836311903,2971215073,4807526976,7778742049,
--      12586269025,20365011074,32951280099,53316291173,86267571272,
--      139583862445,225851433717,365435296162,591286729879,956722026041,
--      1548008755920,2504730781961,4052739537881,6557470319842,
--      10610209857723,17167680177565,27777890035288,44945570212853,
--      72723460248141,117669030460994,190392490709135,308061521170129,
--      498454011879264,806515533049393,1304969544928657,2111485077978050,
--      3416454622906707,5527939700884757,8944394323791464,14472334024676221,
--      23416728348467685,37889062373143906,61305790721611591,99194853094755497,
--      160500643816367088,259695496911122585,420196140727489673,
--      679891637638612258,1100087778366101931,1779979416004714189,
--      2880067194370816120,4660046610375530309,7540113804746346429,
--      12200160415121876738,19740274219868223167,31940434634990099905,
--      51680708854858323072,83621143489848422977,135301852344706746049,
--      218922995834555169026,354224848179261915075]

plex02.js

function BigInt () {
  this.v = [];
  this.show = function () {
    var i, s = "";
    for (i in this.v)
      s = this.v[i] + s;
    return s;
  };
}

BigInt.fromString = function (str) {
  var r = new BigInt(), l;
  for (l = str.length; 0 < l - 7; l -= 7)
    r.v.push(Number(str.substring(l - 7, l)));
  r.v.push(Number(str.substring(0, l)));
  return r;
}

BigInt.plus = function (a, b) {
  var r = new BigInt();
  var i, s, c = 0;
  var al = a.v.length, bl = b.v.length;
  var l = Math.max(al, bl);
  for (i = 0; i < l; i++) {
    s = ((i < al)?a.v[i]:0) + ((i < bl)?b.v[i]:0) + c;
    c = Math.floor(s/10000000);
    r.v.push(s - 10000000*c);
  }
  if (0 < c)
    r.v.push(c);
  return r;
};

function fibs(a, b) {
  return [a, function(){return fibs(b, BigInt.plus(a, b));}];
}

function take(n, ls) {
  var i, r = [];
  for (i = 0; i < n; i++) {
    r.push(ls[0].show());
    ls = ls[1]();
  }
  return r;
}

take(100, fibs(BigInt.fromString("1"), BigInt.fromString("1")))

// -> ['1', '1', '2', '3', '5', '8', '13', '21', '34', '55', '89', '144', '233',
//     '377', '610', '987', '1597', '2584', '4181', '6765', '10946', '17711',
//     '28657', '46368', '75025', '121393', '196418', '317811', '514229',
//     '832040', '1346269', '2178309', '3524578', '5702887', '9227465',
//     '14930352', '24157817', '39088169', '63245986', '102334155', '165580141',
//     '267914296', '433494437', '701408733', '1134903170', '1836311903',
//     '2971215073', '4807526976', '7778742049', '12586269025', '20365011074',
//     '32951280099', '53316291173', '86267571272', '139583862445',
//     '225851433717', '365435296162', '591286729879', '956722026041',
//     '1548008755920', '250473781961', '4052739537881', '655747319842',
//     '10610209857723', '1716768177565', '277778935288', '4494557212853',
//     '7272346248141', '11766903460994', '19039249709135', '38061521170129',
//     '498454011879264', '86515533049393', '134969544928657', '2111485077978050',
//     '3416454622906707', '552793970884757', '8944394323791464',
//     '14472334024676221', '23416728348467685', '37889062373143906',
//     '6135790721611591', '99194853094755497', '1605643816367088',
//     '259695496911122585', '420196140727489673', '679891637638612258',
//     '1100087778366101931', '1779979416004714189', '288006719437816120',
//     '4660046610375530309', '7540113804746346429', '12200160415121876738',
//     '19740274219868223167', '319404346349999905', '5168078854858323072',
//     '83621143489848422977', '135301852344706746049', '218922995834555169026',
//     '354224848179261915075' ]

plex02.lisp

(defun fibs (a b)
  (cons a (lambda () (fibs b (+ a b)))))

(defun take (n l)
  (if (zerop n) '()
      (cons (car l) (take (- n 1) (funcall (cdr l))))))

(take 100 (fibs 1 1))
; -> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711
;     28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578   
;     5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141        
;     267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976      
;     7778742049 12586269025 20365011074 32951280099 53316291173 86267571272         
;     139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920
;     2504730781961 4052739537881 6557470319842 10610209857723 17167680177565        
;     27777890035288 44945570212853 72723460248141 117669030460994 190392490709135   
;     308061521170129 498454011879264 806515533049393 1304969544928657               
;     2111485077978050 3416454622906707 5527939700884757 8944394323791464            
;     14472334024676221 23416728348467685 37889062373143906 61305790721611591        
;     99194853094755497 160500643816367088 259695496911122585 420196140727489673     
;     679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120
;     4660046610375530309 7540113804746346429 12200160415121876738                   
;     19740274219868223167 31940434634990099905 51680708854858323072                 
;     83621143489848422977 135301852344706746049 218922995834555169026               
;     354224848179261915075)

plex02.scm

(define (fibs a b)
  (cons a (delay (fibs b (+ a b)))))

(define (take n ls)
  (if (zero? n)
      '()
      (cons (car ls) (take (- n 1) (force (cdr ls))))))

(take 100 (fibs 1 1))
; -> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584
;     4181 6765 10946 17711 28657 46368 75025 121393 196418
;     317811 514229 832040 1346269 2178309 3524578 5702887
;     9227465 14930352 24157817 39088169 63245986 102334155
;     165580141 267914296 433494437 701408733 1134903170
;     1836311903 2971215073 4807526976 7778742049 12586269025
;     20365011074 32951280099 53316291173 86267571272
;     139583862445 225851433717 365435296162 591286729879
;     956722026041 1548008755920 2504730781961 4052739537881
;     6557470319842 10610209857723 17167680177565 27777890035288
;     44945570212853 72723460248141 117669030460994
;     190392490709135 308061521170129 498454011879264
;     806515533049393 1304969544928657 2111485077978050
;     3416454622906707 5527939700884757 8944394323791464
;     14472334024676221 23416728348467685 37889062373143906
;     61305790721611591 99194853094755497 160500643816367088
;     259695496911122585 420196140727489673 679891637638612258
;     1100087778366101931 1779979416004714189 2880067194370816120
;     4660046610375530309 7540113804746346429 12200160415121876738
;     19740274219868223167 31940434634990099905 51680708854858323072
;     83621143489848422977 135301852344706746049
;     218922995834555169026 354224848179261915075)

plex02hints.clj

;; 'first' takes the first item of a collection
(first '(3 1 4)) ; -> 3

;; 'second' takes the second item of a collection
(second '(3 1 4)) ; -> 1

;; 'take' takes the specified number of items from a collection
(take 3 '(3 1 4 1 5 9 2)) ; -> (3 1 4)

;; Use 'do' to evaluate some forms mainly for side effects
;; and take the result of the last form
(do (println "foo") 1) ; prints "foo" and returns 1

(cons 3 (do (println "foo") '(1))) ; prints "foo" and returns (3 1)

;; This equal to (cons 3 '(1)) except for printing "foo" when the
;; (do) forms evaluated.

(first (cons 3 (do (println "foo") '(1)))) ; prints "foo" and returns 3

;; This means the (do) form evaluated though the result isn't needed.

;; Use 'lazy-seq' to delay the evaluation until when the result is
;; really needed.

(first (cons 3 (lazy-seq (do (println "foo") '(1)))))
; doesn't print "foo" and returns 3

(second (cons 3 (lazy-seq (do (println "foo") '(1)))))
; prints "foo" and returns 1

;; This enable to create an infinite sequence,
;; without evaluating all items which never ends.
(defn conseq [s] (cons s (lazy-seq (conseq (inc s)))))

(take 10 (conseq 1)) ; -> (1 2 3 4 5 6 7 8 9 10)

;; Digits beginning with 1-9, represent a dicimal integer
;; of a class java.lang.Long
(type 1000000000) ; -> java.lang.Long

;; When a literal number exceeds the range of Long
;; It is treated as a BigInt
(type 10000000000000000000) ; -> clojure.lang.BigInt

;; But the calculation result of some Longs exceeds the range of Long,
;; it isn't casted to a BigInt automatically

(* 1000000000 1000000000) ; -> 1000000000000000000

(* 10000000000 10000000000) ; -> ArithmeticException integer overflow

;; Use suffix 'N' to write a BigInt literal
(* 10000000000N 10000000000N) ; -> 100000000000000000000N

;; If one of calculation argument is a BigInt,
;; The result is casted to a BigInt automatically

(* 10000000000N 10000000000) ; -> 100000000000000000000N

(* 10000000000 10000000000N) ; -> 100000000000000000000N

;; Now you can write a 'fibs' function, which accepts the first two
;; terms of a fibonacci sequence and returns an infinite fibonacci
;; sequence.
;; And you can take any number of terms from the infinite sequence
;; with 'take'.

plex02hints.js

/****************************************************************
   Without Lazy Evaluation
****************************************************************/
function fibs(a, b) {
  return [a, fibs(b, a + b)];
}

function take(n, ls) {
  var i, r = [];
  for (i = 0; i < n; i++) {
    r.push(ls[0]);
    ls = ls[1];
  }
  return r;
}

take(100, fibs(1, 1));
// -> RangeError: Maximum call stack size exceeded

// Before the evaluation of 'take' invoked, a processor
// try to evaluate 'fibs(1, 1)', which needs 'fibs(1, 1 + 1)',
// which needs 'fibs(2, 2 + 1)', which needs 'fibs(3, 3 + 2)'
// and so on.
// The evaluation doesn't finish until the stack overflows.

/****************************************************************
   Lazy Evaluation
****************************************************************/
function fibs(a, b) {
  return [a, function(){return fibs(b, a + b);}];
}

function take(n, ls) {
  var i, r = [];
  for (i = 0; i < n; i++) {
    r.push(ls[0]);
    ls = ls[1]();
  }
  return r;
}

take(100, fibs(1, 1));

// -> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
//     2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
//     317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
//     14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
//     267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073,
//     4807526976, 7778742049, 12586269025, 20365011074, 32951280099,
//     53316291173, 86267571272, 139583862445, 225851433717, 365435296162,
//     591286729879, 956722026041, 1548008755920, 2504730781961,
//     4052739537881, 6557470319842, 10610209857723, 17167680177565,
//     27777890035288, 44945570212853, 72723460248141, 117669030460994,
//     190392490709135, 308061521170129, 498454011879264, 806515533049393,
//     1304969544928657, 2111485077978050, 3416454622906707,
//     5527939700884757, 8944394323791464, 14472334024676220,
//     23416728348467684, 37889062373143900, 61305790721611580,
//     99194853094755490, 160500643816367070, 259695496911122560,
//     420196140727489660, 679891637638612200, 1100087778366101900,
//     1779979416004714000, 2880067194370816000, 4660046610375530000,
//     7540113804746346000, 12200160415121877000, 19740274219868226000,
//     31940434634990100000, 51680708854858330000, 83621143489848430000,
//     135301852344706760000, 218922995834555200000, 354224848179262000000 ]

// The stack doesn't overflow.
// But a double precision floating point number can't represent
// the valid 100th term of the sequence.

plex02spec.md

Given 2 natural numbers as a₁ and a₂, a_n is defined by the equation
a_n = a_n-1 + a_n-2
. Write code to get the sequence from a₁ to a_n for arbitrary a₁, a₂ and n.
You must do it by

• creating an infinite fibonacci sequence from specified a₁ and a₂ and
• taking a specified number of elements from a sequence.