Re: Fast Binary to BCD method on ARM9 with huge numbers?
From: Robert Wessel (robertwessel2_at_yahoo.com)
Date: 03/10/04
- Next message: Jack Klein: "Re: BLDC motor motor control - speed time response"
- Previous message: Jim Stewart: "Re: CPLD and FPGA designs"
- In reply to: Al Borowski: "Fast Binary to BCD method on ARM9 with huge numbers?"
- Next in thread: Al Borowski: "Re: Fast Binary to BCD method on ARM9 with huge numbers?"
- Reply: Al Borowski: "Re: Fast Binary to BCD method on ARM9 with huge numbers?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 9 Mar 2004 20:06:00 -0800
Al Borowski <aj.borowski@erasethis.student.qut.edu.au> wrote in message news:<404e3e49$0$22515$5a62ac22@freenews.iinet.net.au>...
> Hi all,
>
> I have an ARM9 based system, and am trying to convert a large binary
> number into BCD. The legacy codebase works in BCD, and changing it is
> not an option. I also need all the digits, not just some.
>
> The number I can trying to convert may be *huge*. I have a positive
> ingtger that could span many words, in the format
>
> <size field> <word 1> <word 2> .. <word n>.
>
> Once converted to BCD, there could easily be five thousand digits.
>
> I's there a faster way then simply dividing by ten over and over again?
> Considering there is no DIV instruction, this method is probably too slow.
>
> Code size isn't really an issue, but obviously I can't have terabyte
> lookup tables.
>
> There's also the so-called 'ADD-3' method before
> (http://koli.kando.hu/eagle/pic/2002/bintobcd.htm), will be much faster?
>
> Are there any other ways I don't know about?
For a simple improvement, instead of dividing my ten, divide by
1,000,000,000 repeatedly, and then process each remained down into
nine decimal digits. About nine times faster, overall. Or use the
largest power of ten you can comfortably divide by. With ARM you'll
probably be doing the usually multiply-by-reciprocal-and-shift thing
for the division. If you've got an ARM with long multiplies, divide
by one billion, without long multiplies, you're probably best off
using 10,000. You can tweak this a little by dividing by the largest
convenient power of five instead, and then shifting by enough extra
bits to convert that back to a power of ten (you can do 13 digits at a
time by dividing by 5**13 and 2**13 in each pass). And be sure to
keep truncating your dividend as the high words zero out – that'll
double throughput right there.
If you've got a bignum package of some sort available, particularly
one with a fast multiply (and by extension a fast divide), you're best
bet for reasonably large numbers will be to divide by a power of ten
close to the square root of the number (eg. if you've got a 1000 bit
binary number, divide by about 10**150). This will split the number
into left and right decimal "halves." With the 1000 bit example,
you'd end up with the left 152 decimal digits in the quotient, and the
right 150 digits in the remainder. Then recursively convert the
quotient and remainder (the two halves) to decimal with the same
algorithm, until the pieces get down to some size where a simpler
approach is faster.
- Next message: Jack Klein: "Re: BLDC motor motor control - speed time response"
- Previous message: Jim Stewart: "Re: CPLD and FPGA designs"
- In reply to: Al Borowski: "Fast Binary to BCD method on ARM9 with huge numbers?"
- Next in thread: Al Borowski: "Re: Fast Binary to BCD method on ARM9 with huge numbers?"
- Reply: Al Borowski: "Re: Fast Binary to BCD method on ARM9 with huge numbers?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
