Arxius

Archive for the ‘Enginyeria’ Category

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.

 

 

 

 

Anuncis

El xino que provava els tablets s’ha quedat sense feina

No m’he pogut estar de re-postejar el video que he vist avui sobre l’ingeniós i divertit sistema que han elaborat a Kno per testejar els seus tablets.

 

La obsolescència programada : cal un documental per ser-ne conscient ?

Ja fa unes setmanes es va emetre per TV3 el documental “comprar, llençar, comprar”.

Aquest documental, que posteriorment també s’ha emès per televisió espanyola en la seva versió castellana, parla sobre l’obsolescència planificada (o programada), un fenomen característic del disseny de productes sorgit del sistema productiu capitalista, en la que els lobbys de determinats sectors empresarials acorden uns màxims per els cicles de vida dels productes que comercialitzen, per tal de poder crear un increment en la seva necessitat d’adquisició. És a dir, escurçar la vida útil dels productes per aconseguir més vendes.

La idea, per ella mateixa, és un evident símptoma de la insostenibilitat del sistema capitalista actual, i com aquest ha estat incapaç de crear el que suposadament hauria de ser un “mercat lliure” per tal de promoure la auto-regulació de la productivitat basada en la sana competència.

Jo vinc d’una família amb vocació d’enginyer. Des de petit, tant el meu pare com els meus 2 avis m’han ensenyat a construir i manipular des de la fusta i el ferro fins a complicats circuits electrònics (primer analògics i posteriorment digitals), per tal d’acabar convertint-me – com no podia ser menys – en enginyer informàtic. A casa meva sempre hem tingut un contacte immediat amb tot tipus d’eines i maquinària, i si alguna cosa se m’ha inculcat amb incansable persistència en la meva educació, és que les coses ben fetes no tenen fronteres. Ho volia deixar clar per tal de fer entendre que el meu punt de vista no és parcial, i que des de  petit conec molt bé aquesta veritat sobre la obsolescència programada, o com li solia dir el meu avi “basura d’un sol ús”.

Tot i que no tenia intenció de postejar sobre un tema com aquest (se’m encongeix realment el cor de vergonya quant hi penso), donat el resó que he vist en varis blogs sobre el documental emès, i arran també d’una petita discussió que vaig tenir l’altre dia amb un bon company, he pensat que és interessant intentar difondre per tots els canals possibles aquesta gran veritat que molts consumidors ignoren.

Així doncs, més enllà de la tristesa que m’aclapara al intentar buscar alguna explicació moral a aquesta atrocitat de la enginyeria moderna, des d’aquí m’agradaria felicitar a la realització del documental, i convidar a tothom que pugui i no n’hagi sentit parlar mai, a veure’l i informar-se sobre com la suposada societat del ben estar es riu de nosaltres a la nostra pròpia cara.

Altres URLs on podeu trobar el documental :

http://www.megaupload.com/?d=KGTOXG9Z (en català)

http://www.rtve.es/mediateca/videos/20110109/comprar-tirar-comprar/983391.shtml (en castellà)

Categories:Enginyeria
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