Asp Forum - Re: iterative-version for computing a Fibonacci number

William James

4/9/2015 8:03:00 PM

Raffael Cavallaro wrote:

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

Scheme:

(define (sum-even-fibs limit)
(let go ((sum 0) (a 0) (b 1))
(if (< b limit)
(go (+ sum (if (even? b) b 0)) b (+ a b))
sum)))

(sum-even-fibs 1000000)
===>
1089154

6 Answers

Kaz Kylheku

4/9/2015 9:05:00 PM

On 2015-04-09, WJ <w_a_x_man@yahoo.com> wrote:
> Raffael Cavallaro wrote:
>
>> > 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
>
> Scheme:
>
> (define (sum-even-fibs limit)
> (let go ((sum 0) (a 0) (b 1))
> (if (< b limit)
> (go (+ sum (if (even? b) b 0)) b (+ a b))
> sum)))

In this situation, the do loop is nicer; it juxtaposes together together the
variable names, their initial values and their next values.

$ txr -p "(zip '(sum a b) '(0 0 1) '((+ sum (if (even? b) b 0)) b (+ a b)))"
((sum 0 (+ sum (if (even? b) b 0))) (a 0 b) (b 1 (+ a b)))

Now paste that into a do:

(do ((sum 0 (+ sum (if (even? b) b 0)))
(a 0 b)
(b 1 (+ a b)))
((>= b limit) sum))

The "what can you do me for" way, rather than the silly "curse again, and
again" way.

Paul Rubin

4/9/2015 10:46:00 PM

Kaz Kylheku <kaz@kylheku.com> writes:
> (do ((sum 0 (+ sum (if (even? b) b 0)))
> (a 0 b)
> (b 1 (+ a b)))
> ((>= b limit) sum))
>
> The "what can you do me for" way, rather than the silly "curse again, and
> again" way.

I'd be interested in seeing an SRFI-45 or force/delay version that
separates generating the unbounded Fibonacci sequence, chopping it at
1000000, filtering to the evens, and adding up the truncating stream.
The Haskell equivalent is very natural:

fibs a b = a : fibs b (a+b)
main = print . sum . filter even . takeWhile (< 1000000) $ fibs 0 1

*Main> main
1089154

Kaz Kylheku

4/10/2015 5:29:00 AM

On 2015-04-09, Paul Rubin <no.email@nospam.invalid> wrote:
> Kaz Kylheku <kaz@kylheku.com> writes:
>> (do ((sum 0 (+ sum (if (even? b) b 0)))
>> (a 0 b)
>> (b 1 (+ a b)))
>> ((>= b limit) sum))
>>
>> The "what can you do me for" way, rather than the silly "curse again, and
>> again" way.
>
> I'd be interested in seeing an SRFI-45 or force/delay version that
> separates generating the unbounded Fibonacci sequence, chopping it at
> 1000000, filtering to the evens, and adding up the truncating stream.
> The Haskell equivalent is very natural:
>
> fibs a b = a : fibs b (a+b)
> main = print . sum . filter even . takeWhile (< 1000000) $ fibs 0 1
>
> *Main> main
> 1089154

That code has just given me a realization: I am missing a "lcons" macro
wrapper around the make-lazy-cons constructor in TXR Lisp:

With that, I can just use (lcons x y) to do the rough equivalent of Haskell's
lazy x : y, thereby expressing the fib in essentially the same way:

Code:

@(do
(defmacro lcons (car-form cdr-form)
(let ((lc (gensym)))
^(make-lazy-cons (lambda (,lc)
(rplaca ,lc ,car-form)
(rplacd ,lc ,cdr-form)))))

(defun fib2 (a b)
(lcons a (fib2 b (+ a b))))

(prinl [reduce-left + [keep-if evenp (first (partition-by (op < 1000000) (fib2 0 1)))]]))

Run:

$ txr fib2.txr
1089154

I don't have takeWhile, but partition-by for lazily partitioning a list will
do the job, followed by taking the first partition.

The last expr rewritten using a pipeline of partial application operations:

[(opip (partition-by (op < 1000000)) first (keep-if evenp) (reduce-left +) prinl)
(fib2 0 1)]

This lcons macro is definitely going into the language.

Kaz Kylheku

4/10/2015 5:44:00 AM

On 2015-04-10, Kaz Kylheku <kaz@kylheku.com> wrote:
> On 2015-04-09, Paul Rubin <no.email@nospam.invalid> wrote:
>> Kaz Kylheku <kaz@kylheku.com> writes:
>>> (do ((sum 0 (+ sum (if (even? b) b 0)))
>>> (a 0 b)
>>> (b 1 (+ a b)))
>>> ((>= b limit) sum))
>>>
>>> The "what can you do me for" way, rather than the silly "curse again, and
>>> again" way.
>>
>> I'd be interested in seeing an SRFI-45 or force/delay version that
>> separates generating the unbounded Fibonacci sequence, chopping it at
>> 1000000, filtering to the evens, and adding up the truncating stream.
>> The Haskell equivalent is very natural:
>>
>> fibs a b = a : fibs b (a+b)
>> main = print . sum . filter even . takeWhile (< 1000000) $ fibs 0 1
>>
>> *Main> main
>> 1089154
>
> That code has just given me a realization: I am missing a "lcons" macro
> wrapper around the make-lazy-cons constructor in TXR Lisp:
>
> With that, I can just use (lcons x y) to do the rough equivalent of Haskell's
> lazy x : y, thereby expressing the fib in essentially the same way:

I once posted this:

(defun fib ()
(let ((fib (list 1 1)))
(rplacd (cdr fib) [mapcar* + fib (rest fib)])
fib))

With lcons, this streamlines:

(defun fib ()
(let (fib)
(set fib (cons 1 (lcons 1 [mapcar* + fib (rest fib)])))))

Now just a suitably scoped let is needed to eliminate the assignment.

William James

11/26/2015 6:34:00 PM

WJ wrote:

> Raffael Cavallaro wrote:
>
> > > 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
>
> Scheme:
>
> (define (sum-even-fibs limit)
> (let go ((sum 0) (a 0) (b 1))
> (if (< b limit)
> (go (+ sum (if (even? b) b 0)) b (+ a b))
> sum)))
>
> (sum-even-fibs 1000000)
> ===>
> 1089154

Ocaml:

let only_even n = ((n+1) land 1) * n;;

let sum_even_fibs limit =
let rec go sum a b =
if b<limit then
go (sum + (only_even b)) b (a+b)
else
sum
in go 0 0 1 ;;

sum_even_fibs 1_000_000;;
===>
1089154

--
As more and more power gravitates in the capital, the more vital it becomes for
the corporate America to secure its interests by corrupting that seat of power.
www.kolumbus.fi/aquilon/america-middle-class-and-the-end-of-growth.htm

William James

2/7/2016 6:53:00 PM

WJ wrote:

> Raffael Cavallaro wrote:
>
> > > 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
>
> Scheme:
>
> (define (sum-even-fibs limit)
> (let go ((sum 0) (a 0) (b 1))
> (if (< b limit)
> (go (+ sum (if (even? b) b 0)) b (+ a b))
> sum)))
>
> (sum-even-fibs 1000000)
> ===>
> 1089154

MatzLisp (Ruby):

def sum_even_fibs limit
a,b,sum = 0,1,0
while b < limit
sum += b if b.even?
a,b = b,a+b
end
sum
end

sum_even_fibs 1_000_000
==>1089154

--
Elie [Wiesel] thus could have remained at Birkenau to await the Russians.
Although his father had permission to stay with him as a hospital patient or
orderly, father and son talked it over and decided to move out with the
Germans. --- Robert Faurisson

comp.lang.lisp

Re: iterative-version for computing a Fibonacci number

William James

Kaz Kylheku

Paul Rubin

Kaz Kylheku

Kaz Kylheku

William James

William James

x Login to ForumsZone