helo, thank you for the reply.
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.
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 is still a correct statement. Say if we are to multiply a k-bit integer n with the same k-bit integer n, i.e multiplying integer n with k-bits by itself. The multiplication takes atmost k^2 bit operations. eg. n=5=101 base 2. i.e the multiplication takes atmost 3^2=9 bit operations. Thus multiplication of O(k^2) for a constant c and n>=no. All logarithms are to the base 2. Since k=[log n]+1 k^2=([log n]+1)^2 in our example = ([log 5]+1)^2 =3^3=9 operations. it is correct to write O(log n)=O(k), as n or k are the inputs to an algorithm whose time complexity is to be determined. O(log n)=O(k)is the time the algorithm takes for processing the input which are essenctially the same.
You ask whether there are linear algorithms for arbitrary precision base conversion.
yes,I was asking if there is an algorithm in O(k)=O(log n) to convert a k-bit integer n to arbitrary base. I only know to do it in O(k^2). thanks, Sarath __________________________________ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com