Re: Converting base 255->256 and vice versa

From: Thad Smith (thadsmith_at_acm.org)
Date: 01/08/04 

Date: Thu, 08 Jan 2004 10:43:58 -0700

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.

Thad

Relevant Pages

  • Re: Myth about mathematicians and mental arithmetic
    ... I think mathematicians are more likely than normal ... The cube root of 32768 is of course 32. ... way easier than multiplying two 3 digit numbers together in your head. ...
    (sci.math)
  • Re: How do I hash this?
    ... I got some primary key failures which would indicate matching keys. ... So your hash value could be x * 6320 ... less than y but I'm not sure why multiplying by 79 * 80 makes it ... They are the possible permutations with 1 digit. ...
    (comp.programming)
  • Re: Converting base 255->256 and vice versa
    ... 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, ... Basically, you repeatedly subtract x/256 from x, but only the leftmost ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: 500!
    ... The algorithm is just multiplying each digit of the current total by ... C++ FAQ: http://www.parashift.com/c++-faq-lite/ ...
    (microsoft.public.dotnet.languages.vc)
  • Re: math class from Hell (aka Bantys nightmare)
    ... Now I've been told that the school does it as ... I'm a bit confused since your example doesn't involve carrying. ... My son is adding and subtracting two and three digit numbers. ...
    (misc.kids)