Question about sum of fibonacci sequene

Ruby
1

-----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)
sum = sum + c
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.

Thanks in advanced & best regards

Panagiotis (atmosx) Atmatzidis

email: [email protected]
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)

iEYEARECAAYFAksr3P4ACgkQrghUb/xOi7Sj3ACfRTXLtHk9vhUuPJ9Ul2o2jlor
mLkAoJGFCERzUJsXjdrnNeYAhXAqn2wf
=v8zV
-----END PGP SIGNATURE-----

2

On Dec 18, 2009, at 2:50 PM, Panagiotis A. wrote:

I’m stuck in the second problem though. Here is the issue:
I think that my code solves it. Works when I test it to smaller
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

sum = sum + c

you could do:
puts [ c, sum ].inspect
to see the c’s that are being added

(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: [email protected]
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 B. http://agileconsultingllc.com
[email protected]

3

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello,
On 18 Δεκ 2009, at 10:23 μ.μ., Rob B. wrote:

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.

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email: [email protected]
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-----

4

On Dec 18, 6:28Â pm, Panagiotis A. [email protected] wrote:

-----BEGIN PGP SIGNED MESSAGE-----
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
while a <= 4000000

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.
email: Â [email protected]
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.

5

On Sat, Dec 19, 2009 at 1:20 AM, W. James [email protected] wrote:

same purpose in the past.
not exceed four million.
c = a + b

while a <= 4_000_000

One of my favourite bits of sample ruby code is the self memoizing
Fibonacci
hash, and since the 3rd element of each Fibonacci sequence is the even
one
( odd + even = odd; even + odd = odd; odd + odd = even; and so on … )
you
only need to add the 3rd elements of the hash together, which is what
the
second automemoizing hash will do. Then find the first one that is >
4,000,000
and print it. The thing that I like about this approach is that if you
need
the
one before you hit the max limit, it is already calculated in the
previous
hash
key so you just need the EFib[n-1] value. It’s not as quick as the
straight
sum+=a if a.even? code, or as easy to understand, but it’s a useful
technique
to have in your armoury.

or to express it in code:

require ‘rubygems’
require ‘benchmark’
MAX_FIB=4_000_000

Benchmark.bm { |x|
x.report('hash: '){
Fib = Hash.new{ |h,n| h[n] = n<2 ? n : h[n-1]+h[n-2] }
EFib = Hash.new{ |h,n| h[n] = n<1 ? 0 : h[n-1]+Fib[n*3] }
puts(EFib[(1…MAX_FIB).detect {|n| EFib[n]>MAX_FIB}])
}
x.report('add: ') {
sum = 0
a,b = 1,1
while a <= MAX_FIB
sum += a if a.even?
a,b = b,a+b
end
puts(sum)
}
}

Best wishes,
Mac

6

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thank you all for the very interesting pointers :slight_smile:

Panagiotis (atmosx) Atmatzidis

email: [email protected]
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)

iEYEARECAAYFAksscfIACgkQrghUb/xOi7Sn0gCfRFNmKgHj/iY2B2VwQx57GrNt
zqsAn3xYLH21uYnq6AFJcSjpRBL9b+aG
=7HwR
-----END PGP SIGNATURE-----

7

Panagiotis A. wrote:

I’m stuck in the second problem though. Here is the issue:
I think that my code solves it. Works when I test it to smaller
if (c % 2 != 0)
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.

Thanks in advanced & best regards

sum = 0
a,b = 1,1
while a <= 4_000_000
sum += a if a.even?
a,b = b,a+b
end

p sum

8

Shot (Piotr S.):

Better yet, use
if c.even?
or
if c.even?
(which are both more readable and do the above binary checks in C).

Or even c.odd?, of course.

— Shot (sorry!)

9

jzakiya:

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)

Better yet, use
if c.even?
or
if c.even?
(which are both more readable and do the above binary checks in C).

— Shot

10

Not efficient but with no explicit loop (while…)

fibonacci = (1…100).inject(f = [1,1]) {|f, n| f.insert(-1,(f[-2] +
f[-1])) }
fibonacci.delete_if {|n| n>= 4_000_000 or n.odd?}
p fibonacci.inject(0) {|s,n| s + n}

one line:
p (1…100).inject(f = [1,1]) {|f, n| f.insert(-1,(f[-2] + f[-1]))
}.delete_if {|n| n>= 4_000_000 or n.odd?}.inject(0) {|s,n| s + n}