1

I have a, very long, integer. The integer is represented by a array of unsigned chars.

Example: the integer 1234 with base 10 is represented in the array as [4,3,2,1], [2,2,3,2] (base 8) and [2,13,4] (base 16)

Now I want to convert my integer with base n to another integer with base m. In my persued for a answer I came accross Wallar's algorithm, originally from here. 

from math import *
def baseExpansion(n,c,b):
    j = 0
    base10 = sum([pow(c,len(n)-k-1)*n[k] for k in range(0,len(n))])
    while floor(base10/pow(b,j)) != 0: j = j+1
    return [floor(base10/pow(b,j-p)) % b for p in range(1,j+1)]

At first I thought this was my answer but unfortunately it is not. The problem I have is that the algorithm computes the sum. In my case this is a problem because the variable base10 is of type unsigned integer of 32 bits. Therefore when my integer, represented as a array, has more then 10 digits it can not convert the number anymore. Anyone has a solution?

Community
  • 1
  • 1
WG-
  • 1,046
  • 2
  • 14
  • 27

1 Answers1

1

Here's the school-book algorithm for doing what you're trying. You start with a representation for zero and call it a running total. Then, for each digit of the number to be converted, starting with the most significant and going to the least significant, 1) multiply the running total by the base of the source number and 2) add the digit to the running total. Now all you need is algorithms to do the multiplication and addition (and you can actually do both at once). Here's how to do that: 1) set the current digit to a variable, call it "carry", 2) for each digit in your new number, starting with the least significant and going to the most significant: 2a) set carry to the current digit in the new number times the output base plus carry, 2b) set the current digit to carry mod the output base, 2c) set carry to carry divided by the output base. And that should do it. There is an implementation of what you are trying to do somewhere here: http://www.cis.ksu.edu/~howell/calculator/comparison.html

Timmy
  • 26
  • 2