From: jzakiya <jzakiya@...>
Date: 2009-12-19T09:05:18+09:00
Subject: Re: Question about sum of fibonacci sequene [PROJECT EULER]

On Dec 18, 6:28 pm, Panagiotis Atmatzidis <a...@convalesco.org> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hello,
> On 18 Δεκ 2009, at 10:23 μ.μ., Rob Biedenharn wrote:
>
>
>
> > On Dec 18, 2009, at 2:50 PM, Panagiotis Atmatzidis wrote:
>
> >> -----BEGIN PGP SIGNED MESSAGE-----
> >> Hash: SHA1
>
> >> Dear Sirs,
>
> >> Just to improve my programming skills and experience I found amusing solving problems like the ones posed by project Euler. Doing so, using Ruby is a joy, compared to Objective-C that I've used for the same purpose in the past.
>
> >> I'm stuck in the second problem though. Here is the issue:
>
> >> 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-valued terms in the sequence which do not exceed four million.
>
> >> I think that my code solves it. Works when I test it to smaller fractions, can someone reply if there's something wrong with this snippet:
> >> - ---------------
> >> # fibonacci
>
> >> a = 1
> >> b = 0
> >> sum = 0
> >> while a <= 4000000
> >> # get the old value of "a"
> >> c = a + b
> >> #puts c
> >> if (c % 2 != 0)
>
> > Note: c % 2 != 0 is only true for ODD values of c and you wanted EVEN values.  Change the 4000000 to be 10 and you ought to see the difference: 1, 2, 3, 5, 8 means 1+3+5=9 for odds and 2+8=10 for evens
>
> omg. I missread that part. Yes I thought it was asking for odd numbers... sorry lol.
>
>
>
> >> sum = sum + c
>
> > you could do:
> > puts [ c, sum ].inspect
> > to see the c's that are being added
>
> thanks for the hint.
>
>
>
>
>
> >> end
> >> b = a
> >> a = c
> >> end
>
> >> puts sum
> >> - ---------------
>
> >> Well my result is: 10316618 . I know that the original Fibonacci sequence will have a (+1) in the beginning of the loop, but (probably) for the sake of convenience is ignored. The system however returns a "false error" in both 10316618 and 10316618 + 1.
>
> > Your sequence will be 1, 1, 2, 3, 5, 8, 13, ...
> > If you initialize b=1, then you should get 1, 2, 3, 5, 8, 13, ...
>
> >> Thanks in advanced & best regards
>
> >> Panagiotis (atmosx) Atmatzidis
>
> >> email: a...@convalesco.org
> >> URL:  http://www.convalesco.org
>
> > Once you get the right answer, you should think about why the value of your first guess is off to the degree that it is.
>
> > -Rob
>
> > Rob Biedenharn            http://agileconsultingllc.com
> > R...@AgileConsultingLLC.com
>
> Thanks for the pointers
>
> Panagiotis (atmosx) Atmatzidis
>
> email:  a...@convalesco.org
> URL:    http://www.convalesco.org
> GnuPG ID: 0xFC4E8BB4
> gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4
> - --
> The wise man said: "Never argue with an idiot. They bring you down to their level and beat you with experience."
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG/MacGPG2 v2.0.12 (Darwin)
>
> iEYEARECAAYFAkssD/0ACgkQrghUb/xOi7QdCACbBVk4GNr60LnD4wF1GH3itZPg
> GQYAmQHTtle9EuakjDEsZ0iLjN06Fa84
> =2cfD
> -----END PGP SIGNATURE-----

Just a quick tip for you.

To check for (odd/even)ness:

Instead of doing this: if (c % 2 != 0)
which uses the modulo operator '%' which is
"expensive" in terms of cpu cycles, because it
performs (with a direct implementation) a (hardware)
division operation, do this instead:

# To check if integer c is even (true)
if (c & 1 == 0)

# To check if integer c is odd (true)
if (c & 1 == 1)

'&' bitwise ANDs the integers c with 1.
If c is even then its lsb (least significant bit) is '0'
if odd it's '1'.

The '&' operation is done in most modern CPUs as a
single cycle hardware bitwise register operation and
is much faster than the modulo operation '%'

It makes a big difference if you're looping through
that test a lot of times. Benchmark the comparisons
as an exercise to convince yourself.