Number theory, converting numbers too different bases

SNOOTCHIEBOOCHEE
Messages
141
Reaction score
0

Homework Statement



Show that for any fixed a and b, there is an algorithm to convert an n-digit number from
base a to base b with O(n^2) operations.

The Attempt at a Solution



Really i am completley lost here. Working backwards, i know to convert from base a to a base b you must use the division algorithm, which requires something on the order of (n^2) operations, but i really don't know how to show any of this.
 
Physics news on Phys.org
Any thoughts?
 

Thread 'Finding the nth roots of a complex number'

There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
View full post »

Similar threads

Prove that ##\lim\limits_{x \to \infty} f(x) = 0##
Replies
3
Views
515
Finding GCD with Fibonacci: Base Case
Replies
1
Views
1K
Proving geometric sum for complex numbers
Replies
6
Views
2K
Base 8 Logic Puzzle: Finding Solutions to Divisibility Rules
Replies
9
Views
2K
Finding the nth roots of a complex number
Replies
21
Views
219
Probability of girls on a team getting shirts with pair numbers
Replies
3
Views
1K
Person i belongs to a clique iff ith diagonal entry of B^3 is positive
Replies
9
Views
1K
Factorize a number in a different base
Replies
1
Views
1K
I On base-b expansion of nonnegative reals
Replies
7
Views
2K
Prove every subset of countable set is either finite or else countable
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top