'fraction of Binary to Decimal convertation'
Sometimes ago discussion about Binary to Decimal convertation has taking
place. Very interesting ideas was introduced. But all of it was pointed
to convertation of int part of binary to the int part of decimal
Has anyone ideas in suggestion box how to quickly and unexpensivly
fractional part of binary to decimal view ? For instance we have number
format 0xFFEFBB.AAC6 where FFEFBB is int part of number and AAC6 is
tional part of number. (with powers of 1/2 1/4 1/8 1/0x10 1/0x20 ...)
For this moment I see only one way to make this. The fractional part
is multiplied by 100. or 1000. or 10000. and after that is converted
to binary. But multiplicating is very resource eating operation.
So asking is: If anyone knows a trick and would like to share it
with others please explaing the ideas of your solution.
Peter L. Peres
A fixed point binary number (which is what you suggest) can be written as:
Nb = Mi + Fj/2^j
where i,j are the number of bits of each respective part, M are the
mantissa bits and F are the fractional digits part.
Another way to say this is, if the M mantissa is represented with msb bits
and the F part with lsb bits, the mantissa can be extracted by shifting
the binary image right by j bits (and losing bits shifted right out of
lsb) , and the fractional part by masking the upper i bits to zero.
The mantissa is converted as we know it, and the fractional part in the
same way (it is now an integer like the mantissa).
The problem is, to add the converted fractional part to the converted
mantissa with correct alignment, with optional carry from the mantissa,
you first need to divide the converted fractional part by 2^j. Adding with
carry in decimal representation we know how to.
So, the big problem is, how do you divide a number in BCD or packed BCD
efficiently by 2^j. There are the obvious ways, but I can see a new
chapter of the piclist optimize-it-to-the-bone contest coming up now ;)
Adriano De Minicis
here is my routine. The inspiration came to me from Robert
Ferenbach's code (integer binary to packed BCD) and subsequent
discussion on this list.
Things are just reversed here: right shift the fractional number,
right shift the packed BCD number and adjust the BCD digits.
Repeat this a number of times equal to the bit size of the fractional
number and, here you are!
This routine may be easily adapted to any number of input bits and
any number of output digits.
Note: my responses have usually one day delay (I receive this list
as a daily digest) so may be at this time someone else has already
posted a similar solution... :-)
; 16 bit fractional binary to BCD
; Input: frac_hi, frac_lo (MSB..LSB, destroyed)
; Output: bcd12, bcd34, bcd56 (MSD..LSD, packed BCD)
; bcd12 holds the 1st and 2nd digit after the decimal point,
; Temp: bit_cnt
; 454 cycles, 29 words (16 bit to 6 digits) (if I'm not wrong)
; NOTE: The quantization for 16 bit fraction is 1/65536 ~= 1.52587E-5.
; So, a good choice would be to use 5 digits to represent the fractional
; part as a decimal number. However, since this routine uses packed BCD,
; it's simpler to have an even number of digits (that's why I choose 6).
; If you need less digits (or more), modify the routine as shown below.
; In the same way, to convert a fractional number of a different size
; simply add (or remove) rrf instruction(s) to shift the middle byte(s)
; between "rrf frac_hi" and "rrf frac_lo" (high-byte to low-byte order).
; v1.0 - Adriano De Minicis
; (I've done some tests, it seems ok)
movlw d'16' ; number of bits
movwf bit_cnt ; bit counter
clrf bcd12 ; clear output
clrf bcd56 ; -- may be omitted if you need only 4 digits
; clrf bcd78 ; ++ may be added if you need 7 or 8 digits
;------ Division by 2
rrf frac_hi ; divide fractional part by 2
; ++ Add here rrf of middle byte(s) (for more than 16 bits)
rrf frac_lo ; (MSb trashed)
rrf bcd12 ; divide packed bcd number by 2
rrf bcd34 ; (MSb is the remainder of frac)
rrf bcd56 ; -- may be omitted if you need only 4 digits
; rrf bcd78 ; ++ Add this if you need 7 or 8 digits
;------ BCD adjust
movlw bcd12 ; adjust carry
call div2adj ; (from most to least significant digit)
movlw bcd56 ; -- may be omitted if you need only 4 digits
call div2adj ; -- may be omitted if you need only 4 digits
; movlw bcd78 ; ++ Add this if you need 7 or 8 digits
; call div2adj ; ++ Add this if you need 7 or 8 digits
; Adjust carry bits
movwf FSR ; address of the BCD pair to adjust
movlw 0 ; default: no adjust
;------ High nibble test
btfsc INDF,7 ; carry from above?
iorlw 0x50 ; yes, prepare to add 5 to high nibble
bcf INDF,7 ; clear the carry bit
;------ Low nibble test
btfsc INDF,3 ; carry from high nibble?
iorlw 0x05 ; yes, prepare to add 5 to low nibble
bcf INDF,3 ; clear the carty bit
addwf INDF ; do the corrections
Greeting Adriano De Minicis.
> Note: my responses have usually one day delay (I receive this list
> as a daily digest) so may be at this time someone else has already
> posted a similar solution... :-)
Seems to be you are first responder with interesting idea ;-)
Thank you very much !
As I see the main idea is to substitute 8(.3 bit in each nibble) with 5.
Probably it may be done with substracting 3 from each nibble if nibble's
MSB bit is set. Sonething like the following...
; In: 01234567,89ABCDEF
; Out: 01234567,56789ABC
; The same shifting and cycling,
; only correction part is modified.
Adriano De Minicis
Right. Very nice optimization, Dmitry!
358 cycles instead of 806 (not 454 as I reported).
27 words instead of 29, and FSR is preserved.
Here is a detailed explanation of the algorithm.
The general structure is very easy:
clear binary digits
for i=1 to number_of_bits
rotate_right frac (LSb in carry, MSB doesn't care)
rotate_right binary digits (BCD/2 to be adjusted, carry from frac)
adjust binary digits
The interesting part is the adjust routine.
When you divide a decimal number by two, you can start from the left
dividing each digit by 2. Even digits are ok, but odd digits give a
remainder of .5 (for that decimal position) which must be added
somewhere. That value is added to the next digit (to the right),
which has a positional value of 1/10 of the preceding digit,
so we add 5. I hope you understand my broken english.. :-)
Here is an example:
98/2 From left to right:
9/2 = 4, remainder .5 -> add 5 to the next digit (carry)
8/2 = 4 (no remainder) + carry (5) = 9
If a digit is even, its bit#0 is 0, so when right shifting (to divide
by 2) no carry is generated, and the next digit (to the right) has a
correct value. But if the digit is odd, its bit#0 is 1, and when
shifting that bit become bit#3 of the next digit. In this case the
next digit must be adjusted. Note that after the rotation (division)
but before the adjusting phase each digit has a value 0..4 (only 3
bits are needed). The carry is in bit3 (binary value 8). Therefore,
if bit3 is set, we must add 5 to the lower 3 bits (which was what I
did in my routine: clear bit3 (that is subtract 8) and add 5), or,
as Dmitry noted, we could just subtract 3.
** BEFORE ROTATION
digit N ................. EVEN ODD
remainder of division 0 .5 (carry bit)
digit N+1 ............... 0123456789 0123456789
** AFTER ROTATION
digit N+1 ............... 0011223344 8899AABBCC
digit N+1 (bit 3 masked) 0011223344 0011223344
(carry from digit N) .... 0000000000 1111111111
(carry to digit N+2) .... 0101010101 0101010101
after BCD adjust ........ 0011223344 5566778899
note: N is the position of the digit after the decimal point,
so N is more significant than N+1 etc..
Better than 1024 words, here is an example of how the algorithm
works (8 bit fractional part, 4 digits output).
fraction = 10000110b = 134/256 = 0.5234375
step <--- binary -----> BCD
# frac bin_12 bin_34 digits
0 10000110 0000 0000 0000 0000 0000
0a (adjust) 0000 0000 0000 0000 .0000
1 x1000011 0000 0000 0000 0000 0000
1a 0000 0000 0000 0000 .0000
2 xx100001 >1000 0000 0000 0000 8000
2a 0101 0000 0000 0000 .5000
3 xxx10000 >1010>1000 0000 0000 A800
3a 0111 0101 0000 0000 .7500
4 xxxx1000 0011>1010>1000 0000 3A80
4a 0011 0111 0101 0000 .3750
5 xxxxx100 0001>1011>1010>1000 1BA8
5a 0001 1000 0111 0101 .1875
6 xxxxxx10 0000>1100 0011>1010 0C3A
6a 0000 1001 0011 0111 .0937
7 xxxxxxx1 0000 0100>1001>1011 049B
7b 0000 0100 0110 1000 .0468
8 xxxxxxxx >1000 0010 0011 0100 8234
8b (final) 0101 0010 0011 0100 .5234
1) step N -> right rotation (division by 2), step Na -> BCD adjust
2) the ">" before a digit means there is a carry (need to adjust)
One more improvement: adding this code at the beginning of frac_loop
(before rrf frac_hi) preserves the fractional part, at the cost of
48 cycles (3x16) and 3 words.
clrc ; carry in = frac.0
(sorry for the long posting)
|For this moment I see only one way to make this. The fractional part
|is multiplied by 100. or 1000. or 10000. and after that is converted
|to binary. But multiplicating is very resource eating operation.
|So asking is: If anyone knows a trick and would like to share it
|with others please explaing the ideas of your solution.
Conversion of a binary fraction to decimal is probably best done by
repeated multiplication by ten (which isn't all that expensive an
operation); the new MSB in each case is the next decimal digit. Perhaps
it's easiest to give some pseudo-code to show the technique:
Assume reg1 and reg2 are 32 bits long; the binary fraction to be output is
in the lower 24 bits of reg1
reg1 = reg1 << 1 /* << is the shiftleft operator */
reg2 = reg1 << 1
reg2 = reg2 << 1
reg1 = reg2 + reg1
output top 8 bits of reg1 and zero them
loop as needed
Estimated code size (not counting output or looping): 13 instructions for
the shifts and 14 for the adds--27 total).
There probably isn't much point in running the loop more than three times
for an 8-bit fraction, five times for a 16-bit fraction, or 7 times for a
24-bit fraction (since you'll be past the really-significant digits) but
if you want a fraction of 1345/65536 to display as 0.0205230712890625, you
can run the loop 16 times.
More... (looser matching)
- Last day of these posts
- In 1998
, 1999 only
- New search...