Please explain 'log' to me

[misplaced]

i'm trying to REALLY get into programming - beyond just knowing the syntax. i'm reading up on algorithms and data stuctures, but i keep running into some mathematical things i'm unfamiliar with. i haven't completed any algebra courses beyond intro to college algebra (somehow though, i managed to test out of intermediate algerbra and go straight to college algebra, anyways....). i see 'log' in just about everything i read.

i've been searching the internet, but since 'log' appears so often, it's hard to find out what it really is.

another thing i keep seeing is O and the text didn't really explain what O represented (unless i skimmed past it)

so, could someone please break this down for me (if at all possible without it's context)
O(n log m)

[Govtcheez]

This'll help get you started.

http://en.wikipedia.org/wiki/Big_O_notation

Sorry I can't help more, I've always sucked at this.

[hk_mp5kpdw]

A page on logarithms, also from wikipedia:

http://en.wikipedia.org/wiki/Logarithm

[Sang-drax]

Those pages seem good.

The use of big-O notation in computer science differs a little from the mathematical definition.
For example, most people would claim that the time complexity of the quicksort algorithm isn't O(n^3). But, any algorithm that is O(n ln n) is also O(n^3).


EDIT:
Look at the definition of "asymptotically tight bound". That is the meaning when computer scientists write f(x) is O( g(x) )

[iain]

In connection with Big-O notation, read arounf the subjects of P and NP complete problems to give you a little more understanding

[Perspective]

In connection with Big-O notation, read around the subjects of P and NP complete problems to confuse the hell out of you

fixed.

[Krak]

I wrote a section on logarithms in my tutorial.

Not only will it teach you what a logarithm is, but how you can apply them to programming video games.

[misplaced]

Thanks alot guys - i've never comes across wikipedia.com before - i never really thought to look in an encyclopedia either. This look like a great place to start.

Oh and krak, you might want to do some error checking on Logrithms.doc - it crashed my comp ..... nah, my computer's just a piece of crap.

(...i know a .doc file isn't executable - i just thought it was kind of funny)

[misplaced]

E represents Sigma

6
E x = 2 + 3 + 4 + 5 + 6
x=2

does that mean that x = 20?
or x = 1?

in other words, is there inplied multiplication between Sigma and x?

(6)
|E|   * x =  2 + 3 + 4 + 5 + 6 = 20
| |_ 
(x=2)

[Sang-drax]

I wrote a section on logarithms in my tutorial.

Not only will it teach you what a logarithm is, but how you can apply them to programming video games.

If you’re wondering, e stands for “Euler’s (Oil-er’s) number, and is approximately 2.71828183. For purposes of game programming, it really won’t benefit you much to know about it. If you’re wondering, it has to do with half-lives and also compound interest and such;

The number e has nothing to do with half-lives and compound interest. The reason e is used is because
D e^x = e^x
For other bases, the derivaive will contain a constant. When you use e, this constant is 1.

[Thantos]

E represents Sigma

6
E x = 2 + 3 + 4 + 5 + 6
x=2

does that mean that x = 20?
or x = 1?

Theres two parts you have to look at. The sumation:

6
E x
x=2

Which means "sum up the values of x where x ranges from 2 to 6 as an integer"
Then you'd write out the values:
2 + 3 + 4 + 5 + 6
which means the sum is 20.

Another example would be:

6
E x+5
x=2

Which would mean "sum up the values of x+5 where x ranges from 2 to 6 as an integer"

[Krak]

nah, my computer's just a piece of crap.

Then here it is:

A logarithm is a pretty important mathematical concept. Even if you do know what a logarithm is, you might not know how they’re useful. So what is a logarithm? In simplest explanation, it’s a way to find an exponent. For example:

10^x = 800

We have an equation here that asks, “10 to what power is 800?” Let’s re-write this equation using a logarithm: Here’s the standard way to write logarithmic equation:

Log Base Total = Exponent
Log 10 800 = x //This is the same as 10^x = 800, just re-written

Your solution for x is (approx) 2.90308998

If you type up 10^2.90308998 on your calculator, you’ll get about 799.9, which shows you that this works for finding an exponent. But you MUST note the following: Generally, no calculator will allow you to use any arbitrary base. For the most part, calculators and computer programs ONLY provide functions to deal with TWO bases: 10, and e. A logarithm (Hereafter often referred to as a ‘log’) for a base of 10 is called a common log, and one to the base of e is called a natural logarithm.

If you’re wondering, e stands for “Euler’s (Oil-er’s) number, and is approximately 2.71828183. For purposes of game programming, it really won’t benefit you much to know about it.

Generally, when you use a log function on a calculator, the syntax will not include the base; it will just be log (number). That might confuse you, but that just means that the base is understood to be 10. A log to the base of e (natural log) is commonly denoted with ln (number). In Flash, the function for logs is Math.log().

You might be wondering: “If you can only use TWO bases, how in the world can logarithms be useful? How do I use a number like 5 as my base?” You can do so by “swapping bases,” and this is where the usefulness of logarithms can definitely be seen. Memorize this general formula:

Log (Total) / Log (N) == Log N (Total)

Example:
Log (100) / Log (4) == Log 4 100

There you have it! You just “swapped the bases.” You went from using the base 10, to using 4. Log(100)/Log(4) will give you the solution to Log 4 100; which is approximately 3.32192809. If you punch up 4^ 3.32192809, you’ll get a number approaching 100. The only reason you DON’T get 100 exactly is because I truncate (cut off) part of the exponent solution so it doesn’t take up an entire line.

But you still don’t know HOW you can use this to your advantage, do you? It’s time to find out. Consider an RPG engine and our protagonist, Billy: Billy gets up levels based on how many experience points he has. But the amount of experience points he needs to get to the next level increases, EXPONENTIALLY. What can logarithms do? Find an exponent for you. So let’s find the exponent that determines what level you’re in. Consider this ActionScript:

MaxLevel = 99;
MaxExp = 99999;
/*Log 99 99,999 = 2.50546576376741, so your level to that
power will give you the experience points you need to reach the next level.
Obviously, the experience points needed to reach the 
next level will increase each level.*/  
Level_exponent = Math.log(MaxExp)/Math.log(MaxLevel);

for ( i=1;   i<(MaxLevel+1);   i++ ) {
	trace("For level "+i+" you need this much exp:");

/*Displays the exp points needed to reach that level, in integer
form (Math.floor() truncates everything after the decimal point by
rounding a decimal down.):*/
	trace(  Math.floor (  Math.pow(i, Level_exponent) )  );

/*Outputs a new line*/
	trace("\n");}

You can also do the opposite by swapping the order in which you divide the terms in your Level_exponent assignment. If you use

Math.log(MaxLevel)/Math.log(MaxExp);
This also equals Log MaxExp MaxLevel, or more easily understood:
Log Exp Level = 0.399127385598886
So Exp ^.399 ~= Level

Raise your experience points to that power, truncate the decimal point, and you’ll ALWAYS get your current level. Try it out! Now you see how you can use logarithms just as they were intended to be used: to find an exponent. Since growth in an RPG is almost always exponential (because as you become stronger and stronger, an upgrade of say…5 hit points when you have 500 wouldn’t be NEAR as effective as it was when you had 10 hit points), you can use logarithms to find exponents by which status attributes, etc. can be raised to.

Raising a number to a power in Flash uses Math.pow(), which accepts two parameters: base, and exponent. Math.pow(5,4) raises 5 to the 4th power. You can use a logarithm for each and every status attribute, to determine the exponent by which that particular attribute grows. This can allow you to customize your character(s)’ growth to allow some characters to grow with certain status attributes than others do.