go_away

Author Topic: Integer floating point maths  (Read 1127 times)

0 Members and 1 Guest are viewing this topic.

Offline WebbotTopic starter

  • Expert Roboticist
  • Supreme Robot
  • *****
  • Posts: 2,136
  • Helpful? 109
Integer floating point maths
« on: March 21, 2009, 01:00:54 PM »
Am posting this rather than doing a tutorial as its fairly small.

You may have found that using floating maths brings in a large library and makes your code much bigger if you have any floating point stuff anywhere such as 'return (x * 0.8333)'.
A common mistake is not to tell the linker to use 'libm.a' (ie by using -lm in the build) in which case your code gets even bigger. However, even the extra 2 to 3k can be a chore for small devices like ATMega8. So I got to wondering how else to do it. Fractions.

So I have written a small program to convert a real number into a single fraction, or a series of fractions. The single fraction may be something like '2003/3127'. Large numbers like these can be a pain as you have to choose large enough variables to store the larger numbers. But sometimes its useful if you get an answer like '6/7'.
The second answer the program gives is a series of fractions where the numerator (on top is always '1') ie 1/2 + 1/258 + 1/1301.  This is good because each division will end up with a smaller number than the one you are multiplying by. ie a 32 bit number divided by another number can always be stored in a 32 bit number.

Also the number fractions required depends on the accuracy of the answer you need. ie if you are only working with an 8 bit number then the (1/258 and 1/1301) parts aren't required as they will always be 0. For a 16 bit number you dont need the 1/1301 but for a 32 bit number then you need all of them.


So lets take a real example. Say we want to multiply a 16 bit number by 'pi' which is '3.14159....'. Well my program says this can be done using either:

36853866/260280919  (which isn't very usable coz the numbers are so big),   or 3/1 + 1/8 + 1/61 + 1/5020 which is much better.
So to find 'foo * PI' then the answer is '3*foo' + 'foo/8' + 'foo/61' + 'foo/5020'

Obviously if you need to use functions like 'sin,cos, tan, pow' then you will probably need the maths lib anyway. But my approach is quite useful when scaling raw sensor data into meaning units like cm or inches.

So here's the hastily put together Java app that converts the real number into fractions. Obviously you wouldn't put this on the microcontroller you would just use it to change a real number constant into a fraction list for your mcu code.

Code: [Select]
import java.util.ArrayList;
import java.util.Collection;

/**
 * $Id$
 *
 * Revision History
 * ================
 * $Log$
 * ===========
 *
 */

/**
 * @author Clive Webster
 *
 * Convert a floating point number into a fraction ie x/y
 * and also into a sequence of unit fractions ie 1/z1 + 1/z2 ...
 *
 */
public class Fractions {
    // Find greatest common divisor
    static public long gcd(long a, long b){
    long max = Math.max(a, b);
    long min = Math.min(a, b);
   
    long whole = max / min;
    long rem = max - (min * whole);
   
    long rtn;
   
    if(rem != 0){
    rtn = gcd(min,rem);
    }else{
    rtn=min;
    }
    return rtn;
    }
   
   
class Fraction{
long numerator;
long denominator;

public Fraction(long numerator, long denominator) {
super();
this.numerator = numerator;
this.denominator = denominator;
simplify();
}

public void simplify(){
if(numerator!=0 && denominator!=0){
long gcd = gcd(numerator,denominator);
if(gcd!=1){
numerator/=gcd;
denominator/=gcd;
}
}
}

public double toDouble(){
return (double)numerator / (double)denominator;
}

@Override
public String toString() {
return String.valueOf(numerator)+"/"+String.valueOf(denominator);
}

FractionList fibonacci(double MaxError){
FractionList rtn = new FractionList();
if(numerator>denominator){
long whole = numerator/denominator;
rtn.add(new Fraction(whole,1));
numerator = numerator % denominator;
}

long yx = (long)Math.floor(denominator/numerator);
if(denominator % numerator > 0){
yx++;
}

rtn.add(new Fraction(1, yx));

Fraction remainder = new Fraction( numerator - (denominator % numerator), yx * denominator);
if(remainder.toDouble() > MaxError){
rtn.addAll(remainder.fibonacci(MaxError));
}
return rtn;
}

/**
* @param amount
* @return
*/
public long multiply(long amount) {
long d = denominator;
long n = (numerator*amount)+(d>>1); // round
return n/d;
}
}

    class FractionList extends ArrayList<Fraction>{

public FractionList() {
super();
}

public FractionList(Collection<? extends Fraction> c) {
super(c);
}

public FractionList(int initialCapacity) {
super(initialCapacity);
}

public long multiply(long amount){
long rtn = 0;

for(Fraction el : this ){
rtn += el.multiply(amount);
}
return rtn;
}

@Override
public String toString() {
StringBuffer buf = new StringBuffer();
boolean first=true;
for(Fraction el : this ){
if(!first){
buf.append(" + ");
}else{
first = false;
}
buf.append(el.toString());
}
return buf.toString();
}
   
    }
   

/**
* @param args
*/
public static void main(String[] args) {
double val = Math.PI; // Set your required value here
Fractions prog = new Fractions();

System.out.println("Number:"+val);

Fraction f;
FractionList l;

f = prog.makeFraction(val,1.0/Math.pow(2, 16));
l=f.fibonacci(1.0/Math.pow(2, 16));
System.out.println("16 bit Fraction:"+f.toString());
System.out.println("16 bit Fibonacci Series:"+l);
System.out.println();

f = prog.makeFraction(val,1.0/Math.pow(2, 8));
l=f.fibonacci(1.0/Math.pow(2, 8));
System.out.println("8 bit Fraction:"+f.toString());
System.out.println("8 bit Fibonacci Series:"+l);
System.out.println();

}

private final int MaxTerms = 15; //Limit to prevent infinite loops
private final double MinDivisor = 0.00001; //Limit to prevent divide by zero
/**
* @param v
* @return
*/
private Fraction makeFraction(double v,double MaxError) {
double f = v;
Fraction f1 = new Fraction(1,0);
Fraction f2 = new Fraction(0,1);
long a=0;
long n=0,d=0;

for(int i=0; i<MaxTerms;i++){
a = (long)Math.floor(f);
f -= a;

n = f1.numerator * a + f2.numerator;
d = f1.denominator * a + f2.denominator;

f2.numerator = f1.numerator;
f2.denominator = f1.denominator;

f1.numerator = n;
f1.denominator = d;

if(f < MinDivisor){
break;
}
if( Math.abs(v - n / d) < MaxError){
break;
}
f = 1 / f;

}

Fraction rtn = f1;
return rtn;
}

}



Webbot Home: http://webbot.org.uk/
WebbotLib online docs: http://webbot.org.uk/WebbotLibDocs
If your in the neighbourhood: http://www.hovinghamspa.co.uk

 


Get Your Ad Here