Question about sum of fibonacci sequene [PROJECT EULER]

[Panagiotis Atmatzidis-2]

-----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: atma@...
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-----

[Rob Biedenharn-2]

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

>  sum = sum + c

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

> 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: atma@...
> 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
Rob@...

[Panagiotis Atmatzidis-2]

-----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: atma@...
>> 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
> Rob@...
>
>
>
>

Thanks for the pointers

Panagiotis (atmosx) Atmatzidis

email: atma@...
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-----

[jzakiya]

On Dec 18, 6:28 pm, Panagiotis Atmatzidis <a...@...> 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...@...
> >> 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...@...
>
> Thanks for the pointers
>
> Panagiotis (atmosx) Atmatzidis
>
> email:  a...@...
> 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.

[W. James]

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

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

p sum


--

[Paul Mckibbin]

On Sat, Dec 19, 2009 at 1:20 AM, W. James <w_a_x_man@...> wrote:

> 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)
> >   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
>
>
> sum = 0
> a,b = 1,1
> while a <= 4_000_000
>  sum += a if a.even?
>  a,b = b,a+b
> end
>
> p sum
>
>
> --
>
>
>

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

[Panagiotis Atmatzidis-2]

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


Thank you all for the very interesting pointers :-)


Panagiotis (atmosx) Atmatzidis

email: atma@...
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-----

[Shot (Piotr Szotkowski)]

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
--
To find a rhyme for silver,
A seemingly rhymeless rhyme,
Requires only will, ver-
bosity and time.
           [Willard R. Espy]

[Shot (Piotr Szotkowski)]

Shot (Piotr Szotkowski):

> 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!)
--
until programmers stop acting like obfuscation is morally hazardous,
they’re not artists, just kids who don’t want their food to touch.
                                                              [_why]

[Giampiero Zanchi]

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}

--
Posted via http://www.ruby-forum.com/.