base conversion

[Eric Cordian]

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"