Re: 6 byte integer to string

From: Derrick Coetzee (dcnews_at_moonflare.com)
Date: 09/26/04 

Date: Sun, 26 Sep 2004 13:20:24 -0400

Alex Fraser wrote:
> If the platform can do 32-bit division (32-bit dividend and divisor to
> 32-bit quotient and remainder) in hardware, then the quickest way is
> probably to start by dividing the 48-bit number by 100000 in software. The
> remainder from that division contains the least significant five digits, and
> the quotient (which is guaranteed to fit in 32 bits) contains the most
> significant digits. Then use the hardware divide to extract the digits from
> each part (dividing by 10).
>
> If there is no hardware divide, I don't know of any better way than the
> obvious repeated division by 10.

I came up with a custom algorithm for doing unsigned 32-bit division of
x by 10 using only a couple shifts and x % 5 hardware multiplications.
I'm not sure if it's the most efficient approach, but it is pretty neat.
On a platform with 32-bit ints and it goes like this:

struct div_result {
     unsigned int quotient;
     unsigned int remainder;
};

#define FIVE_INVERSE 3435973837u
struct div_result divide10(unsigned int x) {
     struct div_result result;
     result.remainder = x & 1;
     x >>= 1;
     unsigned int xdiv4 = x >> 2;
     result.quotient = x * FIVE_INVERSE;
     if (result.quotient <= xdiv4) return result;
     result.remainder += 2; x--;
     result.quotient = x * FIVE_INVERSE;
     if (result.quotient <= xdiv4) return result;
     result.remainder += 2; x--;
     result.quotient = x * FIVE_INVERSE;
     if (result.quotient <= xdiv4) return result;
     result.remainder += 2; x--;
     result.quotient = x * FIVE_INVERSE;
     if (result.quotient <= xdiv4) return result;
     result.remainder += 2; x--;
     result.quotient = x * FIVE_INVERSE;
     return result;
}

I've tested this function on all 2^32 values of an unsigned int. It
effectively works by searching for the nearest number <= x/2 which is
divisible by 5 and then divides it by 5 by multiplying by the inverse of
5 in the group Z(2^32). It knows when it worked because otherwise it
gets a big result exceeding x/8. 

-- 
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.

Relevant Pages

  • Re: Linear Algebra Challenge
    ... there is a precision called double extended which is 80 bits; ... No, can't be in hardware. ... The bigfloat math has arbitrary precision and ... give you about 19 digits. ...
    (comp.sys.hp48)
  • Re: Mixed fixed point Q format multiply?
    ... binary point is the sum of the digits after the binary ... In hardware, you just have to get out the appropriate bits. ... leftmost 33 bits of the product, ...
    (comp.dsp)
  • [PATCH 4/7] Add mISDN DSP
    ... It may use hardware features if available. ... * of the GNU General Public License, ... +extern int dsp_options; ... * each conference has a unique number, ...
    (Linux-Kernel)
  • Re: Explanation needed of binary operators
    ... I am trying to read an int from a file written in binary. ... binary data as an "archaic" file structure. ... int in Java but don't understand what is happening. ... Big-endian hardware stores bytes in memory in their "natural" format, ...
    (comp.lang.java.programmer)
  • Re: Linux-next Alsa hda_intel events/0 high CPU usage, bisected
    ... I didn't expect that this delay is so much, (IOW, the hardware is so ... Could you check the patch below in addition? ... This will show some latency time in the kernel messages. ... static int single_cmd; ...
    (Linux-Kernel)
Loading