🔒 Locked

Fun with logarithms

Started by lnxwndusr Mar 13, 2003 at 1:34 AM 13 replies 1.8k views

Original Post

Mar 13, 2003 at 1:34 AM

Hey, I remember seeing somewhere this really slick way to calculate log2 (thats log with base 2) of any # quickly on a computer using c/c++ ... does such a function exist, and if so, is it better(meaning faster) to use it instead of doing log(x)/log(2) with math.h?

Strife

Mar 13, 2003 at 12:16 PM

Yeah, there are ways of dealing with any kinds of logs directly. The log x/log n trick is just a quick way to do it mentally (or on paper) since we''re used to dealing with decimal systems.

lnxwndusr

Mar 15, 2003 at 2:52 PM

I think I found it...

  
__inline DWORD Log2(DWORD val)
{
 DWORD answer = 0;

 while (val >>= 1)
  answer++;

 return answer;
}

Does this really work? I mean, I'm quite doubtful because it returns a DWORD and not a float.

[edited by - lnxwndusr on March 15, 2003 3:55:23 PM]

Zipster

Mar 15, 2003 at 3:38 PM

It really just gives you a rough estimate, because the bit shift restricts you to unsigned types that don''t have any special encoding format (float wouldn''t work for example), and it only returns an integer value. It will basically return the highest power of two that is less than or equal to the value you pass.

For the most precise value, you''re better off using ln(x)/ln(2). ln(2) is a constant, so store that somewhere and you won''t have to calculate it

Enselic

Mar 15, 2003 at 4:49 PM

It''d be faster to store 1/ln(2) and multiply ln(x) with that.

I am a signature virus. Please add me to your signature so that I may multiply.

Zipster

Mar 15, 2003 at 6:05 PM

Gotta scrape those nanoseconds wherever ya can

Jesper T

Mar 16, 2003 at 6:39 AM

If you wrote ln(x)/ln(2) wouldn''t any decent compiler recognize 1/ln(2) as a constant and do the neccasary optimization?

YoshiN

Mar 16, 2003 at 12:52 PM

quote:
Original post by Jesper T
If you wrote ln(x)/ln(2) wouldn''t any decent compiler recognize 1/ln(2) as a constant and do the neccasary optimization?

I wonder about that...I wouldn''t think so, because if you only used it once, then storing as a constant would actually be slower. Of course, the compiler may calculate the number of times it is used and then optimize...

63616C68h

Mar 16, 2003 at 2:55 PM

Well, you say to yourself: some compilers do it and some others don''t, so I''ll do it myself and make it more poratable!

lnxwndusr

Mar 16, 2003 at 4:04 PM

quote:
Original post by Zipster
It really just gives you a rough estimate, because the bit shift restricts you to unsigned types that don''t have any special encoding format (float wouldn''t work for example), and it only returns an integer value. It will basically return the highest power of two that is less than or equal to the value you pass.

For the most precise value, you''re better off using ln(x)/ln(2). ln(2) is a constant, so store that somewhere and you won''t have to calculate it

Any particular reason to use ln instead of log? There''s no mathematical difference between ln x/ln 2 and log x/log 2, but is there anything I don''t know about using c++?

Zipster

Mar 16, 2003 at 4:11 PM

I just figured the computer would have an easier time calculating the natural log because it can be expressed as a MacLaurin series, and the computer need only solve a few terms to get a good approximation. I suppose log₁₀ could also be expressed in such a way due to the simple constant multiple ( 1/ln(10) ), however why do extra multiplications, eh?

[edited by - Zipster on March 16, 2003 5:14:11 PM]

Fruny

Mar 16, 2003 at 4:17 PM

I don''t know how the ln() and log() functions are actually implemented in the C library, but as far as the 8087 coprocessor is concerned, it''s just about the same thing :

FLDLG2 - push log₁₀(2) on the FP stack
FLDLN2 - push ln(2) on the FP stack

FYL2X - computes Y*log₂(X)

Thus log₁₀(X) is


FLDLG2
FLD X
FYL2X

and ln(X) is


FLDLN2
FLD X
FYL2X

Bagel Man

Mar 17, 2003 at 11:57 PM

Actually, log(x) in C++ IS ln. To do a base 10 log, you use log10(x)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.