Landing : Athabascau University
  • Blogs
  • Implementing Sine and Cosine Without Floats

Implementing Sine and Cosine Without Floats

Implementing Sine and Cosine Without Floats

The Arduino platform doesn't enjoy working with floating point ("FP") numbers. It's slower than you'd think it aught to be. The core of the issue is that the microprocessors the Arduino platform is designed to run on do not have an integrated floating point unit (FPU) or other similarly dedicated hardware. They only have the built-in hardware to perform integer math, an arithmetic logic unit (ALU). Arduinos perform floating point math in software. Although it depends on which compiler (and compiler options) you are using and which libraries are being linked, it's probably IEEE 754 single-precision binary floating-point format ("binary32")[Note]. While the extra code space is concerning, those concerns are present when linking any extra libraries. Uniquely pertaining to the use of FP operations is their slow speed relative to the analogous integer operations. Using an ALU for FPU operations means converting the FP numbers' signs, significands, and exponents into integers, performing operations on each integer, then converting back to FP. The same operation may be performed in a single cycle using integers and the ALU. The lesson here is to avoid floating point numbers on Arduinos.

I need to do some geometry at run time to figure out how my gizmo is positioned, specifically the sin(x) and cos(x) functions. The math.h header normally implements these by linking a floating point library. With the above in mind, I set out to implement sin(x) and cos(x) using a lookup table of integer values.

Sine and cosine functions normally output values ranging from -1 to 1. Integer precision can be increased by scaling these values up. Any script that makes use of these functions will likely perform other math operations on them, such as multiplying and dividing, which puts practical limits on the scaling factor. For example, a result value of type int from multiplying the output scaled by a factor of 1000 would risk overflow if multiplied by a number greater than 32. Reducing the scaling factor reduces precision. I suggest setting the scaling factor to achieve the minimum required precision, then choosing the variable storage types. I chose a scale factor of 1000 and was sure to employ type long variables, which allows the use of multiplicands up to 2,147,483, giving me 1 mm precision with measurements on the order of 1000 mm.

My uses required only integer angle values, and the 360-degree sinusoid and cosinusoid waveforms can be mapped to a single quadrant of the sine wave, which means my lookup table only needed 91 values. Excel was used to calculate the scaled and nearest-rounded values of the first quadrant of sin(x), and to format it as a C++ array. It was stored in flash using the PROGMEM macro.

The library is programmed as a namespace instead of a class with static members as an experiment to gain experience using namespaces. It could easily be converted to the latter. Code is linked below (git develop branch, for now) with the bulk of it transcribed.

IntegerGeometry.h

/*
* IntegerGeometry.h
*
* Created on: Oct 31, 2017
* Author: Tyler Lucas
*/
#ifndef IntegerGeometry_h
#define IntegerGeomtry_h
#include "inttypes.h"
#include "avr/pgmspace.h"
namespace IntegerGeometry
{
int sin1000(int angle); // returns 1000*sin(angle)
int cos1000(int angle); // returns 1000*cos(angle)
    // 1000 times sin(angle) from 0 to 90
const static uint16_t sin1000table[/*91*/] PROGMEM =
{
0,
17,
35,
52,
...
999,
999,
1000,
1000
};
}
#endif // IntegerGeometry_h

IntegerGeometry.cpp

/*
* IntegerGeometry.cpp
*
* Created on: Oct 31, 2017
* Author: Tyler Lucas
*
* SOHCAHTOA
*/
#include "IntegerGeometry.h"
#include <Arduino.h>
namespace IntegerGeometry
{
int sin1000(int angle)
{
// map angle to 1st quadrant
int reducedAngle = ((angle % 360) + 360) % 360;
if (reducedAngle >= 270) // quad IV : sin(x) = -sin(-x)
return -sin1000(-reducedAngle);
if (reducedAngle >= 180) // quad III : sin(x) = -sin(pi+x)
return -sin1000(180 + reducedAngle);
if (reducedAngle > 90) // quad II : sin(x) = -sin(pi-x)
return sin1000(180 - reducedAngle);
        return pgm_read_word(&IntegerGeometry::sin1000table[reducedAngle]);
}
    int cos1000(int angle)
{
return sin1000(angle + 90);
}
 
}

Here's an example of its use in RobotArmMember.cpp (likely soon to be moved to PositionVector.cpp):

int BoomPositionVector::getRadius(int angle)
{
long radiusL = this->length;
radiusL *= IntegerGeometry::cos1000(angle);
radiusL /= 1000L;
return (int)radiusL;
}

Note that the multiplication takes place before scaling the result down (division). (Can you figure out why this may be important?)

After preliminary testing (output verification with Excel) and a few weeks of use, it seems to work well. The use of a namespace instead of a class with static members appears to be without complications, though this example does little to push the boundaries of either use case.


Note: If using avr-gcc with floating point numbers, especially with the AVR8 family, you must link libm.a. It is written especially for AVR microcontrollers. The Arduino IDE may do this automatically.

Comments

  • Thanks Tyler. Floating point numbers are a problem in computer languages. Inaccurate calculations. When I was in the math program, we rounded numbers to the fifth decimal place.

    I wonder why computer languages have such inaccuracy while calculators are accurate.  Might it have something to do with binary calculations instead of base 10?

    Thanks Tyler for answering Ebony's and my questions on the circuit board.  Much appreciated. 

    Susanne Cardwell November 15, 2017 - 11:14am

  • In fact, calculators have the same floating point limitations as computers, which makes sense, because calculators are simple computers. Try adding 0.1 to 1,000,000,000 and you'll get 1,000,000,000, not 1,000,000,000.1 (unless your calculator uses 64-bit numbers, which can precisely display up to about 18 digits); or try cos(0.00001) and you'll get 1, not 0.99999999995. They seem to be more accurate because they can limit their outputs. It's worth noting that having a hardware FPU does not guarantee greater precision than using a floating point library, as Arduinos do. The highest precision operations are actually done in software. Take a look at Java's BigDecimal for a great example and explanation. 

    You are correct in thinking that there could be a loss of precision when working with base-10 numbers in a binary system. The IEEE 754 standard defines 5 binary and 3 decimal floating point formats, where the latter can store decimal numbers exactly. Since the libm.a floating point library (Arduino/avr-gcc, etc.) likely uses the "binary32" format, it does not represent decimal number exactly, and is accurate to about 7 digits. Any format is no more precise than the value of the least significant bit ("LSB") (big-endian only; MSB value for little-endien) in the significand. For binary32 numbers, this is 2^-23 times the exponent, which is related to its magnitude. A quick search found a library that may be able to introduce the decimal32/64/128 formats to an Arduino platform, [here]: GitHub.com/toddtreece/esp8266-Arduino/.../decimal (it is for the ESP8266, a 32-bit Xtensa system, however, so it wouldn't work out of the box, if at all, on the 8-bit AVR/etc. systems we are using).

    Tyler Lucas November 15, 2017 - 1:20pm

  • Tyler,

    This is a great write up, good explanation and documentation. Thank you. If I have time I’m going to refactor this into my project. I just spent the last while programming the basics of dead reckoning for a two-wheeled, differential steering rover and of course the core of it involved the use of sine and cosine and lots of floats. I’ve read several articles admonishing the use of floats on micro controllers. It’s understandable as you’ve noted due to their limited memory, processing power, and lack of floating point unit. I plowed ahead anyway and with no noticeable performance problems yet. The encoder interrupts are firing about 750/s and I’m calculating coordinates and orientation 10/s. My only concern would be sacrificing precision. Dead-reckoning is known for error accumulation anyway.

    peterde December 11, 2017 - 8:30pm

  • Glad you could use it!

    You can add another factor of ten or two to increase precision. (The above code is the float output multiplied by 1000.) Would just need to be a bit more careful about overflow when doing math with the output, especially multiplication. E.g. 'sinx' output may be as high as +10000, so don't multiply by more than 32 if using int, ~200000 if using long. Really, manually keeping track of these ranges is a pain in the ass, especially when debugging it (without a debugger/JTAG/etc), so if your application works with floats, I'd just use them... until it doesn't work. :)

    Also, IntegerGeometry.h and IntegerGeometry.cpp were promoted to the master branch after a bit more review.

    Tyler Lucas December 11, 2017 - 8:58pm

These comments are moderated. Your comment will not be visible unless accepted by the content owner.

Only simple HTML formatting is allowed and any hyperlinks will be stripped away. If you need to include a URL then please simply type it so that users can copy and paste it if needed.

(Required)

(Required)