Review C Code: Find & Resolve Issues in Visual Studio & repl.it

[Buffu]

int MAX_NUM_EL = 500;
int numbers[MAX_NUM_EL];

If you are using C++ then what is the need of this line.
C++ have vectors. the header file is #include<vector>.

 

[ChrisVer]

If you are using C++ then what is the need of this line.

as far as I understood, he said he uses C.

 

[doktorwho]

also you could try using the fibonacci number generator in a separate function- that way nobody would be confused with that j loop...
eg have a function: bool isFibonacci(int n), which can tell you if the integer number n is a Fibonacci number...?
That way you in a later time or other people looking through your code, wouldn't have to read the whole program and keep track of nested for loops in your code... afterall that for loop which tests your fibonnaci numbers can be separated from your main program. This will remove several lines from your main code, and you won't have to keep track of them when you return to reading your code a month later (as long as you tested them and know they work properly).
Also I am wondering how optimal generating all the fibonacci numbers is:
so for example it would be much better to have an array with fibonacci numbers up to the one corresponding to your max(numbers). So for example if you tested your fibonacci-ness of an entry 50, and saw that 1,2,3,5,8 etc were not equal to 50, why would you retry them for an entry 51 (>50) ? with arrays you can come up with several ways that can solve you this problem... eg:
1. have the fibonacci array of length M (taken from the maximum of your array with length N)...
2. sort the fibonacci array (time~M), and your array (time~N). Time's given if you use a counting sort algorithm.
3. start looking in your array elements, if your 0-th element is a fibonacci number and it is in the 5th position of the fibonacci array, you won't ever have to recheck the first 4 elements of the fibonacci array.
Of course there may be more intelligent ways to decrease your calculation time, but that's the 1st one that came to my mind...

You make an interesting point, about the separate function and the fibbonacci array as well. And also for you number 3 prepositions, it's a great idea! I will try to come up with something and ill post to make a comparison as I'm deeply interested in the ways you suggested

 

[SlowThinker]

Well Fibonacci numbers grow quite fast, so the speedup probably won't be all that awesome. And the code will be a LOT longer, with many opportunities for an error.
If you want to make the check faster, I'd try to work with Haruspex's idea from post #23. This might work but I haven't tested it:

bool isFibonacci(int n)
 {
  static const double sqrt5=sqrt(5);
  static const double lnlam=1/ln((1+sqrt(5))/2);
  double error=ln(n*sqrt5)*lnlam;
  error=error-round(error);
  return fabs(error*n)<0.6; //magic constant, needs to be between 0.4 and 0.7
 }

It should only work for big n (I did a quick check with Excel and it seems to work for all numbers though, bigger than 0 of course).

 

[ChrisVer]

yes, that would make it way more faster (as fast as looping through your given array)...
Is there a reason for using the static keyword? Oh it's for doing the assignment only once?

 

[doktorwho]

Well Fibonacci numbers grow quite fast, so the speedup probably won't be all that awesome. And the code will be a LOT longer, with many opportunities for an error.
If you want to make the check faster, I'd try to work with Haruspex's idea from post #23. This might work but I haven't tested it:

bool isFibonacci(int n)
 {
  static const double sqrt5=sqrt(5);
  static const double lnlam=1/ln((1+sqrt(5))/2);
  double error=ln(n*sqrt5)*lnlam;
  error=error-round(error);
  return fabs(error*n)<0.6; //magic constant, needs to be between 0.4 and 0.7
 }

It should only work for big n (I did a quick check with Excel and it seems to work for all numbers though, bigger than 0 of course).

yes, that would make it way more faster (as fast as looping through your given array)...
Is there a reason for using the static keyword? Oh it's for doing the assignment only once?

I believe that as a part of the assignment I'm to show that i know how to generate a sequence. So its down to the suggestion made by ChrisVer and my own solution. Others although correct and faster have to have some sort of fibboncci sequence generation

 

[haruspex]

1. have the fibonacci array of length M (taken from the maximum of your array with length N)...

Having created the array of Fibonacci numbers up to and including the largest number read in, you can look each given number up very quickly using a binary chop.

 

[ChrisVer]

Having created the array of Fibonacci numbers up to and including the largest number read in, you can look each given number up very quickly using a binary chop.

hmm is the binary search faster than what I mentioned? I haven't thought about it... but I guess if you chop the fibonacci array as you go to larger numbers, it has to be (since mine was still linear).

 

[haruspex]

is the binary search faster than what I mentioned?

I believe so. And you do not need to sort the input, nor restore the allowed numbers to original order.

In fact, you can do a bit better than binary chop because the Fib sequence grows exponentially. To make the first guess, count the number of bits, B, in the test number and try index B*K where K=ln(2)/ln((1+√5)/2).

 

[rcgldr]

To get rid of warnings related to functions like scanf(), add this line before any includes in your source file:

#define _CRT_SECURE_NO_WARNINGS 1

VS doesn't support variable length arrays. If you want a stack based equivalent, use _alloca():

    int *numbers = _alloca(MAX_NUM_EL * sizeof(int));    /* include <malloc.h> */

For a 32 bit signed integer, the maximum Fibonacci number is fib(46) = 1836311903, so it will take 47 iterations to check for all possible Fibonacci numbers from fib(0) to fib(46). If using 64 bit unsigned integers, the max is fib(93) = 12200160415121876738, so it would take 94 iterations (fib(0) to fib(93)). For this program, the code could create a table for all Fibonacci numbers fib(0) to fib(46) and as suggested, do a binary search of the table.

 

[willem2]

For a 32 bit signed integer, the maximum Fibonacci number is fib(46) = 1836311903, so it will take 47 iterations to check for all possible Fibonacci numbers from fib(0) to fib(46). If using 64 bit unsigned integers, the max is fib(93) = 12200160415121876738, so it would take 94 iterations (fib(0) to fib(93)). For this program, the code could create a table for all Fibonacci numbers fib(0) to fib(46) and as suggested, do a binary search of the table.

The problem with the binary search are mispredicted jumps. The logarithm idea is better, but the a full precision log takes too long. You can do with a very unaccurate logarithm: just count the zero bits at the start of the number. since fibonaccy numbers are approcimately a factor of 1.618 apart, there will never be more than 2 Fibonacci numbers with the first 1 bit in the same place.

//smallest and largest Fibonacci numbers with a certain number of leading zero's
int table_smallest[] = { 1, 2, 5, 8, 21, 34, 89, 144, etc.
int table_largest[] =   { 1, 3, 5,13,21, 55, 89. 233, etc

bool is_fibo(int n)
{
    int bit;
    bit = _bit_scan_forward(n)
    return ((n == table1[bit]) | (n == table2[bit]);
}

If you can't get at a fast bit scan instruction, converting an int to a double and extracting the exponent may work.

 

[Mark44]

To get rid of warnings related to functions like scanf(), add this line before any includes in your source file:

#define _CRT_SECURE_NO_WARNINGS 1

Or you can do this up at the top of your code:

#pragma waring(disable: 4996)

scanf() and several other string functions have been deprecated in VS since about VS2012 or so, due to their connection with buffer overruns. The preferred input routine to use in place of scanf() is scanf_s(), which is specific to Visual Studio.

 

[Dr Transport]

...
VS doesn't support variable length arrays. If you want a stack based equivalent, use _alloca():

That is the beauty of vectors, you don't have to allocate them in the beginning. Read the numbers into one, if they are out of order, so what, do a sort, you can check it for negatives and eliminate them easily. To check if any are Fibonacci numbers, generate a vector of them and check if the Fibonacci number is larger than the max of the array, then you can stop that generation. Do a binary search and your done.