hai guys,
i came across "Project Euler" while i was searching for some problems
to work on. i find a problem related to Fibonacci numbers.
Statement:-- Find the sum of all the even terms in the Fibonacci
sequence below one million.
OK, i solved it by writing these functions & it works correctly:
(defun fibo-million (bound)
(do ((n 0 (+ n 1))
(sum 0))
((> n bound) sum)
(if (evenp (fibo n))
(setq sum (+ sum (fibo n))))))
;; helper-function for fibo-million
;; computes the fibonacci number for the given number
(defun fibo (n)
(cond ((= n 0) 0)
((= n 1) 1)
(t (+ (fibo (- n 1))
(fibo (- n 2))))))
Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
minutes waiting at REPL but REPL was still calculating.....
WHY? because the helper-function named "fibo" was taking too long to
compute fib 100.
then i thought of writing an iterative version of it but failed to
think of anything. i tried to write using DO but was not able to come
up even with 2 lines of code.
do you have any idea for computing a fibonacci number using an
iterative method?
( i once saw both styles for computing a factorial, recursive version
took long time but ate less memory whereas iterative version was quick
and ate lots of memory)
thanks
"arnuld"
On 2006-07-22 08:09:49 -0400, "arnuld" <·······@gmail.com> said:
> do you have any idea for computing a fibonacci number using an
> iterative method?
Though not strictly iterative, this will compute (fib (expt 10 6)) in
about 2 seconds on my machine under sbcl.
Using this version of fib to do your (fibo-million 100) takes 1.1e-4 seconds.
With some sort of memoization or caching your problem shouldn't take
too long to compute.
You might need to define fib-aux separately rather than using labels to
get your particular memoization facility to memoize it.
btw, your version of fibo-million might be computing (fibo n) twice
depending on how smart your compiler is - you might want to use
something like (let (current (fibo n))) and use this current value
everywhere else in each iteration.
(defun fib (x)
(declare (optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))
(integer x n))
(if (< x 1) 0
(let ((n (1- x)))
(labels ((fib-aux (number)
(case number
((0) (values 1 0))
((1) (values 0 1))
(otherwise (let ((k (floor number 2)))
(multiple-value-bind (a b) (fib-aux k)
(let* ((aa (* a a))
(bb (* b b))
(ab2 (* 2 a b))
(ab2bb (+ ab2 bb)))
(if (= number (* 2 k))
(values (+ aa bb) ab2bb)
(values ab2bb (+ ab2bb aa bb))))))))))
(if (<= n 1) 1
(let ((k (floor n 2)))
(multiple-value-bind (a b) (fib-aux k)
(let ((ab (+ a b)))
(if (= n (* 2 k))
(+ (* ab ab) (* b b))
(+ (* ab ab) (* 2 b ab)))))))))))
regards,
Ralph
On 22 Jul 2006 05:09:49 -0700, "arnuld" <·······@gmail.com> tried to
confuse everyone with this message:
>
>do you have any idea for computing a fibonacci number using an
>iterative method?
>
How about:
(defun fibo (x) (round (/ (expt (/ (1+ (sqrt 5)) 2) x) (sqrt 5)))
--
|Don't believe this - you're not worthless ,gr---------.ru
|It's us against millions and we can't take them all... | ue il |
|But we can take them on! | @ma |
| (A Wilhelm Scream - The Rip) |______________|
Timofei Shatrov wrote:
> How about:
>
> (defun fibo (x) (round (/ (expt (/ (1+ (sqrt 5)) 2) x) (sqrt 5)))
Won't work due to overflow. The OP wants to sum F_i for 0<i<1000000.
arnuld <·······@gmail.com> wrote:
> hai guys,
>
> i came across "Project Euler" while i was searching for some problems
> to work on. i find a problem related to Fibonacci numbers.
>
[...]
>
> do you have any idea for computing a fibonacci number using an
> iterative method?
>
(defun fib (n)
(loop
for f0 = 1 then f1
for f1 = 1 then f2
for f2 = 1 then (+ f1 f0)
repeat (1- n)
finally (return f2)))
You can solve your problem by augmenting the loop:
(defun project-euler (bound)
(loop
for f0 = 1 then f1
for f1 = 1 then f2
for f2 = (+ f1 f0)
while (< f2 bound)
when (evenp f2)
sum f2))
Since the first two fibonnaci numbers are odd, we start with f(2) = 2
and sum all of the even terms which are less than "bound".
Bob Felts wrote:
> arnuld <·······@gmail.com> wrote:
>
> > hai guys,
> >
> > i came across "Project Euler" while i was searching for some problems
> > to work on. i find a problem related to Fibonacci numbers.
> >
> [...]
> >
> > do you have any idea for computing a fibonacci number using an
> > iterative method?
> >
>
> (defun fib (n)
> (loop
> for f0 = 1 then f1
> for f1 = 1 then f2
> for f2 = 1 then (+ f1 f0)
> repeat (1- n)
> finally (return f2)))
>
> You can solve your problem by augmenting the loop:
>
> (defun project-euler (bound)
> (loop
> for f0 = 1 then f1
> for f1 = 1 then f2
> for f2 = (+ f1 f0)
> while (< f2 bound)
> when (evenp f2)
> sum f2))
>
> Since the first two fibonnaci numbers are odd, we start with f(2) = 2
> and sum all of the even terms which are less than "bound".
I've already done that project Euler problem. I used this method
exactly.
One difference. If I remember right, the recursion relation specified
on the problem page stated that F1 = 1 and F2 = 2 instead of 1, 1.
Not actually a programming concern, but it makes certain you get the
right answer.
> (defun fib (n)
> (loop
> for f0 = 1 then f1
> for f1 = 1 then f2
> for f2 = 1 then (+ f1 f0)
> repeat (1- n)
> finally (return f2)))
yes, it works
> You can solve your problem by augmenting the loop:
>
> (defun project-euler (bound)
> (loop
> for f0 = 1 then f1
> for f1 = 1 then f2
> for f2 = (+ f1 f0)
> while (< f2 bound)
> when (evenp f2)
> sum f2))
according to this:
(project-euler 6) = 2
(project-euler 10) = 10
WRONG.
"arnuld"
arnuld <·······@gmail.com> wrote:
> > (defun fib (n)
> > (loop
> > for f0 = 1 then f1
> > for f1 = 1 then f2
> > for f2 = 1 then (+ f1 f0)
> > repeat (1- n)
> > finally (return f2)))
>
> yes, it works
>
>
> > You can solve your problem by augmenting the loop:
> >
> > (defun project-euler (bound)
> > (loop
> > for f0 = 1 then f1
> > for f1 = 1 then f2
> > for f2 = (+ f1 f0)
> > while (< f2 bound)
> > when (evenp f2)
> > sum f2))
>
> according to this:
> (project-euler 6) = 2
> (project-euler 10) = 10
>
> WRONG.
>
What should they be?
The first Fibonacci numbers less than 6 are:
(1 1 2 3 5). The sum of the even one is 2.
The Fibonacci numbers less than 10 are:
(1 1 2 3 5 8), of which the sum of the even ones is 2 + 8 = 10.
Now, if the problem is to calculate N terms of the Fibonacci series and
take the sum of the even ones, then the code is equally simple:
(defun euler-project (n)
(loop
for f0 = 1 then f1
for f1 = 1 then f2
for f2 = 1 then (+ f1 f0)
repeat (1- n)
when (evenp f2)
sum f2))
On 2006-07-23 19:24:29 -0400, ····@stablecross.com (Bob Felts) said:
> What should they be?
>
> The first Fibonacci numbers less than 6 are:
> (1 1 2 3 5). The sum of the even one is 2.
>
> The Fibonacci numbers less than 10 are:
> (1 1 2 3 5 8), of which the sum of the even ones is 2 + 8 = 10.
After consulting the project euler web site I now see that the problem
posed is much less daunting - its just the sum of all the even
fibonacci numbers which are themselves less than 1 million, not the sum
of all the even (fib n) where *n* is less than 1 million.
Using the version of fib I posted earlier this can be done in a tiny
fraction of a second on this iMac:
CL-USER> (time (fib-evens 1000000))
Evaluation took:
0.0 seconds of real time
1.4e-5 seconds of user run time
1.e-6 seconds of system run time
0 page faults and
0 bytes consed.
1089154
;; fib-evens
(defun fib-evens (limit)
"find the sum of all the even fibonacci numbers less than 1 million"
(declare (optimize (speed 3) (safety 0)) (fixnum limit))
(loop for i from 1
as current = (fib i)
while (< current limit)
when (evenp current) sum current))
;; fib from the other day
(defun fib (x)
(declare (optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))
(integer x n))
(if (< x 1) 0
(let ((n (1- x)))
(labels ((fib-aux (number)
(case number
((0) (values 1 0))
((1) (values 0 1))
(otherwise (let ((k (floor number 2)))
(multiple-value-bind (a b) (fib-aux k)
(let* ((aa (* a a))
(bb (* b b))
(ab2 (* 2 a b))
(ab2bb (+ ab2 bb)))
(if (= number (* 2 k))
(values (+ aa bb) ab2bb)
(values ab2bb (+ ab2bb aa bb))))))))))
(if (<= n 1) 1
(let ((k (floor n 2)))
(multiple-value-bind (a b) (fib-aux k)
(let ((ab (+ a b)))
(if (= n (* 2 k))
(+ (* ab ab) (* b b))
(+ (* ab ab) (* 2 b ab)))))))))))
regards,
Ralph
From: Patrick Frankenberger
Subject: Re: iterative-version for computing a Fibonacci number
Date:
Message-ID: <e9t6k5$on4$03$1@news.t-online.com>
arnuld wrote:
> Statement:-- Find the sum of all the even terms in the Fibonacci
> sequence below one million.
>
> OK, i solved it by writing these functions & it works correctly:
>
> (defun fibo-million (bound)
> (do ((n 0 (+ n 1))
> (sum 0))
> ((> n bound) sum)
> (if (evenp (fibo n))
> (setq sum (+ sum (fibo n))))))
>
>
> ;; helper-function for fibo-million
> ;; computes the fibonacci number for the given number
> (defun fibo (n)
> (cond ((= n 0) 0)
> ((= n 1) 1)
> (t (+ (fibo (- n 1))
> (fibo (- n 2))))))
>
>
> Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
> minutes waiting at REPL but REPL was still calculating.....
You might find that helpful:
(defun memoize (name)
"written ad-hoc, deficient in several ways"
(let ((fun (symbol-function name))
(ht (make-hash-table)))
(setf (symbol-function name)
(lambda (n)
(if (gethash n ht)
(gethash n ht)
(setf (gethash n ht) (funcall fun n)))))))
Use it like that (memoize 'fibo) and your program will be fast enough
for most purposes.
A faster way to directly compute fib is like that:
(defun fib (n)
(labels ((fibi (a b i)
(if (= i n)
b
(fibi b (+ a b) (1+ i)))))
(fibi 1 1 0)))
It's quite easy to adapt that way of computing fib to directly solve
your problem.
HTH,
Patrick
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: iterative-version for computing a Fibonacci number
Date:
Message-ID: <87psfxiuu3.fsf@qrnik.zagroda>
Patrick Frankenberger <···············@gmx.net> writes:
> Use it like that (memoize 'fibo) and your program will be fast enough
> for most purposes.
Not necessarily: recursive calls inside FIBO may refer to the old
version.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Le Sat, 22 Jul 2006 16:21:24 +0200, Marcin 'Qrczak' Kowalczyk a écrit :
>> Use it like that (memoize 'fibo) and your program will be fast enough
>> for most purposes.
> Not necessarily: recursive calls inside FIBO may refer to the old
> version.
Then use the mzmoize package[1], which doesn't seem to have that
problem.
Quickly,
Nowhere man
[1] http://www.cliki.net/memoize
--
···········@levallois.eu.org
OpenPGP 0xD9D50D8A
From: Patrick Frankenberger
Subject: Re: iterative-version for computing a Fibonacci number
Date:
Message-ID: <e9ti6o$vgo$00$1@news.t-online.com>
Marcin 'Qrczak' Kowalczyk wrote:
> Patrick Frankenberger <···············@gmx.net> writes:
>
>> Use it like that (memoize 'fibo) and your program will be fast enough
>> for most purposes.
>
> Not necessarily: recursive calls inside FIBO may refer to the old
> version.
Yeah, I haven't checked under what circumstances the recursive call
calls the replacement function. It works with interpreted functions in
clisp, that is all that I have checked.
If the function to be memoized is declared notinline it is guaranteed to
work, isn't it?
"arnuld" <·······@gmail.com> writes:
> hai guys,
>
> i came across "Project Euler" while i was searching for some problems
> to work on. i find a problem related to Fibonacci numbers.
>
> Statement:-- Find the sum of all the even terms in the Fibonacci
> sequence below one million.
>
> OK, i solved it by writing these functions & it works correctly:
>
> (defun fibo-million (bound)
> (do ((n 0 (+ n 1))
> (sum 0))
> ((> n bound) sum)
> (if (evenp (fibo n))
> (setq sum (+ sum (fibo n))))))
>
>
> ;; helper-function for fibo-million
> ;; computes the fibonacci number for the given number
> (defun fibo (n)
> (cond ((= n 0) 0)
> ((= n 1) 1)
> (t (+ (fibo (- n 1))
> (fibo (- n 2))))))
>
>
> Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
> minutes waiting at REPL but REPL was still calculating.....
>
> WHY? because the helper-function named "fibo" was taking too long to
> compute fib 100.
Because you're computing an exponential number of times (fibo n) for
all n<100.
A quick and dirty solution to speed up your program is to memoize the
function fibo. It'll use O(n) space.
> then i thought of writing an iterative version of it but failed to
> think of anything. i tried to write using DO but was not able to come
> up even with 2 lines of code.
> do you have any idea for computing a fibonacci number using an
> iterative method?
Just start from 0 instead of n.
(defun fibo-i (n)
(labels ((fibo-i-1 (i f-1 f-2)
(if (= i n)
(+ f-1 f-2)
(fibo-i-1 (1+ i) (+ f-1 f-2) f-1))))
(fibo-i-1 0 1 -1)))
> ( i once saw both styles for computing a factorial, recursive version
> took long time but ate less memory whereas iterative version was quick
> and ate lots of memory)
For factionnal, the recursive one takes more memory than the iterative one:
(defun fact-r (n)
(if (= 1 n)
1 ; last factor, we still need to multiply.
(* n ; stacks up n
(fact-r (1- n))))) ; no tail call, we still need to multiply.
(defun fact-i (n)
(labels ((fact-i-1 (i f)
(if (= i n)
(* i f) ; last multiplication, we can exit.
(fact-i-1 (1+ i) (* i f))))) ; tail call, no stack used.
(fact-i-1 1 1)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
arnuld wrote:
> hai guys,
>
> i came across "Project Euler" while i was searching for some problems
> to work on. i find a problem related to Fibonacci numbers.
>
> Statement:-- Find the sum of all the even terms in the Fibonacci
> sequence below one million.
There's a way to do this in logarithmically many bignum operations.
This follows from the observation that the nth power of the
integer matrix
( 0 1 )
A = ( )
( 1 1 )
times the vector ( F_0 F_1 ) is the vector ( F_n F_{n+1} ).
So, compute 1 + A^2 + A^4 + ... + A^n. This is equal
to (A^2 - I)^-1 (A^{n+2) - I), which can be computed in O(log n)
operations.
Paul
Paul F. Dietz wrote:
> ( 0 1 )
> A = ( )
> ( 1 1 )
>
> times the vector ( F_0 F_1 ) is the vector ( F_n F_{n+1} ).
>
> So, compute 1 + A^2 + A^4 + ... + A^n. This is equal
> to (A^2 - I)^-1 (A^{n+2) - I), which can be computed in O(log n)
> operations.
i did not even get the "a,b,c" of this method. keep in mind that i am
pretty weak at maths.
arnuld wrote:
> Paul F. Dietz wrote:
> > ( 0 1 )
> > A = ( )
> > ( 1 1 )
> >
> > times the vector ( F_0 F_1 ) is the vector ( F_n F_{n+1} ).
> >
> > So, compute 1 + A^2 + A^4 + ... + A^n. This is equal
> > to (A^2 - I)^-1 (A^{n+2) - I), which can be computed in O(log n)
> > operations.
>
> i did not even get the "a,b,c" of this method. keep in mind that i am
> pretty weak at maths.
Take A to be the following 2x2 matrix (2 rows and 2 columns):
|1 1|
|1 0|
if you keep multiplying A by itself you get the following sequence:
A^2 =
|2 1|
|1 1|
A^3=
|3 2|
|2 1|
A^4=
|5 3|
|3 2|
A^5=
|8 5|
|5 3|
A^6=
|13 8|
|8 5|
A^7=
|21 13|
|13 8|
A^8=
|34 21|
|21 13|
and so on.
You will notice that the sequence of first numbers from each matrix is
the Fibonacci sequence.
Also note that the 'nth' power of A gives the 'n+1th' Fibonacci.
This technique is used in the Python code here:
http://en.wikipedia.org/wiki/Fibonacci_number_program#Matrix_equation
with reference to:
http://en.wikipedia.org/wiki/Exponentiating_by_squaring#Squaring_algorithm
(It in fact uses 3-tuples beginning with (1,1,0) because the symmetry
of the matrices in the sequence means that only three multiplications
are necessary).
Lisp and Scheme code (not using the matrix method) from the same page:
http://en.wikipedia.org/wiki/Fibonacci_number_program#Common_Lisp
http://en.wikipedia.org/wiki/Fibonacci_number_program#Scheme
hth
Gerard
(I am not a lisper, just lurking after reading this:
http://www.defmacro.org/ramblings/lisp.html )
arnuld wrote:
> Statement:-- Find the sum of all the even terms in the Fibonacci
> sequence below one million.
I would interpret this as: the sum of all F_i such that F_i is even and
F_i < 1000000...
> OK, i solved it by writing these functions & it works correctly:
>
> (defun fibo-million (bound)
> (do ((n 0 (+ n 1))
> (sum 0))
> ((> n bound) sum)
> (if (evenp (fibo n))
> (setq sum (+ sum (fibo n))))))
... but this program tries to compute the sum of all even F_i with 0 < i
< 1000000. Computing F_1000000 alone takes me 40 seconds of processor
time with a log-time algorithm, and yields a 208988 digit number.
> ;; helper-function for fibo-million
> ;; computes the fibonacci number for the given number
> (defun fibo (n)
> (cond ((= n 0) 0)
> ((= n 1) 1)
> (t (+ (fibo (- n 1))
> (fibo (- n 2))))))
:)
This solves the problem as I interpret it in linear time (exponential in
the number of bits):
(defun fib-sum-even-terms (bound)
(labels ((iter (a b sum)
(if (>= a bound)
sum
(iter b (+ a b) (if (evenp a) (+ a sum) sum)))))
(iter 0 1 0)))
But Shatrov's suggestion works, too.
arnuld wrote:
> do you have any idea for computing a fibonacci number using an
> iterative method?
Yes:
;;;; fibonacci.lisp
(defun %fibonacci-iter (n)
(declare (optimize (speed 3) (safety 0)
(space 0) (debug 0) (compilation-speed 0)))
(check-type n (integer 0 *))
(labels ((mul (a b)
(vector (+ (* (svref a 0) (svref b 0))
(* (svref a 2) (svref b 1)))
(+ (* (svref a 0) (svref b 1))
(* (svref a 1) (svref b 3)))
(+ (* (svref a 0) (svref b 2))
(* (svref a 2) (svref b 3)))
(+ (* (svref a 2) (svref b 1))
(* (svref a 3) (svref b 3)))))
(mexpt (a k)
(let ((x #(1 0 0 1)))
(loop :until (= k 0)
:do (if (evenp k)
(setf a (mul a a)
k (/ k 2))
(setf x (mul x a)
k (1- k))))
x)))
(if (= 0 n) 1
(let ((m (mexpt #(0 1 1 1) (1- n))))
(+ (svref m 2) (svref m 3))))))
(defun fibonacci (n)
(check-type n (integer 0 *))
(cond ((= 0 n) 1)
((= 1 n) 1)
(t (+ (%fibonacci-iter (- n 1))
(%fibonacci-iter (- n 2))))))
;;; eof
CL-USER> (time (fibonacci 100000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.31 seconds of real time
; 0.296018 seconds of user run time
; 0.0 seconds of system run time
; 873,556,996 CPU cycles
; 0 page faults and
; 1,571,968 bytes consed.
resulting number has over 20000 decimal digits.
arnuld wrote:
[...]
> Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
> minutes waiting at REPL but REPL was still calculating.....
>
> WHY? because the helper-function named "fibo" was taking too long to
> compute fib 100.
>
> then i thought of writing an iterative version of it but failed to
> think of anything. i tried to write using DO but was not able to come
> up even with 2 lines of code.
Hi, perhaps someone can help me translate my Python version? I'm slowly
learning Lisp, but I'm out of my league on translating something like
this still :-(
def fib(n): # generate the first n numbers in the fibonacci sequence
a,b = 0,1 # pairwise assignment a <- 0, b <-1
for i in xrange(n-1): # i gets [0,n-1)
yield b # save state, yield b to calling context
a,b = b,a+b # return to here from calling context
return
# sum all numbers, n, coming from the fib generator if they're even
x = sum(n for n in fib(200000) if n%2==0)
it does 100000 in ~14 secs and 200000 in ~56 secs (the length of x is
20899 for 100K and 41797 for 200K).
-- bjorn
On 2006-07-27 19:40:32 -0400, "thebjorn"
<··························@gmail.com> said:
> Hi, perhaps someone can help me translate my Python version?
(defun fib (x)
(do ((a 0 b) ;; do loop variable a is initially 0, then b
(b 1 (+ a b)) ;;loop variable b is initially 1 then a + b
(i 1 (1+ i))) ;;loop index incremented by 1 each go round
((> i x) a))) ;;termination condition - when index passes x stop
;; and return a
(defun fib-evens (limit)
"find the sum of all the even fibonacci numbers less than 1 million"
(loop for i from 1 ;;loop index starts at 1 implicitly incremented by 1
as current = (fib i) ;;compute fib of the current index
while (< current limit) ;;stop if index exceeds limit
when (evenp current) sum current)) ;;sum all the even fibs and
return this sum
CL-USER> (time (fib-evens 1000000)) ;; time the sum of all the even
fibs less than a million
Evaluation took:
0.0 seconds of real time
8.e-6 seconds of user run time ;;; took about one
onehundredthousandth of a second
1.e-6 seconds of system run time
0 page faults and
0 bytes consed.
1089154 ;; here's your answer
hth,
Ralph
On 2006-07-27 21:57:45 -0400, Raffael Cavallaro
<················@pas-d'espam-s'il-vous-plait-mac.com> said:
> (defun fib-evens (limit)
> "find the sum of all the even fibonacci numbers less than 1 million"
> (loop for i from 1 ;;loop index starts at 1 implicitly incremented by 1
> as current = (fib i) ;;compute fib of the current index
> while (< current limit) ;;stop if index exceeds limit
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
sorry, this comment should read ;; stop if current is greater than or
equal to limit
Raffael Cavallaro wrote:
> On 2006-07-27 21:57:45 -0400, Raffael Cavallaro
> <················@pas-d'espam-s'il-vous-plait-mac.com> said:
>
> > (defun fib-evens (limit)
> > "find the sum of all the even fibonacci numbers less than 1 million"
> > (loop for i from 1 ;;loop index starts at 1 implicitly incremented by 1
> > as current = (fib i) ;;compute fib of the current index
> > while (< current limit) ;;stop if index exceeds limit
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> sorry, this comment should read ;; stop if current is greater than or
> equal to limit
I was summing over the sequence up to the limit'th fibonacci, so
shouldn't that be (< i limit) ? If I change it to that I get similar
answers for small values, but it gets prohibitively slow on larger
ones...
-- bjorn
On 2006-07-28 05:54:08 -0400, "thebjorn"
<··························@gmail.com> said:
> I was summing over the sequence up to the limit'th fibonacci, so
> shouldn't that be (< i limit) ? If I change it to that I get similar
> answers for small values, but it gets prohibitively slow on larger
> ones...
If you read up thread you'll see that I originally thought so too, but
after visiting the Project Euler web page It appears that the problem
is stated as:
"Each new term in the Fibonacci sequence is generated by adding the
previous two terms. By starting with 1 and 2, the first 10 terms will
be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even terms in the sequence below one million."
^^^^^^^^^^^^^^^^
So they appear to be looking for the sum of all the even fibonacci
numbers which are *themselves* below 1 million, not the sum of all the
nth fibonacci number where n is less than 1 million.
Raffael Cavallaro wrote:
> On 2006-07-28 05:54:08 -0400, "thebjorn"
> <··························@gmail.com> said:
>
> > I was summing over the sequence up to the limit'th fibonacci, so
> > shouldn't that be (< i limit) ? If I change it to that I get similar
> > answers for small values, but it gets prohibitively slow on larger
> > ones...
>
> If you read up thread you'll see that I originally thought so too, but
> after visiting the Project Euler web page It appears that the problem
> is stated as:
[...]
Yeah, but I thought the original problem was much more interesting :-)
-- bjorn
On 2006-07-28 16:15:04 -0400, "thebjorn"
<··························@gmail.com> said:
> Yeah, but I thought the original problem was much more interesting :-)
Me too - I suppose you could solve the other one - the sum of the even
(fib n) for n < a million - for more of a challenge.
thebjorn <··························@gmail.com> wrote:
+---------------
| Hi, perhaps someone can help me translate my Python version? I'm slowly
| learning Lisp, but I'm out of my league on translating something like
| this still :-(
|
| def fib(n): # generate the first n numbers in the fibonacci sequence
| a,b = 0,1 # pairwise assignment a <- 0, b <-1
| for i in xrange(n-1): # i gets [0,n-1)
| yield b # save state, yield b to calling context
| a,b = b,a+b # return to here from calling context
| return
|
| # sum all numbers, n, coming from the fib generator if they're even
| x = sum(n for n in fib(200000) if n%2==0)
|
| it does 100000 in ~14 secs and 200000 in ~56 secs (the length of x is
| 20899 for 100K and 41797 for 200K).
+---------------
Someone else showed you one possible translation to Lisp, but
I suspect that the following one is closer to the spirit of what
your Python code seems to be actually doing, that is, creating
a "generator". Since Common Lisp doesn't have user-visible
continuations per se, the usual idiom in CL is to make a
"function maker" which returns a closure which encapsulates
the "continuation state", which you can later call to produce
each successive element. Unlike your "fib(n)" above, the following
version does not put an arbitrary upper limit on the number of
elements returned; you control that externally in the caller.
My results with CMUCL (in 32-bit mode) on a 1.8 GHz Athlon64
were 3.18 s & 12.92 s, respectively [I included the "system time"
since CMUCL uses page-fault traps for GC], and gave the same
number of digits (20899 & 41797, resp.) for the results as yours:
> (defun make-fibber ()
(let ((a 0)
(b 1))
(lambda ()
(prog1 b
(psetf a b
b (+ a b))))))
MAKE-FIBBER
> (compile *)
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
MAKE-FIBBER
NIL
NIL
> (loop with fib = (make-fibber) ; quick test
for i below 10
collect (funcall fib))
(1 1 2 3 5 8 13 21 34 55)
> (defun sum-even-fibs (how-many)
(let ((x (loop with fib = (make-fibber)
for i below how-many
and n = (funcall fib)
when (evenp n)
sum n)))
(ceiling (log x 10))))
SUM-EVEN-FIBS
> (compile *)
; Compiling LAMBDA (HOW-MANY):
; Compiling Top-Level Form:
SUM-EVEN-FIBS
NIL
NIL
> (time (sum-even-fibs 100000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 3.18f0 seconds of real time
; 2.5f0 seconds of user run time
; 0.67f0 seconds of system run time
; 5,724,123,132 CPU cycles
; [Run times include 0.95f0 seconds GC run time]
; 0 page faults and
; 581,748,776 bytes consed.
;
20899
-0.6777344f0
> (time (sum-even-fibs 200000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 12.92f0 seconds of real time
; 10.33f0 seconds of user run time
; 2.59f0 seconds of system run time
; 23,287,767,118 CPU cycles
; [Run times include 4.07f0 seconds GC run time]
; 0 page faults and
; 2,320,568,856 bytes consed.
;
41797
-0.12109375f0
>
Also unlike yours [I think, as I'm not too sure about Python's
"yield" operator], the above version allows you to create multiple
independent "fib generators", and step them independently:
> (let ((fib-vec (coerce (loop for i below 3 collect (make-fibber))
'vector)))
(loop for i below 25 do
(let* ((index (random (length fib-vec)))
(fib (funcall (aref fib-vec index))))
(format t "Fibber #~d returned ~d~%" index fib))))
Fibber #2 returned 1
Fibber #1 returned 1
Fibber #1 returned 1
Fibber #2 returned 1
Fibber #0 returned 1
Fibber #2 returned 2
Fibber #0 returned 1
Fibber #2 returned 3
Fibber #2 returned 5
Fibber #1 returned 2
Fibber #1 returned 3
Fibber #2 returned 8
Fibber #1 returned 5
Fibber #0 returned 2
Fibber #0 returned 3
Fibber #2 returned 13
Fibber #0 returned 5
Fibber #0 returned 8
Fibber #2 returned 21
Fibber #1 returned 8
Fibber #0 returned 13
Fibber #0 returned 21
Fibber #0 returned 34
Fibber #2 returned 34
Fibber #1 returned 13
NIL
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
[...]
> > (defun make-fibber ()
> (let ((a 0)
> (b 1))
> (lambda ()
> (prog1 b
> (psetf a b
> b (+ a b))))))
>
[..]
> > (defun sum-even-fibs (how-many)
> (let ((x (loop with fib = (make-fibber)
> for i below how-many
> and n = (funcall fib)
> when (evenp n)
> sum n)))
> (ceiling (log x 10))))
Thanks (don't think I could have written that, but it's easy to read).
> > (time (sum-even-fibs 100000))
I got floating point overflow here running on CLisp (it was the easiest
accessible on xp at the time I downloaded it...) I'll look into CMUCL
over the weekend.
> Also unlike yours [I think, as I'm not too sure about Python's
> "yield" operator], the above version allows you to create multiple
> independent "fib generators", and step them independently:
>
> > (let ((fib-vec (coerce (loop for i below 3 collect (make-fibber))
> 'vector)))
> (loop for i below 25 do
> (let* ((index (random (length fib-vec)))
> (fib (funcall (aref fib-vec index))))
> (format t "Fibber #~d returned ~d~%" index fib))))
That would be something like this (trying to stay as close to your
semantics as possible):
# in 2.5+ generators are co-routines, so one could change the while
# stmt to while (yield b) so the calling context could shut it
down...
def fibg():
a,b = 0,1
while 1:
yield b
a,b = b,a+b
import random
fib_vec = [fibg() for i in range(3)]
for i in range(25):
index = random.choice(range(3))
fib = fib_vec[index].next() # call next on the generator at
index
print "Fibber %d returned %d" % (index, fib)
For simple stuff like this Python is quite expressive enough, however
earlier today I wrote:
valid1 = Customers.objects.filter(·················@')
where the Django framework parses out the Email field in a Customer
record and calls contains on it because it has noticed the double
underscore (*sigh*). So I guess we are doomed to reinvent significant
portions of Lisp yet again... but I digress :-)
Thanks for the code.
-- bjorn
thebjorn <··························@gmail.com> wrote:
+---------------
| > > (defun sum-even-fibs (how-many)
| > (let ((x (loop ... )))
| > (ceiling (log x 10))))
...
| > > (time (sum-even-fibs 100000))
|
| I got floating point overflow here running on CLisp (it was the easiest
| accessible on xp at the time I downloaded it...) I'll look into CMUCL
| over the weekend.
+---------------
It will certainly run much faster on CMUCL. But try this variation
on CLISP in the meantime: Replace the (CEILING (LOG X 10)) in
SUM-EVEN-FIBS with (CEILING (/ (INTEGER-LENGTH X) (LOG 10d0 2d0))).
That should run without overflow on CLISP.
But note that the latter formula doesn't always give *quite* the
same results, e.g., (sum-even-fibs 100000) ==> 20899 as before, but
(sum-even-fibs 200000) ==> 41798, one more than before. At the cost
of a little more run-time (~0.1 s more, on CMUCL), you can get a
better count of "digits" with (LENGTH (FORMAT NIL "~d" X)), which
once again gives 20899 & 41797, respectively.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
thebjorn wrote:
> arnuld wrote:
> [...]
> > Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
> > minutes waiting at REPL but REPL was still calculating.....
> >
> > WHY? because the helper-function named "fibo" was taking too long to
> > compute fib 100.
> >
> > then i thought of writing an iterative version of it but failed to
> > think of anything. i tried to write using DO but was not able to come
> > up even with 2 lines of code.
>
> Hi, perhaps someone can help me translate my Python version? I'm slowly
> learning Lisp, but I'm out of my league on translating something like
> this still :-(
>
> def fib(n): # generate the first n numbers in the fibonacci sequence
> a,b = 0,1 # pairwise assignment a <- 0, b <-1
> for i in xrange(n-1): # i gets [0,n-1)
> yield b # save state, yield b to calling context
> a,b = b,a+b # return to here from calling context
> return
>
> # sum all numbers, n, coming from the fib generator if they're even
> x = sum(n for n in fib(200000) if n%2==0)
>
> it does 100000 in ~14 secs and 200000 in ~56 secs (the length of x is
> 20899 for 100K and 41797 for 200K).
>
> -- bjorn
In MatzLisp (a.k.a. Ruby):
def fib( n )
a, b = 0, 1
n.times {
yield b
a, b = b, a+b }
end
sum = 0
fib( 100_000 ) { |n| sum += n if n % 2 == 0 }
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: iterative-version for computing a Fibonacci number
Date:
Message-ID: <87psfqq83n.fsf@qrnik.zagroda>
"William James" <·········@yahoo.com> writes:
> In MatzLisp (a.k.a. Ruby):
[...]
Ruby is about as far from Lisp as e.g. Python, Perl, Smalltalk,
Rebol, or JavaScript.
Please don't post Ruby code in response to people seeking help
with Lisp.
Or I will start replying with QrczakLisp (a.k.a. Kogut)...
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
William James wrote:
> thebjorn wrote:
> > arnuld wrote:
> > [...]
> > > Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
> > > minutes waiting at REPL but REPL was still calculating.....
> > >
> > > WHY? because the helper-function named "fibo" was taking too long to
> > > compute fib 100.
> > >
> > > then i thought of writing an iterative version of it but failed to
> > > think of anything. i tried to write using DO but was not able to come
> > > up even with 2 lines of code.
> >
> > Hi, perhaps someone can help me translate my Python version? I'm slowly
> > learning Lisp, but I'm out of my league on translating something like
> > this still :-(
> >
> > def fib(n): # generate the first n numbers in the fibonacci sequence
> > a,b = 0,1 # pairwise assignment a <- 0, b <-1
> > for i in xrange(n-1): # i gets [0,n-1)
> > yield b # save state, yield b to calling context
> > a,b = b,a+b # return to here from calling context
> > return
> >
> > # sum all numbers, n, coming from the fib generator if they're even
> > x = sum(n for n in fib(200000) if n%2==0)
> >
> > it does 100000 in ~14 secs and 200000 in ~56 secs (the length of x is
> > 20899 for 100K and 41797 for 200K).
> >
> > -- bjorn
>
> In MatzLisp (a.k.a. Ruby):
>
> def fib( n )
> a, b = 0, 1
> n.times {
> yield b
> a, b = b, a+b }
> end
>
> sum = 0
> fib( 100_000 ) { |n| sum += n if n % 2 == 0 }
A couple of suggestions:
1. Ruby code is not on-topic in comp.lang.lisp (are you lost?)
2. Ruby is not a dialect of Lisp. Matz may have referred to Ruby as
MatzLisp, but that doesn't mean he knows what he's talking about.
Indeed, he doesn't. Ruby is not Lisp; Ruby is not a dialect of Lisp.
Show me Ruby with CAR-CDR-CONS, s-expressions, the seven axioms,
special variables, macros, regular syntax with a reader, etc. and
_then_ you _might_ be able to call it MatzLisp. Pretending that Ruby
is a Lisp does not make you cooler.
3. Stop it.
From: Giorgos Keramidas
Subject: Re: iterative-version for computing a Fibonacci number
Date:
Message-ID: <867j14f8xe.fsf@gothmog.pc>
On 22 Jul 2006 05:09:49 -0700, "arnuld" <·······@gmail.com> wrote:
> hai guys,
>
> i came across "Project Euler" while i was searching for some problems
> to work on. i find a problem related to Fibonacci numbers.
>
> Statement:-- Find the sum of all the even terms in the Fibonacci
> sequence below one million.
>
> OK, i solved it by writing these functions & it works correctly:
>
> (defun fibo-million (bound)
> (do ((n 0 (+ n 1))
> (sum 0))
> ((> n bound) sum)
> (if (evenp (fibo n))
> (setq sum (+ sum (fibo n))))))
>
>
> ;; helper-function for fibo-million
> ;; computes the fibonacci number for the given number
> (defun fibo (n)
> (cond ((= n 0) 0)
> ((= n 1) 1)
> (t (+ (fibo (- n 1))
> (fibo (- n 2))))))
>
>
> Problem: i tried "fibo-million" with 100 as argument, i spent next 8.5
> minutes waiting at REPL but REPL was still calculating.....
>
> WHY? because the helper-function named "fibo" was taking too long to
> compute fib 100.
Sorry for replying so late to an old thread, but I've been away
from c.l.l for a while and I only just noticed this one.
You are computing (fib n) far too many times. One way to speed things
up a bit is to first write a function that returns a list of all the
Fibonacci numbers up to a given boundary:
CL-USER> (defun fib-bounded (boundary-value)
"Return a list of all the Fibonacci numbers smaller than
the given BOUNDARY-VALUE."
(let ((a 1) (b 1))
(loop while (< a boundary-value)
:collect a
:do (setq a b b (+ a b)))))
FIB-BOUNDED
CL-USER>
And then use other, existing Lisp functions to trim the list and
apply functions on the remaining Fibonacci numbers:
CL-USER> (remove-if-not #'evenp (fib-bounded 1000000))
(2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768
65536 131072 262144 524288)
CL-USER> (apply #'+ (remove-if-not #'evenp (fib-bounded 1000000)))
1048574
CL-USER> (time (apply #'+
(remove-if-not #'evenp
(fib-bounded 1000000))))
Evaluation took:
0.0 seconds of real time
2.2e-5 seconds of user run time
3.e-6 seconds of system run time
0 page faults and
8,160 bytes consed.
1048574
CL-USER>
This can be a lot faster than calculating the Fibonacci numbers
again and again every time you have to reach Fib(N). Using SBCL
0.9.15 on an Intel(R) Celeron(R) CPU 1.80GHz, with 512 MB of
physical memory, running FreeBSD 7.0-CURRENT with full kernel and
userland debugging turned on, I get the following here:
CL-USER> (defun fibonacci-sum-bounded (bound)
(apply #'+ (remove-if-not #'evenp (fib-bounded bound))))
FIBONACCI-SUM-BOUNDED
CL-USER> (profile fibonacci-sum-bounded)
; No value
CL-USER> (reset)
NIL
CL-USER> (loop for run below 1000
:do (fibonacci-sum-bounded (expt 10 6)))
NIL
CL-USER> (report)
seconds | consed | calls | sec/call | name
-----------------------------------------------------
0.001 | 507,800 | 1,000 | 0.000001 | FIBONACCI-SUM-BOUNDED
-----------------------------------------------------
0.001 | 507,800 | 1,000 | | Total
estimated total profiling overhead: 0.01 seconds
overhead estimation parameters:
3.6e-8s/call, 9.552e-6s total profiling, 4.632e-6s internal profiling
; No value
CL-USER>
Running 100,000 times instead of just 1,000 times, the results
are a little slower, but I'm not sure how much of this is caused
by interference from the profiler itself or by GC not recovering
memory from each run as fast the requests from new memory arrive:
CL-USER> (reset)
NIL
CL-USER> (loop for run below 100000
:do (fibonacci-sum-bounded (expt 10 6)))
NIL
CL-USER> (report)
seconds | consed | calls | sec/call | name
----------------------------------------------------------
0.385 | 51,080,968 | 100,000 | 0.000004 | FIBONACCI-SUM-BOUNDED
----------------------------------------------------------
0.385 | 51,080,968 | 100,000 | | Total
estimated total profiling overhead: 0.96 seconds
overhead estimation parameters:
3.6e-8s/call, 9.552e-6s total profiling, 4.632e-6s internal profiling
; No value
CL-USER>