Results 1 to 8 of 8

Math Help - Computing efficiently

  1. #1
    Member courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    Posts
    206

    Question Computing efficiently

    What is gained when x^y is computed as 2^{y\log_2 x} (for x>0) rather than the "direct" (but not naive) way?

    You get a smaller base (not sure if that helps, but I'll leave it to be corrected ) ... on the other hand, \log introduces (additional) error.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by courteous View Post
    What is gained when x^y is computed as 2^{y\log_2 x} (for x>0) rather than the "direct" (but not naive) way?

    You get a smaller base (not sure if that helps, but I'll leave it to be corrected ) ... on the other hand, \log introduces (additional) error.
    I don't think I'll have the answer in any case, but you should probably specify whether x,y are integers/floats/other.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    Posts
    206
    This is from a chapter on IEEE-754 standard, so call x and y "floats". Though, at the level of 23 (or 52 for double precision) bits, they're all really just integers, aren't they?

    The textbook uses the above (questioned) fact just for showing, that even 52 bits (double precision) aren't good enough for IEEE and we need 64 bits (Extended precision). But it doesn't show why x^y is better computed as 2^{y\log_2 x}.
    Last edited by courteous; September 3rd 2010 at 09:12 AM. Reason: [math]
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by courteous View Post
    This is from a chapter on IEEE-754 standard, so call x and y "floats". Though, at the level of 23 (or 52 for double precision) bits, they're all really just integers, aren't they?

    The textbook uses the above (questioned) fact just for showing, that even 52 bits (double precision) aren't good enough for IEEE and we need 64 bits (Extended precision). But it doesn't show why x^y is better computed as 2^{y\log_2 x}.
    Perhaps this will be of some use?

    Info: (gmp) Normal Powering Algorithm

    There might be further notes in the source code of GMP.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    Posts
    206
    Couldn't help myself with GMP documentation.

    Should've looked at Wikipedia first, though this paragraph is still unclear (to me):
    Moreover, cd = b^{(\log_b c)d} reduces the exponentiation to looking up the logarithm of c, multiplying it with d (possibly using the previous method*) and looking up the antilogarithm of the product.
    Looking up, as in "looking up in the tables"? Is this then what makes it efficient, the fact that computer has those tables already stored?
    Without this stored table, this method isn't any more efficient, because antilogarithm is exponentiation, right (or is there some subtle difference (like between antiderivative and integral, I think ... ))?

    * cd = b^{\log_b c}*b^{\log_b d} = b^{\log_b c + \log_b d}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by courteous View Post
    Couldn't help myself with GMP documentation.

    Should've looked at Wikipedia first, though this paragraph is still unclear (to me):


    Looking up, as in "looking up in the tables"? Is this then what makes it efficient, the fact that computer has those tables already stored?
    Without this stored table, this method isn't any more efficient, because antilogarithm is exponentiation, right (or is there some subtle difference (like between antiderivative and integral, I think ... ))?

    * cd = b^{\log_b c}*b^{\log_b d} = b^{\log_b c + \log_b d}
    Isn't exponentiation with base 2 just a bitshift?

    2^0 -> 1
    2^1 -> 10
    2^2 -> 100

    Or am I missing something? I haven't really worked with floating point in this way.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by courteous View Post
    What is gained when x^y is computed as 2^{y\log_2 x} (for x>0) rather than the "direct" (but not naive) way?

    You get a smaller base (not sure if that helps, but I'll leave it to be corrected ) ... on the other hand, \log introduces (additional) error.
    It is (or rather can be) more efficient because you are using base 2 and a binary float representation, so logs are only ever required for numbers in the range 1 to 2, and the main part of a log can be read straight out of the exponent (-ish if we ignore the normalisation/non-normalisation complication) and the same sort of tricks can be played in the reverse direction.

    CB
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member courteous's Avatar
    Joined
    Aug 2008
    From
    big slice of heaven
    Posts
    206
    Quote Originally Posted by CaptainBlack View Post
    ..., so logs are only ever required for numbers in the range 1 to 2, ...
    Could you give some (simple) example?
    For instance, 5^7=78125=2^{7\log 5}.
    In memory that would look like 0000.0101^{0000.0111}=101^{111}=10^{111\log 101}= ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing A^k
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 19th 2011, 02:51 PM
  2. Evaluate efficiently
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 18th 2011, 01:02 AM
  3. divide an area efficiently
    Posted in the Geometry Forum
    Replies: 2
    Last Post: September 6th 2009, 07:20 AM
  4. Replies: 5
    Last Post: May 27th 2009, 04:36 PM
  5. Computing ROI ?
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 13th 2009, 03:46 PM

/mathhelpforum @mathhelpforum