- #36
Buffu
- 849
- 146
doktorwho said: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>.
doktorwho said:int MAX_NUM_EL = 500;
int numbers[MAX_NUM_EL];
as far as I understood, he said he uses C.Buffu said:If you are using C++ then what is the need of this line.
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 suggestedChrisVer said: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...
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
}
SlowThinker said: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:
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).C: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 }
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 generationChrisVer said: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?
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 said:1. have the fibonacci array of length M (taken from the maximum of your array with length N)...
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 said: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.
I believe so. And you do not need to sort the input, nor restore the allowed numbers to original order.ChrisVer said:is the binary search faster than what I mentioned?
#define _CRT_SECURE_NO_WARNINGS 1
int *numbers = _alloca(MAX_NUM_EL * sizeof(int)); /* include <malloc.h> */
rcgldr said: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.
//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]);
}
Or you can do this up at the top of your code:rcgldr said:To get rid of warnings related to functions like scanf(), add this line before any includes in your source file:
Code:#define _CRT_SECURE_NO_WARNINGS 1
#pragma waring(disable: 4996)
rcgldr said:...
VS doesn't support variable length arrays. If you want a stack based equivalent, use _alloca():