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

[Mark44]

As for the scanf, I don't actually use scanf at all but you may try to do something like

  while (getchar()!=EOF) { }

just before you ask for array length. It's supposed to read and throw away any characters left in stdin.

Or you could use fflush() to flush the input buffer.

fflush(stdin);

This is especially useful if you read in a number and then later read in a string of characters or even one character. Flushing the input buffer after reading a number prevents a following read from taking in the newline character.

Do you happen to know how to solve my next bug: When i scan for the numbers in the array if i input let's say 9 numbers and I've said I am going to have 8 numbers that last one is transferred as the array length input for the second loop. Could i somehow tell the scanf function to scan only n numbers and ignore the rest?

I'm not sure I understand your question. Are you are using scanf() to input more than one number at a time? It's easiest on the user of your program (which is not necessarily you) to input a single number per call to scanf().

You could issue a prompt that asks how many numbers are to be entered. Then use that number to control a for loop. Something like this:

printf("How many numbers do you want to enter?")
scanf("%d", &count);
for (i = 0; I < count; ++i)
{
   printf("> ");
   scanf("%d", &arr[ i]);
}

 

[doktorwho]

Or you could use fflush() to flush the input buffer.

fflush(stdin);

This is especially useful if you read in a number and then later read in a string of characters or even one character. Flushing the input buffer after reading a number prevents a following read from taking in the newline character.
I'm not sure I understand your question. Are you are using scanf() to input more than one number at a time? It's easiest on the user of your program (which is not necessarily you) to input a single number per call to scanf().

You could issue a prompt that asks how many numbers are to be entered. Then use that number to control a for loop. Something like this:

printf("How many numbers do you want to enter?")
scanf("%d", &count);
for (i = 0; I < count; ++i)
{
   printf("> ");
   scanf("%d", &arr[ i]);
}

I find it faster if the user inputs all the numbers in one row, as an easier way for the user to use the program but that has a bad side that i will pick up in my scanf more numbers if inputted. One at the time works like a charm and i really like the way you used > and I've implemented in in my code :)

 

[Mark44]

I find it faster if the user inputs all the numbers in one row, as an easier way for the user to use the program but that has a bad side that i will pick up in my scanf more numbers if inputted. One at the time works like a charm and i really like the way you used > and I've implemented in in my code :)

If you want it to be really fast, just initialize your matrix with the numbers you want and don't bother with scanf().

As far as inputting multiple numbers at the same time, you might find it faster, but if you write "real" software that others use, it can be very confusing to those people. And as you found out, things can go wrong even for the person who wrote the program. There are some real intricacies in the control string for scanf() with multiple inputs.

 

[newjerseyrunner]

I just want to let you know that if you just hit "run" on that code in a mingw ide and VS, they will act differently.

Mingw ides never launch the executable directly, they launch a launcher, which stays open until you close it. It allows you to see the results of any stdout before closing. VS doesn't do that, so you should place a pause (just wait for a cin) if you want to see the output in the ide.

 

[ChrisVer]

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

 

[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.