Division (binary restoring method)

[Tim Kleinert]

cheerios,

As I'm moving on from the G2 platform, I've decided to skim through my folders containing tons of doodles and experiments and publish the ones that actually do something that might be useful.

As we all know, the G2 sadly lacks a dedicated division module. The cheapest and simplest way to patch it is via the Goldschmidt convergence algorithm, which requires merely two mixers and a multiplier in a feedback arrangement. It's really neat and produces full precision results. (IIRC, it's published here somewhere.)

But the Goldschmidt algorithm unfortunately has a few drawbacks. Being a convergence method, the calculation time is variable and highly dependent on the numerical size of numerator and denominator. Also, there is no built-in flagging of the final result. These issues can make it unsuitable for patches that require predictability of computation time and availability of the result.

The following patch is a G2 implementation of an algorithm harking back to the early days of computing, also known as the binary restoring division algorithm It is obviously more expensive, but has some big advantages in that it has a predictable calculation time, flags the result and also is very customizable.

The calculation time is directly related to the numeric resolution of the result. Eg., a 8 bit precision quotient requires 8 iterations, or 8 samples calculation time. In this way one can trade off precision against speed as one sees fit. (Just to clarify: the bit precision only pertains the resulting quotient. Numerator and denominator can be positive full-scale.)

The presented patch calculates the quotient to the full numerical resolution and thus updates itself every 23 samples. (The sign bit is not dealt with, the circuit only accepts positive numbers.) It also emits an one-sample spike trigger every time a new result has been calculated. It can be easily modified to not continuously auto-update by disconnecting the feedbacked comparator flag at the top, so the calculation can be externally triggered (with an one-sample spike). Also as stated, the calculation precision/speed can be easily modified by plugging in a correctly tuned constant into the empty comparator input. (Otherwise the circuit always calculates through the whole binary headroom down to zero.)

cheers,
t

EDIT: DSP usage of this circuit: 6.3% cycles, 10.2% memory

---

RestoDivision_TK.pch2
Description:	predictable and customizable division using the binary restoring algorithm	Download (listen)
Filename:	RestoDivision_TK.pch2
Filesize:	1.8 KB
Downloaded:	3762 Time(s)

---

[Tim Kleinert]

Addendum:

Another interesting property of the binary restoring method is that it can actually be implemented in real-time if you can sacrifice the DSP usage.

It's not at all taxing cycles-wise, but does eat up the zero-page memory fast.

Here's an example of a real-time 8 bit precision division. Basically an unravelling of the iterative loop. (we called that "speedcode" in the old C64 days ...)

EDIT: DSP usage of this circuit: 3.3% cycles (at control rate), 19.5% memory

---

RealtimeDivis_TK.pch2
Description:	real-time division with 8 bit resolution, using a direct form of the binary restoring method	Download (listen)
Filename:	RealtimeDivis_TK.pch2
Filesize:	2.28 KB
Downloaded:	3715 Time(s)

---