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(a)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(a)cse.unl.edu
402-432-0795
Show replies by date