lol@tim ,good work! --- Tim May <timcmay@got.net> wrote:

On Wednesday, October 8, 2003, at 06:16 AM, Sarad AV wrote:

...

hi,

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?

I have decoded this latest bit of "homework stego" and have found the plaintext:

"Attack the Islamic Center in Hyderabad at the rise of the new moon."

I assume Sarad's readers have now gotten coordinated.

--Tim May "Aren't cats Libertarian? They just want to be left alone. I think our dog is a Democrat, as he is always looking for a handout" --Unknown Usenet Poster

__________________________________ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com

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