Please explain 'log' to me

This is a discussion on Please explain 'log' to me within the Tech Board forums, part of the Community Boards category; i'm trying to REALLY get into programming - beyond just knowing the syntax. i'm reading up on algorithms and data ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    719

    Please explain 'log' to me

    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)
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  2. #2
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,825
    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.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    A page on logarithms, also from wikipedia:

    http://en.wikipedia.org/wiki/Logarithm
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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) )
    Attached Images Attached Images  
    Last edited by Sang-drax; 04-08-2005 at 12:20 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Hamster without a wheel iain's Avatar
    Join Date
    Aug 2001
    Posts
    1,385
    In connection with Big-O notation, read arounf the subjects of P and NP complete problems to give you a little more understanding
    Monday - what a way to spend a seventh of your life

  6. #6
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by iain... kind of
    In connection with Big-O notation, read around the subjects of P and NP complete problems to confuse the hell out of you
    fixed.

  7. #7
    People Love Me
    Join Date
    Jan 2003
    Posts
    412
    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.

  8. #8
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    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)
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  9. #9
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    E represents Sigma
    Code:
    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?
    Code:
    (6)
    |E|   * x =  2 + 3 + 4 + 5 + 6 = 20
    | |_ 
    (x=2)
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  10. #10
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by 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.
    Quote Originally Posted by Krak's tutorial
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by misplaced
    E represents Sigma
    Code:
    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:
    Code:
    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:
    Code:
    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"

  12. #12
    People Love Me
    Join Date
    Jan 2003
    Posts
    412
    Quote Originally Posted by misplaced
    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:

    Code:
    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.
    Last edited by Krak; 04-09-2005 at 02:00 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching problem
    By DaMenge in forum C Programming
    Replies: 9
    Last Post: 09-12-2005, 02:04 AM
  2. fprintf works in one function but not in the other.
    By smegly in forum C Programming
    Replies: 11
    Last Post: 05-25-2004, 04:30 PM
  3. log and restore
    By TopJo in forum C Programming
    Replies: 3
    Last Post: 07-01-2003, 08:14 PM
  4. 10 log?
    By Shadow in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 05-19-2003, 05:26 AM
  5. My log file player; Hit the brick wall
    By Twig in forum C Programming
    Replies: 6
    Last Post: 07-27-2002, 06:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21