X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
Date: Sun, 13 Sep 2015 23:03:59 -0400
Message-Id: <201509140303.t8E33xJk014460@envy.delorie.com>
From: DJ Delorie <dj AT delorie DOT com>
To: geda-user AT delorie DOT com
In-reply-to: <F19A9B9C-C544-4B76-AF8B-EA981B6BA952@noqsi.com> (message from
	John Doty on Sun, 13 Sep 2015 20:03:01 -0600)
Subject: Re: [geda-user] Apollon
References: <20150913140631 DOT 1da1b78d AT jive DOT levalinux DOT org> <201509131529 DOT t8DFTUVS022118 AT envy DOT delorie DOT com> <B0EDB76E-F0DE-4A05-97FC-A405489ACA5A AT noqsi DOT com> <201509131824 DOT t8DIOCBc028428 AT envy DOT delorie DOT com> <B03281A2-123E-4F54-B3AA-CB8CCB09F1B1 AT noqsi DOT com> <201509132031 DOT t8DKVH0P000824 AT envy DOT delorie DOT com> <AB671235-711B-4ECD-9015-515A5BFC6955 AT noqsi DOT com> <201509132148 DOT t8DLmxI6003481 AT envy DOT delorie DOT com> <D8151856-4B93-4826-A80F-E00578A2E93C AT noqsi DOT com> <201509132300 DOT t8DN0sE6006134 AT envy DOT delorie DOT com> <7EF3E562-BC7F-4853-B90A-29726FDFEBF6 AT noqsi DOT com> <201509132319 DOT t8DNJBjC006829 AT envy DOT delorie DOT com> <40057B48-2FD4-4A37-A01E-9344F6C33ADF AT noqsi DOT com> <201509140138 DOT t8E1cqY1011780 AT envy DOT delorie DOT com> <F19A9B9C-C544-4B76-AF8B-EA981B6BA952 AT noqsi DOT com>
Reply-To: geda-user AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: geda-user AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk


[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).