[time-nuts] 32768 Hz from 10 MHz
Hal Murray
hmurray at megapathdsl.net
Fri Feb 3 03:16:03 UTC 2012
> It's possible to use Bresenham with two integers 10,000,000 and 32,768 but I
> found no way to perform all the 24-bit calculations on an 8-bit PIC quick
> enough. Removing the GCD often helps but in this case the accumulator
> remains 3-bytes wide.
> To generate 32 kHz you have to toggle a pin and calculate if the next toggle
> must be 38 or 39 instructions in the future; all the math must occur within
> 37 instructions. That's why I came up with the binary leap year kind of
> algorithm; it's as close to math-less as you can get.
You missed the simple way. Table lookup. :)
The table is only 256 slots long.
That's toggling between 305 and 306 cycles. If your CPU uses N clocks per
instruction, multiply the table size by N.
In hindsight, I'm embarrassed that I didn't see this much sooner.
10,000,000 is 10^7 or 2^7 * 2^5.
32,768 is 2^15. So we need a factor of 2^8 to get back to where we started.
---------
My early introduction to the advantages of table lookup was using Fortran on
an IBM 7094. How do you calculate factorials quickly? The table is only
30-50 slots. Anything bigger generates a floating point overflow.
---------
Here is my hack python code that I had to write to see what's going on:
#!/usr/bin/python2
# Given 10 MHz, target is 32 KHz
# What sequence of DDS steps is required?
# How long is the sequence before it repeats.
import sys
Target = 32768
Input = 10000000
table = {}
X = 0
K = 0
oldI = 0
for I in range(0,Input):
X += Target
if X >= Input:
X -= Input
print "%5d %7d %5d %3d" % (K, I, X, I-oldI)
if table.has_key(X):
print "Found in table:", X
sys.exit(0)
table[X] = K
K += 1
oldI = I
--
These are my opinions, not necessarily my employer's. I hate spam.
More information about the time-nuts
mailing list