470,616 Members | 2,138 Online

# converting numbers between number systems 8,656 Expert Mod 8TB
I recently found a problem I haven't seen a good solution yet.

this is just the general conversion from a number between number/notation systems (e.g. decimal, binary, octadecimal notation)
Expand|Select|Wrap|Line Numbers
1.  ∞             ∞
2.  Σ{a(i)⋅n^i} = Σ{b(j)⋅m^j}
3. ∞            ∞
n, m  base of the number system
a(i)  given coefficients of number in system n
b(j)  unknown coefficients of number in system m

ex:
Expand|Select|Wrap|Line Numbers
1. 10110 (2) = 28 (10)
2. n = 2, a(1) = a(2) = a(4) = 1, a(x) = 0 (x not 1,2 or 4)
3. m = 10, b(0) = 8, b(1) = 2, b(x) = 0 (x not 0 or 1)
the solution I know is an iterative one, but I wonder if there is an analytical solution to this equation at all.
maybe something like:
Expand|Select|Wrap|Line Numbers
1. a(i) = f(m,n,i,b(j))
Dormi
Jan 15 '09 #1
6 4252 jkmyoung
2,057 Expert 2GB
Are you trying to find a specific a(i) given variable i, and fixed m, n, and b(j)'s? If so, the solution probably uses specific mod rules, dependent on m and n.
Jan 15 '09 #2
Dormilich
8,656 Expert Mod 8TB
@jkmyoung
no, I want all coefficients a, but I guess the coefficient for a given i (a(i)) depends on i, m, n and all coefficients b. (just feels like that)

(I mixed up a and b in the last code block, but it doesn't matter as long as you imagine b as given, instead of a)

@jkmyoung
that's what the iteration way uses.
Jan 15 '09 #3
FishVal
2,653 Expert 2GB
@Dormilich
I guess this could not be resolved unless logn(m) is an integer and j*(logn(m)-1)-1 <= i <= j*logn(m)-1.

Did you mean
Expand|Select|Wrap|Line Numbers
1. a(i) = f(m,n,i,b)
Jan 22 '09 #4
Dormilich
8,656 Expert Mod 8TB
@FishVal
I don't have an idea, what the result function depends on, that's really only a guess.

note: b(j) means "b with index j", but I couldn't make it display this way
Jan 22 '09 #5
jkmyoung
2,057 Expert 2GB
What is the criteria for solving this? Do you want a faster algorithm? One that takes less space on a computer?
Recursive, eg,
a(i) = f(m,n,i,b a(i-1))
or relate it somehow to another function?
Jan 23 '09 #6
Dormilich
8,656 Expert Mod 8TB
@jkmyoung
not the iterative way (means applying mod n recursively, a.k.a. a(i) = f(m,n,a(i-1)) ), just a solution where each coefficient can be computed separately.
Jan 23 '09 #7