Number theory, converting numbers too different bases

SNOOTCHIEBOOCHEE · Oct 5, 2008

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.

SNOOTCHIEBOOCHEE · Oct 6, 2008

Any thoughts?

Number theory, converting numbers too different bases

Homework Statement

The Attempt at a Solution

Discussion

Finding the range of k for three real roots of a cubic

Hi! Can someone explain about Differential Equations?

Deriving spatial derivatives

What does "compute Aut(G)" mean?

J_1(x) = (x^2/10)*(J_1(x) + J_3(x)) How to solve?

Insights Revisiting the Velocity-Time Function

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

Number theory, converting numbers too different bases

Homework Statement

The Attempt at a Solution

Discussion

Similar threads

High School Two interesting number theory tricks

Undergrad Is my proof that lcm(a,b) = ab/gcd(a,b) valid?

Mathematica How do I convert a hexadecimal number to base 10 in Mathematica?

Graduate How can primorials be used to generate a sequence of prime numbers?