6 byte integer to string

[sudi]

HI,
I face the task of converting a 6 byte integer (MSB first) to a
decimal string.
The platform I use supports only 4 byte basic data type. I have
written some algorithms that loops to many times :-(. It would be
great help if any of you can share a high performance algorithm to do
this.

Thanks
Sudi

 

[lallous]

Hello,

HI,
I face the task of converting a 6 byte integer (MSB first) to a
decimal string.
The platform I use supports only 4 byte basic data type. I have
written some algorithms that loops to many times :-(. It would be
great help if any of you can share a high performance algorithm to do
this.

Thanks
Sudi

Can you give an example of what you want exactly?

Are you looking for something like IntegerToString() ?

 

[Alex Fraser]

I face the task of converting a 6 byte integer (MSB first) to a
decimal string.
The platform I use supports only 4 byte basic data type. I have
written some algorithms that loops to many times :-(. It would be
great help if any of you can share a high performance algorithm to do
this.

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. You could perhaps get some improvement by
reducing the size of the division as you go.

Alex

 

[Derrick Coetzee]

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 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.

Wait - I'm an idiot. I only need ONE hardware multiplication! Here's the
revised algorithm:

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;
result.quotient -= FIVE_INVERSE;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
if (result.quotient <= xdiv4) return result;
result.remainder += 2;
result.quotient -= FIVE_INVERSE;
return result;
}

Once again tested on all unsigned 32-bit integers.

 

[Derrick Coetzee]

result.quotient = x * FIVE_INVERSE;

As an aside, on platforms with no hardware multiply, we can exploit the
regular bit pattern of FIVE_INVERSE to write this statement like this:

unsigned int temp = (x << 3) + (x << 2);
temp = (temp << 4) + temp;
temp = (temp << 8) + temp;
temp = (temp << 16) + temp;
result.quotient = temp + x;

The final program is then this, with 6 shifts, 1 AND, and 5-13 adds:

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

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

Once again, exhaustively tested.

 

[Ben Pfaff]

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, [...]

I doubt it. The book _Hacker's Delight_ describes a general
algorithm for unsigned division by a constant that only requires
one multiplication and a little error correction, typically ten
or so cycles on a RISC processor.

 

[Derrick Coetzee]

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, [...]

I doubt it. The book _Hacker's Delight_ describes a general
algorithm for unsigned division by a constant that only requires
one multiplication and a little error correction, typically ten
or so cycles on a RISC processor.

My approach also requires only one multiplication (see my reply updates
to myself) and doesn't require a 64-bit product like the one you cite.
On the other hand, my approach doesn't scale to division by larger
constants very well.

 

[Derrick Coetzee]

My approach also requires only one multiplication (see my reply updates
to myself) and doesn't require a 64-bit product like the one you cite.
On the other hand, my approach doesn't scale to division by larger
constants very well.

Er, although now that I look it also describes some other algorithms
that don't require a 64-bit product:

http://www.hackersdelight.org/divcMore.pdf

Thanks for the reference.

 

[CBFalconer]

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. You could perhaps get
some improvement by reducing the size of the division as you go.

A general solution to this problem, quite old, is to convert to
BCD via the hoary old double/dabble algorithm. It is all
explained in:

<http://cbfalconer.home.att.net/download/dubldabl.txt>

This is an algorithm, so discussion belongs on comp.programming.
However discussion of a C implementation belongs here.