Skip to content

Instantly share code, notes, and snippets.

@kohyama kohyama/plex02.clj
Created Oct 23, 2012

Embed
What would you like to do?
Excercise 02 Fibonacci Sequence
(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)
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]
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' ]
(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)
(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)
;; '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'.
/****************************************************************
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.

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

  • creating an infinite fibonacci sequence from specified a1 and a2 and
  • taking a specified number of elements from a sequence.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.