What is the issue with the Fibonacci sequence code in C#?

[AliGh]

I have been writing c# for fun a few weeks but i always run into problem with for circles
I wrote a simple code to show me first n numbers of fibonacci sequence but i don't know where the problem is
I had similar issues with it before ...

Even if the code is wrong then at least it should give me ten wrong numbers if n given 10

 

[mfb]

Why do you have two loops? That does not make sense.
I don't know input handling of C#, but do you need that ToInt32() and does it do what you expect? What happens if you plug in 10 into the code directly?

 

[AliGh]

Well i think i can make it one loop . I didnt realize that
What i put in the console.read() will be a string so i have to convert it to an integer
I plugged 10 into the code directly . It gave me the first 10 number in the screenshot i uploaded

I think there is a possibility that my editor has a problem ...

 

[AliGh]

Made it one loop and it worked but i still don't know what was the problem ...

int n = Convert.ToInt32(Console.ReadLine());
int x; int x1 = 0 ; int x2 = 1; int Switch;

for ( x = 1;n>=x ;x++)
{
Switch = x1;
x1 = x2;
x2 = Switch + x2;
Console.Write(" ,{0}", x2);

}
while (1 > 0) {
Console.ReadLine();
}

 

[mfb]

I don't understand what the two loops were supposed to do. If you wanted to start computation from scratch for every number then there was something missing to reset x1 and x2 each time.

 

[Mark44]

What is the purpose of this code?

while (1 > 0) {
   Console.ReadLine();
}

Since 1 > 0 is always true, you have an infinite loop. Inside the loop, you read a line of text, but don't store it anywhere. In other words, your code will run forever, which is probably not what you want to happen.

 

[rcgldr]

What is the purpose of this code?

The read line keeps the console window open, but there's no need for an infinite loop. With the current code, the program has to be aborted to exit it.

 

[at94official]

}
while (1 > 0) {
Console.ReadLine();
}

This is one of the problem makes the program insignificant to what you want to happen.

 

[D H]

Made it one loop and it worked but i still don't know what was the problem ...

One very important debugging tool is for you yourself to be the computer. Walk through your code, line by line.

n  x1 x2 Switch x y    statement                                 output
10                     Convert.ToInt32(Console.Read())
    0  1    -          int x; int x1=0; int x2=1; int Switch;
1836311903                1      for ( x=1;n>=x ;x++)
                  1    for (int y=1;x>=y ; y++ )
            0          Switch = x1; 
    1                  x1 = x2; 
       1               x2 = Switch + x2; 
                       Console.Write(" ,{0}", x2);               , 1 
                  2    for (int y=1;x>=y ; y++ )
                2      for ( x=1;n>=x ;x++)
                  1    for (int y=1;x>=y ; y++ )
            1          Switch = x1; 
    1                  x1 = x2; 
       2               x2 = Switch + x2; 
                  2    for (int y=1;x>=y ; y++ )
            1          Switch = x1; 
    2                  x1 = x2; 
       3               x2 = Switch + x2; 
                  3    for (int y=1;x>=y ; y++ )
                       Console.Write(" ,{0}", x2);               , 3 
                3      for ( x=1;n>=x ;x++)
                  1    for (int y=1;x>=y ; y++ )
            2          Switch = x1; 
    3                  x1 = x2; 
       5               x2 = Switch + x2; 
                  2    for (int y=1;x>=y ; y++ )
            3          Switch = x1; 
    5                  x1 = x2; 
       8               x2 = Switch + x2; 
                  3    for (int y=1;x>=y ; y++ )
            5          Switch = x1; 
    8                  x1 = x2; 
      13               x2 = Switch + x2; 
                  4    for (int y=1;x>=y ; y++ )
                       Console.Write(" ,{0}", x2);               , 13

That extraneous inner loop makes you skip ever more elements of the Fibonacci sequence. Instead of printing F₂, F₃, F₄, F₅, F₆, ... you are printing F₂, F₄, F₇, F₁₁, F₁₆, ...

If that was what you were asked to do, that would work just fine up to x=9, which prints F₄₆, or 1836311903. If you had walked through your program with a debugger (another excellent tool for figuring out what your program is doing), you would have seen that your computer calculates 1134903170+1836311903 as -1323752223. You just overflowed!

 

[rcgldr]

The calculation can be sped up using an unfolded loop, and alternating between two variables to hold the Fibonacci values:

unsigned int fib(unsigned int n)
{
unsigned int f0, f1;
    f0 = n & 1;         /* if n even, f0=0=fib(0), f1=1=fib(-1) */
    f1 = 1 - f0;        /* else       f0=1=fib(1), f1=0=fib(0)  */
    while(n >= 8){      /* this unfolded loop is optional */
        f1 += f0;
        f0 += f1;
        f1 += f0;
        f0 += f1;
        f1 += f0;
        f0 += f1;
        f1 += f0;
        f0 += f1;
        n -= 8;
    }
    while(n >= 2){      /* this unfolded loop used to avoid shifting data */
        f1 += f0;
        f0 += f1;
        n -= 2;
    }
    return f0;
}

In 64 bit mode, there are enough registers that a matrix method is faster (if calculating a single value as opposed to generating an array of values). The Fibonacci function is a linear recurrence equation f(n) = f(n-1) + f(n-2), which can be converted into a matrix operation:

/* pseudo code: */
m[2][2] = {{1, 1}, {1, 0}};   /* Fibonacci matrix */
f[2][1] = {{0},{1}};          /* fib(0) = {{fib(0)}, {fib(-1)}} */ 
fib(n)  = m x fib(n-1);       /* fib(n) done with matrix multiply */
fib(n)  = pow(m,n) x fib(0);  /* raise matrix m to power n using repeated squaring */

typedef unsigned long long UI64;

UI64 fibm(UI64 n)
{
/*   s0 s1      squared matrix  */
/*   s2 s3                      */
UI64 s0 = 1;
UI64 s1 = 1;
UI64 s2 = 1;
UI64 s3 = 0;
/*   m0 m1      pow(m,n) matrix */
/*   m2 m3                      */
UI64 m0 = 1;
UI64 m1 = 0;
UI64 m2 = 0;
UI64 m3 = 1;
/*  x0 x1       tmp matrix  */
/*  x2 x3                   */
UI64 x0, x1, x2, x3;
    while(1){
        if(n & 1){
            /* multiply m by s */
            x0 = m0*s0 + m1*s2;
            x1 = m0*s1 + m1*s3;
            x2 = m2*s0 + m3*s2;
            x3 = m2*s1 + m3*s3;
            m0 = x0;
            m1 = x1;
            m2 = x2;
            m3 = x3;
        }
        n >>= 1;
        if (n == 0)
            break;
        /* square s */
        x0 = s0*s0 + s1*s2;
        x1 = s0*s1 + s1*s3;
        x2 = s2*s0 + s3*s2;
        x3 = s2*s1 + s3*s3;
        s0 = x0;
        s1 = x1;
        s2 = x2;
        s3 = x3;
    }
    return m1;
}

Not that this makes much difference, fib(47) is the largest number that fits in a 32 bit unsigned integer: 2971215073. fib(93) is the largest number that fits in a 64 bit unsigned integer: 12200160415121876738. Some programming challenges find fib(n) modulo some prime number like 1000000007 for large n, in which case these type of optimizations make more sense.

 

[D H]

You can speed up the calculation using an unfolded loop, and alternating between two variables to hold the Fibonacci values.

unsigned int fib(unsigned int n)
{
unsigned int f0, f1;
    f0 = n & 1;         /* if n even, f0=0=fib(0), f1=1=fib(-1) */
    f1 = 1 - f0;        /* else       f1=0=fib(0), f0=1=fib(-1) */
    switch(n%8){
        do{
            f1 += f0;
          case 7:
            f0 += f1;
          case 6:
            f1 += f0;
          case 5:
            f0 += f1;
          case 4:
            f1 += f0;
          case 3:
            f0 += f1;
          case 2:
            f1 += f0;
          case 1:
            f0 += f1;
          case 0:
            continue;
        }while(0 <= (int)(n -= 8));
    }
    return f0;
}

Seriously? Duff's device for a mere 46 calculations? Talk about micro-optimizations!

Besides, this thread is about C#, and that code is illegal in C#. There is no way to implement Duff's device in C#. You are using fall through to go from one case to the next. That is illegal in C#. In C#, you have to use goto to explicitly say you truly do want to fall through to the next case:

switch (value) {
case 0:
    do_case_0_stuff;
    goto case 1;
case 1:
    ...
}

In C#, the first thing after a switch must be a case label. That do statement immediately after the switch is illegal. If you move the do statement after the case 0 case label, that's also illegal. Now those remaining case labels are illegal. They now belong to the do loop rather than the switch statement, and case labels can only be used in a switch statement. You also can't decouple the switch statement and the do loop and use the switch to goto a labeled statement inside the do loop. You can't use goto to jump into the middle of a loop in C#.

Bottom line, you can't implement Duff's device in C#.

And that's a good thing. Duff's device is for the most part an outdated concept from 1980s computing. There have been a number of cases where people went through archaic code and eliminated all occurrences of Duff's device and the code ran faster.

 

[D H]

I updated my previous post, will delete this one later.

Even with your change, you are still doing loop unrolling. That is a micro optimization. Downsides: your code is harder to understand, harder to maintain, and may do exactly the opposite of what you intended. Loop unrolling can make your program run slower.

Many modern CPUs are Harvard architecture machines underneath the hood, with separate level 1 caches for data and instructions. Loop unrolling inevitably makes your code base fatter, resulting in more misses on the level 1 instruction cache. That brings the CPU to a grinding halt.

My advice: Aspire to write code that is as clean, simple, and unsurprising as possible. The future maintainers of your code will thank you, as will the compiler. The compiler knows what to do with clean, simple, unsurprising code, and oftentimes, its optimizations are better than what you think is optimal. Complex code befuddles maintainers and it befuddles compilers.

Then you test. There's no need to optimize your code if the program performs well. If it doesn't, find the bottlenecks. Those bottlenecks oftentimes can be attributed to very isolated and very small amounts of code. Optimize those, but leave the rest of your code clean, simple, and unsurprising.

 

[rcgldr]

still doing loop unrolling.

The key concept I was trying to demonstrate is often used to optimize linear feedback shift algorithms. Instead of shifting values through a set of variables, the logical meaning of the variables changes during a repeated sequence of code, until the logical meaning cycles back to the original state. In this case, it's a set of two variables, so it's just two statements: f1 += f0; f0 += f1; .

Take the case of a 4 variable sequence with a right shift. All 4 variables are probably in registers.

tt = f(s0, s1, s2, s3)
s3 = s2;
s2 = s1;
s1 = s0;
s0 = tt;
/* is unfolded into */
s3 = f(s0,s1,s2,s3);
s2 = f(s3,s0,s1,s2);
s1 = f(s2,s3,s0,s1);
s0 = f(s1,s2,s3,s0);

 

[AliGh]

I read last 4 replies got confused ...

 

[rcgldr]

I read last 4 replies got confused ...

Those are optimized examples, but as mentioned in post #10, since the maximum loop count is small, the optimizations aren't needed. I was hoping you or others reading this thread would be able to follow those examples, as sort of a learning exercise. The matrix method won't help if you don't know how to do matrix operations in math.

Your code in post #4 is OK, except for the while(1 > 0) part at the end.

If you're wondering how to determine Fibonacci for negative n, just rerrange the terms in the equation:

f(n) = f(n-1) + f(n-2)

f(n-2) = f(n) - f(n-1)

So given f(1) = 1, and f(0) = 0, then you can calculate Fibonacci function for negative n:

f(-1) = 1
f(-2) = -1
f(-3) = 2
f(-4) = -3
f(-5) = 5
f(-6) = -8
...

 

[at94official]

I have been writing c# for fun a few weeks but i always run into problem with for circles
I wrote a simple code to show me first n numbers of fibonacci sequence but i don't know where the problem is
I had similar issues with it before ...

Even if the code is wrong then at least it should give me ten wrong numbers if n given 10

unsigned int fib(unsigned int n)
{
unsigned int f0, f1;
f0 = n & 1; /* if n even, f0=0=fib(0), f1=1=fib(-1) */
f1 = 1 - f0; /* else f0=1=fib(1), f1=0=fib(0) */
while(n >= 8){ /* this unfolded loop is optional */
f1 += f0;
f0 += f1;
f1 += f0;
f0 += f1;
f1 += f0;
f0 += f1;
f1 += f0;
f0 += f1;
n -= 8;
}
while(n >= 2){ /* this unfolded loop used to avoid shifting data */
f1 += f0;
f0 += f1;
n -= 2;
}
return f0;
}

 

[rootone]

Without trying to delve too deeply into your method, one thing which is apparent is that your function takes a single integer as input and returns a single integer as output.
Whatever your input value is, it's still going to produce a single integer as it's output.

 

[AliGh]

unsigned int fib(unsigned int n)
{
unsigned int f0, f1;
f0 = n & 1; /* if n even, f0=0=fib(0), f1=1=fib(-1) */
f1 = 1 - f0; /* else f0=1=fib(1), f1=0=fib(0) */
while(n >= 8){ /* this unfolded loop is optional */
f1 += f0;
f0 += f1;
f1 += f0;
f0 += f1;
f1 += f0;
f0 += f1;
f1 += f0;
f0 += f1;
n -= 8;
}
while(n >= 2){ /* this unfolded loop used to avoid shifting data */
f1 += f0;
f0 += f1;
n -= 2;
}
return f0;
}

Solved this problem long time ago
I got confused with your code what are you trying to achieve ? if you want it to return Nth number , i don't think this is the way to do it