How could I neaten this code up.

Hi

Currently working through some of Project Eulers problems as mentioned in the forum discussion 'Best way(s) to master MATLAB'. I have created this code, it works but there is something about it I find messy. For a start I don't like all the declared variables.

function eusol2 = euler2(euin)

% for No's in fibonacci sequence < 4mil, sum all even No terms.

x = [1 2];
y = 1;
xout = 2;
fibMax = 0;

while fibMax < euin

      fibMax = x(1) + x(2);

      if fibMax < euin
              if mod(fibMax, 2) == 0;
                  xout = xout + fibMax;
              else

              end
      else

      end

      x(y) = fibMax;
      y = 3 - y;
      eusol2 = xout;
  end

Any suggestions or remarks

AD

[bym]

your first if-else-end block is unnecessary, because fibMax<euin is a condition of entering the while loop

[Jan]

@procsm: But the value of fibMax has been increased since the WHILE.

[Jan]

You started the sequence with [1,2] accidently instead of [1,1]. Using xout=2 instead of 0 compensates this such that the correct answer is calculated.

A very nice example for a "stealth bug": No effect for standard usage, generalising the function for any Fibonacci sequence [a,b] fails.

Answer 1

[Jan]

Your function looks fine already. Most of all it is very fast, e.g. twice as fast as Daniel's program.

The result is wrong, because you start with xout=2. The empty ELSE branch wastes time. The "if fibMax < euin" check can be omited, if fibMax is increased after adding the new term. I prefer meaningful names instead of x and y.

function out = euler2(limit)
accum  = [1, 1];  % [EDITED], was [1,2] as in the original question
index  = 1;
out    = 0;
fibMax = 0;

while fibMax < limit
  if mod(fibMax, 2) == 0
    out = out + fibMax;
  end
  fibMax = accum(1) + accum(2);
  accum(index) = fibMax;
  index        = 3 - index;
end

Of course Binet's formula would be more sophisticated. But calling this function 10'000 times with the input 4e6 needs 0.15438 seconds only.

The MOD(fibMax, 2) fails after 75 terms due to the limited precision. Exploiting the simple pattern of even terms might be interesting, but a further "improvement" of the function is of accademical interest only. For a practical use this function is eitehr fast enough, of a lookup table with the 75 values is faster brute-force approach.

[Daniel Shub]

You need to replace euin with limit in the while loop.

No question the 4 sums I was doing verses the 1 required sum will be faster; then again it let me get rid of a declared variable. I also do twice as much indexing/memory swapping, but it allows me to get rid of another declared variable.

[Daniel Shub]

I didn't know that the empty else takes time. I thought that the JIT accelerator would catch things like that.

[Jan]

The JIT is magic and changes its (her?!) behaviour with the contents of the loops and the Matlab version. In Matlab 2011b the empty ELSE branch takes a small amount of time.

Without doubt an empty ELSE branch is not "neat".

[Scragmore]

Jan,

Thanks for your time, much appreciated. I found an improvement, your comment that my ans was wrong got me checking, as my ans was accepted. My mistake was that I loaded accum = [1, 2];. This meant that the first even number in the Fib sequence was not included in the sum. Thus I compensated with out = 2; were I should have made accum = [1, 1].

I don't full understand your last comments about MOD(fibMax, 2) failing after 75 terms. Or your last statement about lookup tables and brute force. Could you expand on you ans a little.

A school boy Question? Does the length and complexity of variable names make any difference to a program compiling or a function running.

Thanks,

AD

[Jan]

After 76 terms (when starting with [1,2] 75), the resulting term is larger than 2^53, such that it cannot be represented exactly as a DOUBLE anymore:

a = [1,1];

for i = 1:77, a=[a(2),a(1)+a(2)]; fprintf('%.16g %d\n', a(2), a(2)==a(2)+1); end

Or explicitely:

5527939700884757+8944394323791464 == 5527939700884757+8944394323791464 + 1

Therefore further elements of the Fibonacci sequence cannot be calculated exactly anymore using DOUBLEs. And if the number is not exactly an integer anymore, the MOD(x,2) is not meaningful also.

A school boy solution for the question about the complexity of symbols: Try it. Simply measure the time using TIC/TOC. But the question is too important to be hidden in the comments of another question. Please post it as a new question. Currently I cannot access the list of question (server problems...), but if you send me the link to your question, I will post some corresponding information.

[Scragmore]

Thanks for the answers and explanation. I don't blame matlab, my maths is not good enough to accurately go beyond the size of those numbers either.

AD

Answer 2

[bym]

Have a look at Binet's formula and look for a pattern in the distribution of even Fibonnaci numbers...I bet a one liner could be written

Answer 3

[Daniel Shub]

x = [1 2];
eusol2 = 0;
while sum(x) < euin
  if mod(sum(x), 2) == 0;
    eusol2 = eusol2 + sum(x);
  end
  x = [x(2), sum(x)];
  % k = sum(x);
end

This will likely be a little slower since it calculates the sum(x) 4 times per loop. If you add another declared variable (k) you can make it so sum(x) is calculated only once. I eliminated y, because it doesn't seem to do anything.

[Scragmore]

Thanks,

I didn't know you could sum a complete matrix like that. I presume as its matlap and matrices are native you can sum in a hole bunch of ingenious ways.

My y is a switch, it flips between 1 & 2, in this case cell positions of x(y), allowing me to alternate storing the latest number in the series.

From reading your code I can use my function output, in this case eusol2 as a declared variable. I was worried that every time I wrote to this variable it would return it from the function. I will test/try this.

Thanks,

AD

Answer 4

[bym]

just to let you know where I was headed:

clc;clear;tic

phi = (1+sqrt(5))/2;
i = 1:11;               % 11 even terms < 4e6
fib = (phi.^(i.*3)-(-1/phi).^(i.*3))/sqrt(5);
fprintf('%6.0f\n',sum(fib))
toc

as Jan suspected, it runs slower than yours (about .8 msec vs .07 msec). +1 vote for the question