Pàgina d'inici > Enginyeria, Informàtica, Matemàtica, Tecnologia, Uncategorized > Number base conversion from 64 to 58

Number base conversion from 64 to 58

If you are only looking for an example, you can find one here in my GitHub.

It would seem that a number base conversion is easy. And it is unless you deal with very large numbers. In this case, the problem gets worse. Here I explain how I developed an efficient base change algorithm that will take simple execution requisites for large number conversions.

As this nice page explains, the simplest way to convert base number is this algorithm:

// M = input number, N = output base,
result = “”
if M < N, result = ‘M’ + result. Stop.
S = M mod N, result = ‘S’ + result
M = M/N
goto 2

For example, if we try to convert 100 from base 10 to base 16, we should follow these steps:

M = 100, N = 16
100 < 16 ?
S = 4, result = ‘4’
M = 100/16 = 6
6 < 16 ?
result = ’64’

And therefore, we’ll get that 100 is equal 64 in base 16.

However, this algorithm involves working with the whole input number in math operations (such as division and modulus). If you tried to convert a long number (let’s suppose a long number has more than 30 digits), it would be needed a very long numeric data type for this operations. For instance, to allow a 60 hexadecimal digit number, we would need a 240-bit (30 bytes) data type number, which does not exist in most languages (usually the largest types are long and double-precision, with 64 bit).

So, I tried to find out a different way to manage a base conversion, where it would be possible to slice the number and work with their parts independently. It came to me that there must be an easier way to shift a number by only 1 base. And actually there is.

Let’s try to explain it with a simple example. Imagine you want to convert a 2 digit number from base 16 to base 15, for instance, the number “43 hex”. The second digit of this number (4) means that in fact, we have added 4*16 times the 1 value. If we try to allocate the same value in a 15 base number, we could find easily that: (4*16) = 4 * (4*15), so the second digit remains as “4”, but we must add the same second digit value to the first digit value (4+3). Finally, we get that “43” base 16 = “47” base 15. Notice that we did this conversion only with a simple and independent digit sum.

Well, to be fair let’s see the worst case in this conversion example. Let’s try to convert in the same way the number “FF hex” to 15 base. If we apply the same rule, by decoding the number as “FF = (F * 16) + F = (F * 15) + F + F”, we’ll have an overflow at the first digit (F + F = 1E), so we must add (carry) this “1” spent value to the second digit. And then, the second digit “F + 1” will also have another overflow, and will also take another carry value to the next digit. So finally we’ll get that “FF hex” equals to “1FE” in base 15. In fact, the method is the same, though we must pay attention to the carry values.

Now let’s try to convert a 4 digit number “5A78 hex”. In order to introduce yourself to my algorithm’s notation, I’m going to write this number as an integer array: “5A78 hex” = [5,10,7,8]. If we try to apply the same method, we’ll find that “[5,10,7,8] = (5 * 16³) + (10 * 16²) + (7 * 16) + 8”. By decoding every part independently, we’ll get:

(8 * 16⁰) = (8 * 15⁰) = [0,0,0,8]
(7 * 16¹) = (7 * 15) + 7 = [0,0,7,7]
(10 * 16²) = (10 * 15²) + (10 * 2 * 15) + 10 = [0,10,(10*2),10]
(5 * 16³) = (5 * 15³) + (5 * 3 * 15²) + (5 * 3 * 15) + 5 = [5,(5*3),(5*3),5]

It means that, for shifting each digit, we must add the following values:

5 10 7 8  
      8 the first digit needn’t be shifted
    7 7 to shift the second digit
  10 20 10 to shift the third digit
5 15 15 5 to shift the fourth digit
5 25 42 30 without carrying the overflows
6 12 14 0  

And thereafter, without missing the overflow carries, we’ll get the result = [6,12,14,0].
Notice that the same matrix would work for any other 4 digit conversion since we express the accumulators (the numbers we must add to shift the digits) as a multipliers of the original digits:

d c b a
      a
    b b
  c 2c c
d 3d 3d d

So, by following this method we can increase this matrix in size to the needed digits, and then apply simple sums for each digit. For instance, the 8 digit conversion matrix  is equal to:

h g f e d c b a
              a
            b b
          c 2c c
        d 3d 3d d
      e 4e 6e 4e e
    f 5f 10f 10f 5f f
  g 6g 15g 20g 15g 6g g
h 7h 21h 35h 35h 21h 7h h

We can also apply this to convert, for example, the number “39485A78 hex”. We only must apply this fix multiplier matrix:

              1
            1 1
          1 2 1
        1 3 3 1
      1 4 6 4 1
    1 5 10 10 5 1
  1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

To the specific values:

  3 9 4 8 5 10 7 8
8               8
7             7 7
10           10 20 10
5         5 15 15 5
8       8 32 48 32 8
4     4 20 40 40 20 4
9   9 54 135 180 135 54 9
3 3 21 63 105 105 63 21 3
  3 30 121 268 362 311 169 54
  5 9 5 8 8 7 7 9

Once here, you should have noticed that the next goal should be to set a method for building any size multipliers matrix. Indeed, as you may have graphically seen, there’s an easier way to build the matrix without decoding each digit into a mathematical expression. Instead, we can iterate each digit and get the next multiplier value by adding the multiplier value at its previous position (at its right position in the grid). It would be something like:

 

gapi

We could easily get this with the following double loop:

var buffer_mult = [1,0,0,0,0,.....]; // First multiplier must be set as 1
for (var cdig = 0; cdig < buffer_mult.length; cdig++) {
    for (var t = cdig; t > 0; t--) buffer_mult[t] += (buffer_mult[t - 1] || 0);
}

This method always works for every number.

However, in the same way as the matrix grows, we’ll get higher multiplier values. We can reach several millions at a 30 digit conversion though there’s an optimization to avoid this lack. Shifting the multiplier values up, with a modulus and carry values at the conversion base, we could manage to avoid big numbers getting the same result.

For instance, in the last example we can optimize the seventh interation by shifting up the values over 15:

  1 6 15 20 15 6 1
    +1 +1 +1      
  1 7 1 6 0 6 1
1 8 8 7 6 6 7 1

and get the same result with fewer multiplier values.

.

Practical case: Convert from hexadecimal to 58 base

.

A practical case of this method could be used to convert from base 64 to base 58. It is usual to need number conversion to base 58 when you’re dealing with bitcoin addresses, URL shorteners and others. Therefore, it is nice to have a good way to do it.

I did it by applying this method with good results. I applied 6 times the algorithm, shifting from base 64 to base 58. I had good results with some 80 digit hexadecimal numbers. Fast executions, with less than 50.000 iterations, and maximum variable’s values under 200.000.

If you’d like to check it out, you can find this example developed in a simple html/javascript page just here in my GitHub repository, or try it working here.

gapi.png

Or if you are not still satisfied, here’s another page where you can find another ways to get the same.

 

 

 

 

Advertisements
  1. Encara no hi ha cap comentari.
  1. No trackbacks yet.

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s

Enfilant el camí

Visualitzant el present per construir el futur

El Noguer

Visualitzant el present per construir el futur

Visualitzant el present per construir el futur

%d bloggers like this: