Sarad AV writes:
If we are to convert a k-bit integer n to a base b number,it takes us O(log n) if the base b is a power of 2. eg. converting (11111)base to base 16
0001 1111 ^ ^ 1 F in hex.
using a look up table.
Is there an algorithm with time complexity O(log n) which allows such conversion to base b ,when b is not a power of 2?
The algorithm you describe is linear, not log. Complexity measures are a function of the size of the input data set in bits. In general, a large integer M will require an input around N = LOG2(M) bits to represent. A linear algorithm will take twice as long to process a 2 megabyte integer, as it takes to process a 1 megabyte integer. You ask whether there are linear algorithms for arbitrary precision base conversion. I seem to recall that Schonhage showed how to do base conversion with an FTT along with his well-known fast multiplication algorithm. So my guess would be that there are no known linear arbitrary precision base conversion algorithms, but probably something O(n log(n))-ish as the best currently achievable. As usual, Google is your friend. I think near-linear reciprocals, nth roots, and base conversions are covered in "Pi and the AGM" by the Borweins. My copy is packed in a box somewhere, so I can't check. Perhaps you can find the book at your local university library. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"