Minsky Circle Algorithm. Generate sin and cos fast with only add, sub and shift.



  • Heater.Heater. Posts: 21,213
    edited 2015-08-30 - 02:33:56
    More nerding out with numbers:

    This may be obvious but I had to scratch my head a bit over it. A radius of 4096 and a shift of 10 has to have 20 sides because:

    After the shift we only have 2 bits left, so we can only move the current position by 0, 2, or 3 in x or y directions. We will ignore the negative directions.That means the possible gradients of the line segments can only be:
    0/0   1/0   2/0   3/0 
    0/1   1/1   2/1   3/1 
    0/2   1/2   2/2   3/2 
    0/3   1/3   2/3   3/3
    Which is:
    NaN   ∞     ∞     ∞
    0     1     2     3
    0     0.5   1     1.5
    0     0.33  0.66  1
    We can remove duplicates and "Not A Number" and we have these possible gradients:
    0     1     2     3
          0.5         1.5
          0.33  0.66   
    We can remove remove things that are nice multiples if a half: 1/2, 2/2 and 2. Leaving:
    0                 3
          0.33  0.66
    The five different gradients 0, 0.33, 0.66, 1.5 and 3 are enough to get us a quarter of the way around the circle with equal length line segments.

    Ergo we have to get a 20 sided polygon.

    By a similar argument we see that a radius of 4096 has three bits to make adjustments in direction, 64 possible directions. 14 of them are used to get us around a quadrant for a 56 sided polygon. The sides are not all of equal length in this case.
  • Mark_T,
    I think this is now a footnote in the textbooks, Bressenhams (ie DDA) is a more general and flexible approach and doesn't risk accumulating errors.
    I just noticed a little detail here. Your statement hints that there is a risk of accumulating errors with the Minsky Circle algorithm. Actually part of it's magic is that it is stable. You can run around that circle forever and it won't accumulate errors.
  • BeanBean Posts: 7,997
    edited 2016-01-03 - 04:08:56
    The Minsky circle algorithm is a modification of cordic.

    If you use the temporary variable (which you should NOT do for Minsky) it IS cordic and the radius will grow by COS(step) per step. By not using the temporary variable causes the growth to be signed so over the whole circle it cancels.

    The number of steps required for a whole circle is (2*PI)/ATAN(step) (assuming radians).

    COS(step) of small steps is much smaller than larger steps. For example COS(step/32)*32 is much smaller than COS(step), smaller steps cause less gain even though there are more steps. This makes larger steps have much more gain which makes them more oblong.

Sign In or Register to comment.