Programming Forums > Application Development > C

bl00dninja · Sep 5th, 2005, 2:37 AM

you're learning programming, not adding fibonacci sequences. use a damn loop.

crap, i could have sworn i posted this code on this site before but i can't find it. sorry man.

stevengs · Sep 5th, 2005, 4:56 PM

Quote:

Originally Posted by EverLearning

...Exponentials grow faster than polynomials, so there you have it.

I am certainly no mathematician, but I think this statement should be revised, considering the definition of a polynomial (at least as I understand the term, I am open to correction). Were you possibly intending to compare exponential and linear growth?

EverLearning · Sep 10th, 2005, 7:35 PM

Quote:

I am certainly no mathematician

Me... a wannabe mathematician

whatever you take that to mean...

OK, it involves several "other" mathematical conceps, so bear with me

:

let's say you have a polynomial x^10 and an exponential 2^x, so you are suspecting that my conjecture does not hold. True (duh... 2^10 < 10^10)... for values on a certain interval only, however in asymptotic analysis interest is in long term growth, i.e. limit of f(t) as t->inf(inity); so after intersection point is found (or perhaps several for some wierd function) the behavior of two functions is determined by a limit of their ratio, as t->inf.

In this case i should show that g(x) = O(f(x)), i.e. f(x) is the upper bound for g(x), in other words f(x) will outgrow g(x) for all values of g(x) as they get past a point of intersection of these functions. Usually in asymptotic analysis the intersection value and constants are included in result, but i'm not bothering with it here.

So...let f(x) = 2^x and g(x) = x^10, now if we want to see that f(x) growth faster than g(x) we take limit of ratio g(x)/f(x), if the limit exists and = 0, then "I am right" and that makes sense, right? if lim = 0 that means that denominator blows up and the whole ratio goes to zerrrro.

So...one other point: sometimes it is much easier to work in logarithmic scale to reduce overhead, so I will do it here with a purpose. Roughly: f(x) = ln(2^x) = xln(2) and g(x) = ln(x^10) = 10ln(x) by properties of ln-s. I say roughly because technically you'd have to change bases to apply these properties, but the result would change by a small constant which does not make a difference.

Now take limit(g(x)/f(x)) = lim(10ln(x)/{xln(2)}) = 10/ln(2)lim (ln(x)/x) and if we let x->inf, we have inf/inf or indeterminate form. That's where L'Hopital's rule comes in: take derivative of denom. and numer. and take limit again, so previous limit = lim ([1/x]/1) = lim (1/x) and now (whew...) let x->inf, you get lim = 0, [oh there was a constant there before limit, but c*0 = 0] which proves that x > ln(x), hence 2^x > x^10.

Actually, now that i think of this, g(x) = o(f(x)), i.e. LOOSE upper bound, stronger than O(n), that is O(n) for all constants past a certain point, not sure if o(n) has initial point, so don't quote me on this theoretical claim.
This was a specific case with certain numbers, but it is pretty extendable to general case. You can also prove it by induction, probably. hmmm.....that's a thought.....

The actual exponential e^x does grow faster than any polynomial, by definition e^x is represented by (Maclaurin) series [k = 0 to inf.] 1 + x/1! + x^2/2! + ... x^k/k!; magic....

If you are interested in details of this or see a mistake, let me know, i'd be glad to work it out, just wasn't sure how far to bother with algebra.

ps: i'm kind of an odd visitor here in these days, busy with my classes on circuit design... should be getting back to my breadboard. Oh, no!! it's smoking!!! :eek:

grimpirate · Sep 11th, 2005, 3:50 AM

Hey melee28, here's a code I wrote to do what you ask for very simply, and in an iterative manner using a for loop.

(Toggle Plain Text)

int main(void)
{
	int i;
	int fib[10];

	fib[0] = 0;
	fib[1] = 1;

	for(i = 2; i < 10; i++)
	{
		fib[i] = fib[i - 1] + fib[i - 2];
	}

	for(i = 0; i < 10; i++)
	{
		printf("%d  ", fib[i]);
	}
}

The i variable is used as a counter, and the fib array is used to store the values of the fibonacci sequence. The first for loop computes the sequence, and the second for loop outputs it.

Hope this helps.

stevengs · Sep 11th, 2005, 5:24 AM

Quote:

Originally Posted by EverLearning

let's say you have a polynomial x^10 and an exponential 2^x, so you are suspecting that my conjecture does not hold.

I stand corrected, and ashamed :o . It all became clear again with the third sentence.

Thanks for the clear and precise explanation. Basically a rundown of the first three weeks of my 2nd year mathematics

(*groan*, it has been so long..)

Simon Gray · Sep 11th, 2005, 5:42 AM

I recently wrote such a program myself in TI-83 BASIC.

Take a look! Might help you

DaWei · Sep 11th, 2005, 6:48 AM

Quote:

Oh, no!! it's smoking!!! :eek:

Exponential positive feedback.

Sep 5th, 2005, 2:37 AM	#31
bl00dninja Programming Guru Join Date: Oct 2004 Location: namespace std Posts: 1,246 Rep Power: 5	you're learning programming, not adding fibonacci sequences. use a damn loop. crap, i could have sworn i posted this code on this site before but i can't find it. sorry man. __________________ i put on my robe and wizard hat... Have you ever heard of Plato, Aristotle, Socrates?...Morons.

Sep 11th, 2005, 3:50 AM	#34
grimpirate King of Portal Join Date: Sep 2005 Posts: 431 Rep Power: 4	Hey melee28, here's a code I wrote to do what you ask for very simply, and in an iterative manner using a for loop. (Toggle Plain Text) int main(void) { int i; int fib[10]; fib[0] = 0; fib[1] = 1; for(i = 2; i < 10; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } for(i = 0; i < 10; i++) { printf("%d ", fib[i]); } } int main(void) { int i; int fib[10]; fib[0] = 0; fib[1] = 1; for(i = 2; i < 10; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } for(i = 0; i < 10; i++) { printf("%d ", fib[i]); } } The i variable is used as a counter, and the fib array is used to store the values of the fibonacci sequence. The first for loop computes the sequence, and the second for loop outputs it. Hope this helps. __________________ Lo, there do I see my father. 'Lo, there do I see My mother, and my sisters, and my brothers. 'Lo, there do I see The line of my people... Back to the beginning. 'Lo, they do call to me. They bid me take my place among them. In the halls of Valhalla... Where the brave... May live... ...forever.. GrimBB \| Mimesis

Sep 11th, 2005, 5:42 AM	#36
Simon Gray Programmer Join Date: Aug 2005 Location: �lsg�rde, Denmark Posts: 62 Rep Power: 4	A Fibonacci program in TI-83 BASIC I recently wrote such a program myself in TI-83 BASIC. Take a look! Might help you __________________ Visit my blog, about all that stuff in between your nostrils >_>

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

complete newbie question