gointegersubtractionarithmetic-expressionstinygo

Minimize integer round-off error in PLL frequency calculation

On a particular STM32 microcontroller, the system clock is driven by a PLL whose frequency F is given by the following formula:

F := (S/M * (N + K/8192)) / P

S is the PLL input source frequency (1 - 64000000, or 64 MHz).

The other factors M, N, K, and P are the parameters the user can modify to calibrate the frequency. Judging by the bitmasks in the SDK I'm using, the value of each can be limited to a maximum of M < 64, N < 512, K < 8192, and P < 128.

Unfortunately, my target firmware does not have FPU support, so floating-point arithmetic is out. Instead, I need to compute F using integer-only arithmetic.

I have tried to rearrange the given formula with 3 goals in mind:

  1. Expand and distribute all multiplication factors
  2. Minimize the number of factors in each denominator
  3. Minimize the total number of divisions performed
  4. If two expressions have the same number of divisions, choose the one whose denominators have the least maximum (identified in earlier paragraph)

However, each of my attempts to expand and rearrange the expression all produce errors greater than the original formula as it was first expressed verbatim.

To test out different arrangements of the formula and compare error, I've written a small Go program you can run online here.

Is it possible to improve this formula so that error is minimized when using integer arithmetic? Also are any of my goals listed above incorrect or useless?

Solution

  • Looking at the answer by @StevenPerry, I realized the majority of error is introduced by the limited precision we have to represent K/8192. This error then gets propagated into the other factors and dividends.

    Postponing that division, however, often results in integer overflow before its ever reached. Thus, the solution I've found unfortunately depends on widening these operands to 64-bit.

    The result is of the same form as the other answer, but it must be emphasized that widening the operands to 64-bit is essential. In Go source code, this looks like:

    var S, N, M, P, K uint32
...
F := uint32(uint64(S) * uint64(8192*N+K) / uint64(8192*M*P))

    To see the accuracy of all three of these expressions, run the code yourself on the Go Playground.