Division bug in \doMPconcat (supp-pdf.tex)

* Division bug in \doMPconcat (supp-pdf.tex)
@ 2004-12-14 22:56 Dan Luecking
  2004-12-15  9:39 ` Hans Hagen
  0 siblings, 1 reply; 2+ messages in thread
From: Dan Luecking @ 2004-12-14 22:56 UTC (permalink / raw)

I encountered a problem with supp-pdf when I tried to rewrite Knuths
"dangerous bend" as a MetaPost figure. Very little change was required to
get a good picture, but the "reverse dangerous bend" (obtained by merely
reflecting the currentpicture" produced a quite grotesquely distorted
picture. I tracked this down to the method used to divide by the determinant
of the scaling matrix in \doMPconcat.

The division code is the following:
    \ifdim\dimen16=\onepoint \else
      \ifdim\dimen16>\MPconcatfactor \onepoint \relax
        \doMPreducedimen16
        \divide \dimen18 \dimen16 \doMPexpanddimen18
        \divide \dimen12 \dimen16 \doMPexpanddimen12
      \else
        \divide \dimen18 \dimen16 \doMPexpanddimen18 \doMPexpanddimen18
        \divide \dimen12 \dimen16 \doMPexpanddimen12 \doMPexpanddimen12
      \fi
    \fi

In the reverse dangerous bend symbol \dimen16 (the determinant in question)
is -1 and \MPconcatfactor is 256, so the else part is taken. The division is
integer division, so the accuracy (after the two \doMPexpanddimen) is +/-
1pt. This turns values like the following:

     58.11118 -61.6534 7.53143 -11.0737 7.52731 -11.06958 c
     4.48691 -8.02919 1.99252 -4.2878 1.99252 0 c
     1.99252 4.2878 4.48691 8.02919 7.52731 11.06958 c
     7.53143 11.0737 58.11118 61.6534 58.1153 61.65752 c

into (actual code in from uncompressed pdf output):

     58.0 -61.0 7.0 -11.0 7.0 -11.0 c
     4.0 -8.0 1.0 -4.0 1.0 0.0 c
     1.0 4.0 4.0 8.0 7.0 11.0 c
     7.0 11.0 58.0 61.0 58.0 61.0 c

Similar problems occur if the figure is rotated. (Theoretically, the 
determinant is 1, but with only 5 decimal accuracy, the same branch is
taken.)

Also the \if tests above don't take the sign of \dimen16 into account.

There is a lesser problem with multiplication when numbers are less than 
around 1pt. The pre-division by 256 (\doMPreducedimen) reduce accuracy to
less than 3 significant decimal digits (i.e., 8 binary digits).

I have written some modifications for supp-pdf that avoid all of these.
No pre-division is used because multiplication is accomplished by something
like
    \dimen16 = \withoutpt\the\dimen0 \dimen6
and division is accomplished by computing 1/D and multiplying.
Since the numerator (1) is fixed, this one division can be arranged for
maximum accuracy. I do this by halving D until it is less than 1pt,
keeping track of the number of halvings required. Then I divide 2^30
by D, then double the result 2 fewer times than than D was halved. This
guarantees at least 14 binary places accuracy, or the number of places in
D, whichever is smaller.

My speed tests show that the resulting code is as fast or slightly faster
than the current code. Further efficiency could be gained by performing
the calculation of D outside the loop of calls to \doMPconcat (I have not
done this yet).

The current state of my code can be found at
   http://comp.uark.edu/~luecking/tex/supp-pdf.mod
and a stripped down version of the reverse dangerous bend code that shows the
problem is
   http://comp.uark.edu/~luecking/tex/rdbend.mp

Comments are welcome. I hope at least the division can be made more accurate
in the context distribution.

Dan Luecking

Daniel H. Luecking
Department of Mathematical Sciences
University of Arkansas 

^ permalink raw reply	[flat|nested] 2+ messages in thread