Re: Converting base 255->256 and vice versa
From: Willem (willem_at_stack.nl)
Date: 01/08/04
- Next message: Joseph Dionne: "Re: To Richard Heathfield: enough's enough"
- Previous message: Programmer Dude: "Re: C Sharp RichEditBox HyperLinks"
- In reply to: Thad Smith: "Re: Converting base 255->256 and vice versa"
- Next in thread: Willem: "Re: Converting base 255->256 and vice versa"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 8 Jan 2004 19:31:36 +0000 (UTC)
Thad wrote:
) Graham Lewis wrote:
)
)> I'm trying to convert a 32 byte wide, base 255 number to base 256.
)
) A easy way to convert is to build up the number an input digit at a
) time, starting with the msd.
)
) As an example, assume that the input digits are a, b, c, ..., base 255.
)
) x = a
) x = x*255 + b
) x = x*255 + c
) ...
)
) Of course, you need to use multiple precision arithmetic for x. Note
) that you only need to be able to multiply by 255 and add a single digit.
)
) Use the normal hand multiply technique for multiplying by 255,
) multiplying each digit of the multiplicand with the multiplier (255),
) saving the lower digit of the product and carrying the higher digit.
) There is also a shortcut for this particular base in which you multiply
) by 256 then subtract the original number, in which you avoid the
) multiply operation (useful for low end micros without a multiply).
)
) Adding a single digit is just like hand addition, where you add digits
) together, keeping the lower order digit and carrying the high order
) digit to the next summation.
You can rearrange the operations so that you don't need to have the source
number, you can just do simple operations on the target.
Basically, you repeatedly subtract x/256 from x, but only the leftmost
digits. Each round, you subtract one digit more.
Some C-code that does this: (NB: I'm not 100% sure it works in all cases)
uchar num[32];
for (i = 32; --i > 0; ) {
c = 0;
for (j = i; j < 32; j++) {
r = num[j-1] - num[j] - c;
c = 0;
while (r < 0) {
c++;
r += 256;
}
num[j-1] = r;
}
num[31] -= c;
}
The other way around is similar, but with additions instead of subtractions.
for (i = 32; --i > 0; ) {
c = 0;
for (j = i; j < 32; j++) {
r = num[j-1] + num[j] + c;
c = 0;
while (r > 254) {
c++;
r -= 255;
}
num[j-1] = r;
}
num[31] += c;
}
NB: with this second routine, you may get an oiverflow in the top digit,
as base-255 can hold less than base-256.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
- Next message: Joseph Dionne: "Re: To Richard Heathfield: enough's enough"
- Previous message: Programmer Dude: "Re: C Sharp RichEditBox HyperLinks"
- In reply to: Thad Smith: "Re: Converting base 255->256 and vice versa"
- Next in thread: Willem: "Re: Converting base 255->256 and vice versa"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
