base conversion

[Sarad AV]

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