Mail Archives: geda-user/2015/09/13/23:04:37
[FYI I'm not arguing this, more like exploring an interesting
mathematical realm]
> > I imagine integer overflow might be a non-trivial problem to
> > solve.
>
> Not one you need to worry about in a language that supports
> rationals. I use rationals in Mathematica all the time: floating
> point is poison to complicated algebra. The techniques are well know
> and efficient, although not as efficient as floating point hardware.
That just defers the problem to the language. The more the language
hides in "the implementation", the more "the implementation" needs to
do. I wouldn't want to program a 3D video game in Mathematica, the
FPS would be horrible. Really fast games might avoid floating point
completely, relying on fixed point instead, when even marginal speed
improvements matter.
> > But if the whole point is to defer imprecise operations, what is the
> > advantage of this over just storing the angles as degrees and doing
> > the math on the fly?
>
> The problem is that you'll accumulate error when you have both
> rotations and translations.
I think we have three cases of where imprecision affects us:
1. Storing a user-specified value in an imprecise way (i.e. storing
millimeters in units of 1E-5 inches ;)
2. Accumulating error when imprecise calculations are stored, and
later reused iteratively (i.e. rotating footprints by changing the
internal coordinates, over and over again)
3. Imprecision when converting stored data to a temporary useful
representation (i.e. scaling data to fit on the screen)
(pcb manages to break all of these wrt rotations)
Storing angles as triplets lets you avoid #2 at the expense of #1.
Storing angles as angles lets you avoid #1 and #2 at the expense of
making #3 slower.
My idea was like this example: consider rotated subsets in gschem.
Each instantiated symbol has a "X,Y,A" triplet that says where it
shows up on the screen. Now consider these can nest (doesn't make
sense in reality, but just imagine).
You end up with data like this:
(part N [500,450,60] (this is X,Y,A)
(subpart M [40,500,35]
(subpart L [-50,100,25]
(text [0,0,0] "foo")
)
)
)
The location of text "foo" is "known" to this data, using only
integers, without imprecision. If you want to rotate part M you just
change that 35 to something else. We store the values used for the
transformations, not the transformations themselves. (But we can't
use this data as-is for "real" things since "real" things need the
transformations applied and reduced to "normal" number formats that
other libraries can use.)
Thus we meet #1 (all data is stored accurately) and #2 (we can apply
futher transformations without loss of precision) at the expense of
#3, which you have to do anyway to get a usable coordinate (whether
explicitly or as part of the internals of the language).
There is still some imprecision as you *apply* these transforms, when
you need the transformed coordinates as "usable" ones, like for a
postscript file or GPU operation which won't know about the language's
or application's internal representation. The trick is to keep the
performance cost of these transient operations low in
performance-sensitive code (pcb's main drawing loop can be pretty
expensive, for example) ("performance" is the reason we pre-rotate
footprints)
> > Just speed? /me wonders what the speed difference would be, if
> > you include all the division ops you've created a need for,
>
> Huh? Division of rationals is easy.
Per operation, sure, but you're doing a *lot* of division. I'm
talking about the final step when you need to do a real floating point
division to turn the in-language rational into a floating point value
other apps can use. Plus the cost of every other operation is doubled
since both numerator and denominator are affected.
I don't know if it's non-trivial or not, just considering it.
> > plus algorithms to find pythagorean triples as
> > needed,
>
> Have a table. Or use Euclid's formula.
The user wants a rotation of 28.75 degrees. What's the optimal way to
find a triple? How "precise" should the triple be? How long do we
spend searching for a triple that might be more precise? How big
should the table be?
I can see why using sin(x) and cos(x) is so popular - it's good
enough, reasonably fast, and easy to code.
> > plus overflow protection of a sort, etc.
>
> Taken care of automatically if you choose a suitable language.
That just moves the problem elsewhere. I'm thinking of performance
here. Typically, the less you have to do in the language, the more
you have to do *as* the language.
Imagine drawing a spinning item, continuously rotating by 5 degrees.
That means you're multiplying N/D by A/B, and N and D grow without
bounds unless something acts to reduce them. What if A/B are
relatively prime? N/D will never be reducible and will eventually hit
limits (or become computationally expensive as the format
grows/changes to adapt).
- Raw text -