Solved

float computing algorithm and BCD operation

Posted on 2002-07-17
13
447 Views
Last Modified: 2011-10-03
Anyone know the float computing algorithm, and BCD operation? How should I do add/minus/multiply/divide operation with operands if I can't use the float/double data type.
0
Comment
Question by:99525
  • 9
  • 2
13 Comments
 
LVL 1

Expert Comment

by:acerola
ID: 7167167
Floating point variables have three parts.

1-A bit to specify the sign.
2-digits
3-position of the point.

Like this:
0.25 = + 25 *10^-2
-123.456 = - 1233456 *10^-3
25000 = + 25000 *10^0

The first part stores the sign (+ or -). The second store the digits (25 or 123456 or 25000). The third stores the power of ten the number is multiplied by (-2 or -3 or 0)
0
 
LVL 1

Expert Comment

by:acerola
ID: 7167181
Now the operations. Suppose you only have the data type for signed integer. So you can use two integer variables to store the result of a floating point operation. Something like this:

int digits,point

digits = 123450
point = 3
(that is number 123.456)

A fuction for division (the sintax is incorrect. but that is the idea):

fuction divide (int numerator,denominator) {

const maxprecision = 10;
int digits,point,i;

for (i=0,i<maxprecision,i++) {

  digits = (numerator*10^i) / denominator;
   
  if (digits*denominator = numerator*10^i) {
    /* exact division, no more decimal places */
    break; /* or the correct statement to exit the for loop*/
  }
}
point = i;

return digits,point; /*that is incorrect, you must use some kind of structure/record to output the two values*/
}

Got it?

lets check for numerator = 1 and denominator = 4 (0.25)

i = 0

digits = (numerator*10^i) / denominator;
digits = (1*1) / 4 = 0

if (digits*denominator = numerator*10^i) {
if (0*4=1*1) - false, loop continues

i = 1

digits = (1*10) / 4 = 3 (or 2, i dont know if the language rounds 2.5 to 2 or 3)
if ( (3*4) = 1*10 ) false
in the other case where the language makes 2.5 => 2
if ( (2*4) = 1*10 ) false anyway
loop continues

i = 2

digits = (1*100) / 4 = 25
if (25*4) = 1*100 (true, loop stops)
digits = 25
point = i = 2

so the answer is digits*10^-point = 0.25

if we have too many decimal places, the loop will stop at maxprecision.
0
 
LVL 1

Expert Comment

by:acerola
ID: 7167191
for sum/subtraction you must put both numbers with the same point value and then sum/subtract normally.

I will use the structure:
number.digits
number.point
I don't know how to define it in C. It is probably using a record or someting.

function sumsubtract (structure number1, number2) {

structure result;

if (number1.point > number2.point) {

  number2.digits = number2.digits*10^(number1.point-number2.point);
  number2.point = number1.point;

} elseif (number1.point < number2.point) {

  number1.digits = number1.digits*10^(number2.point-number1.point);
  number1.point = number2.point;

}

result.point = number1.point /*or number2.point, they should be the same by now*/

result.digits = number1.digits-number2.digits;

return result;

}

Now the test. We want to subtract 1.25 - 0.5.

number1.digits = 125
number1.point = 2
nubber2.digits = 5
number2.point = 1

function runs

number1.point > number2.point

  number2.digits = number2.digits*10^(number1.point-number2.point);
  number2.digits = 5 * 10^(2-1) = 50
  number2.point = number1.point
  number2.point = 2

result.point = 2
result.digits = 125-50 = 75

so the answer is 0.75
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 1

Expert Comment

by:acerola
ID: 7167195
finally for multiplication. just multiply the digits and sum the point.

result.point = number1.point + number2.point
result.digits = number1.digits * number2.digits

for example, 6.2 * 0.5.

result.digits = 62 * 5 = 310
result.point = 1 + 1 = 2

the answer is 310*10^-2 = 3.10 = 3.1
0
 
LVL 1

Expert Comment

by:acerola
ID: 7167201
now a function to remove trailing zeroes, like the one on the multiplication:

while ( (result.digits/10)*10 = result.digits ) {

  result.digits = result.digits/10;
  result.point = result.point - 1;

}

testing:

result.digits = 25000
result.point = 4
(number 2.5000 = 2.5)

loop 1

(result.digits/10)*10 = result.digits
(25000/10)*10 = 2500*10 = 25000 (true)
result.digits = 2500
result.point = 3

loop 2

(result.digits/10)*10 = result.digits
(2500/10)*10 = 250*10 = 2500 (true)
result.digits = 250
result.point = 2

loop 3

(result.digits/10)*10 = result.digits
(250/10)*10 = 25*10 = 250 (true)
result.digits = 25
result.point = 1

loop 3

(result.digits/10)*10 = result.digits
(25/10)*10 = 2*10 = 20 (false)
(25/10)*10 = 3*10 = 30 (false anyway if the language rounds up)

loop stops

return:
result.digits = 25
result.point = 1

0
 
LVL 1

Expert Comment

by:acerola
ID: 7167203
sorry, the last loop should be loop 4. copy and paste should be smarter ;)
0
 
LVL 1

Expert Comment

by:acerola
ID: 7167206
You can incorporate the number.point and number.digits into a single biginteger:

suppose you will only handle numbers bigger than 1*10^-99 (0 < point < 99):

biginteger = number.digits*100 + number.point;

the way back

number.digits = biginteger / 100;
number.point = biginteger - number.digits;

the number 1.25 would be stored as 12502 (125 02)
0
 

Author Comment

by:99525
ID: 7168514
I may transplant these code to assembly finally. You know, the assembly may only has ADD/SUB instruction. So we'd better not use integer multiply or divide.
And if the integer data type is 4-bytes long, the max precision is only 10 digits. But the precision I need is far higher than 10 digits. So we can't depend on integer operations.

I have thought of float point variable like this:
sign    /* 1 byte */
point   /* 1 byte, power of 10 */
digits  /* 10 bytes, in BCD format */

Then I have 20-digits precision, and the range is 10^128.

But I don't know how to do BCD multiply and divide, and I also worry about the speed of BCD operation.
All operations in decimal system may save the time, I hope.
0
 
LVL 1

Expert Comment

by:acerola
ID: 7168695
you can implement integer division/multiplication like this:

function multiply(int factor1,factor2) {

int i,result;

result = 0;

for (i=0;i<factor1;i++) {
  result = result + factor2;
}

return result;

}

function divide(int numerator,denominator) {

int i;

i = 0;

while (numerator >= denominator) {
i++;
numerator = numerator - denominator;
}

return i;

}
0
 

Author Comment

by:99525
ID: 7170913
acerola,

The divide() will lose the remainder.
The algorithm is too slow.
0
 
LVL 1

Accepted Solution

by:
acerola earned 100 total points
ID: 7177697
sorry, i used the same name for two different functions.

the last divide() function performs an integer division, the one that should be used inside the first divide() funciton.

the remainder can be calculated like this:

remainder = numerator-integer_divide(numerator,denominator)*denominator

the remainder of 3/2

remainder = 3-integer_divide(3,2)*2
remainder = 3-1*2 = 1

there may be faster ways to calculate that. i just used the definition of the multiplication and division operations. maybe the processor has a instruction to perform those?
0

Featured Post

Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Need help with programming in R stats software 6 36
new car buying (price bargaining) ideas.. 5 99
Triangle - computing angles 3 56
What is sqrt( (x+b/2a)^2) 35 76
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

828 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question