Archive for May 24th, 2017

Arduino vs. Significant Figures: Preliminary 64-bit Fixed Point Exercise

Although it’s not advertised, the Arduino / AVR compiler mostly does the right thing with long long = uint64_t variables: add & subtract work fine, but multiplication & division discard anything that doesn’t fit into 64 bits. Fitting a 32 bit integer and a 32 bit fraction into such a thing should eliminate (most) problems with significant figures.

The general idea is to set up a struct giving access to the two 32 bit halves for direct manipulation, then overlay / union them with a single 64 bit integer for arithmetic purposes:

struct ll_s {
  uint32_t low;
  uint32_t high;

union ll_u {
  uint64_t ll_64;
  struct ll_s ll_32;

Of course, the integer part still falls one bit shy of holding 2³². At the cost of one bit’s worth of resolution, you can still compute 2³² / 125×10⁶ by pre-dividing each quantity by 2:

2^63 = [80000000 00000000]
2^63 / 125/2 M = [00000022 5c17d04d]

The low-order digit should be 0xe, not 0xd, but I think that’s survivable.

Unfortunately, printf doesn’t handle 64 bit quantities, necessitating some awkward conversion routines. “Printing” to a string seems the least awful method, as I’ll eventually squirt the strings to a display, not send them to the serial port:

void PrintFractionLL(char *pBuffer,uint64_t *pLL) {
  uint64_t Fraction;

  Fraction = (uint32_t)*pLL;                      // copy 32 fraction bits, high order = 0
  Fraction *= ONEGIG;                             // times 10^9 for conversion
  Fraction >>= 32;                                // align integer part in low long
  sprintf(pBuffer,"%09lu",(uint32_t)Fraction);    // convert low long to decimal

void PrintIntegerLL(char *pBuffer,uint64_t *pLL) {
  sprintf(pBuffer,"%lu",*((uint32_t *)pLL+1));

void PrintDecimalLL(char *pBuffer,uint64_t *pLL) {
  pBuffer += strlen(pBuffer);       // pointer to end of integer part
  *pBuffer++ = '.';                 // drop in the decimal point, tick pointer

The result seems nearly indistinguishable from the Right Answer:

Integer:  34
Fraction: 359738367
Decimal: 34.359738367

This whole mess has a bunch of rough edges, but it looks promising. The code coalesced while fiddling around, so the union notation didn’t get much love at first.

The Arduino source code as a GitHub Gist: