Mailing List Archive: logarithmic approximations

logarithmic approximations

Nov 14, 2002, 8:18 AM

Post #1 of 3 (404 views)

I'm working on a project right now using GNU's multiprecision library.
However, and unfortunately, there are no library functions to do any
logarithmic functions.

I'm merely trying to get a ceiling (or floor) or the lg (base 2) of a
large integer. Of course, I could always send it into a loop requiring
O(lg^3(n)) to get it, but I know there must be a way to do a simpler
approximation, especially since I don't need very high precision.

I asked this question of some math associates and they suggested the usual
taylor series, etc. However, I am unable to find a satisfactory series
for a large n (taylor only works for x<1, right?).

Any help would be appreciated.

-----------------------------------------------

Chris Bourke
cbourke@cse.unl.edu
402-432-0795

RE: logarithmic approximations [ In reply to ]

Edmund.W.Poor at abc

Nov 14, 2002, 8:29 AM

Post #2 of 3 (396 views)

Permalink

How about shifting left, and counting how many shifts it takes to get to the first "1" digit? This will work, if you have an unsigned two's-complement integer, won't it?

Ed Poor

-----Original Message-----
From: Chris Bourke [mailto:cbourke@cse.unl.edu]
Sent: Thursday, November 14, 2002 10:19 AM
To: wikitech-l@wikipedia.org
Subject: [Wikitech-l] logarithmic approximations

I'm working on a project right now using GNU's multiprecision library.
However, and unfortunately, there are no library functions to do any
logarithmic functions.

I'm merely trying to get a ceiling (or floor) or the lg (base 2) of a
large integer. Of course, I could always send it into a loop requiring
O(lg^3(n)) to get it, but I know there must be a way to do a simpler
approximation, especially since I don't need very high precision.

I asked this question of some math associates and they suggested the usual
taylor series, etc. However, I am unable to find a satisfactory series
for a large n (taylor only works for x<1, right?).

Any help would be appreciated.

-----------------------------------------------

Chris Bourke
cbourke@cse.unl.edu
402-432-0795

Re: logarithmic approximations [ In reply to ]

taw at users

Nov 14, 2002, 10:31 AM

Post #3 of 3 (394 views)

Permalink

On Thu, Nov 14, 2002 at 09:18:39AM -0600, Chris Bourke wrote:
>
> I'm working on a project right now using GNU's multiprecision library.
> However, and unfortunately, there are no library functions to do any
> logarithmic functions.
>
> I'm merely trying to get a ceiling (or floor) or the lg (base 2) of a
> large integer. Of course, I could always send it into a loop requiring
> O(lg^3(n)) to get it, but I know there must be a way to do a simpler
> approximation, especially since I don't need very high precision.
>
> I asked this question of some math associates and they suggested the usual
> taylor series, etc. However, I am unable to find a satisfactory series
> for a large n (taylor only works for x<1, right?).
>
> Any help would be appreciated.

You can use mpfr library which is addon for GMP, which has all the
functions you want.

-- Taw, author of Ruby bindings to GMP