Truncated match.
PICList
Thread
'fraction of Binary to Decimal convertation'
1998\12\14@205923
by
Dmitry Kiryashov
Greetings All.
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
numbers.
Has anyone ideas in suggestion box how to quickly and unexpensivly
convert
fractional part of binary to decimal view ? For instance we have number
in
format 0xFFEFBB.AAC6 where FFEFBB is int part of number and AAC6 is
frac
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.
WBR Dmitry.
1998\12\15@115641
by
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 optimizeittothebone contest coming up now ;)
Peter
1998\12\15@133635
by
Adriano De Minicis

Hi Dmitry,
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.
Adriano
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,
; etc..
; 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.52587E5.
; 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" (highbyte to lowbyte order).
;
; v1.0  Adriano De Minicis
; (I've done some tests, it seems ok)
frac2bcd
movlw d'16' ; number of bits
movwf bit_cnt ; bit counter
clrf bcd12 ; clear output
clrf bcd34
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
frac_loop
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 bcd34
call div2adj
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
;
decfsz bit_cnt
goto frac_loop
return
; Adjust carry bits
div2adj
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
return
1998\12\15@173022
by
Dmitry Kiryashov

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.
movlw 0x30
btfsc bcd_12,7
subwf bcd_12,f
btfsc bcd_34,7
subwf bcd_34,f
btfsc bcd_56,7
subwf bcd_56,f
movlw 0x03
btfsc bcd_12,3
subwf bcd_12,f
btfsc bcd_34,3
subwf bcd_34,f
btfsc bcd_56,3
subwf bcd_56,f
WBR Dmitry.
{Quote hidden}> div2adj
> 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
> return
1998\12\16@084728
by
Adriano De Minicis

{Quote hidden}> 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...
>
> movlw 0x30
> btfsc bcd_12,7
> subwf bcd_12,f
> btfsc bcd_34,7
> subwf bcd_34,f
> btfsc bcd_56,7
> subwf bcd_56,f
>
> movlw 0x03
> btfsc bcd_12,3
> subwf bcd_12,f
> btfsc bcd_34,3
> subwf bcd_34,f
> btfsc bcd_56,3
> subwf bcd_56,f
>
> WBR Dmitry.
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
next i
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
result: 49
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
Notes:
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
btfsc frac_lo,0
setc
Adriano
(sorry for the long posting)
1998\12\16@193303
by
John Payson

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 pseudocode 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
Loop:
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 adds27 total).
There probably isn't much point in running the loop more than three times
for an 8bit fraction, five times for a 16bit fraction, or 7 times for a
24bit fraction (since you'll be past the reallysignificant 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
 Today
 New search...