Personally, I would like the property that <. on gaussian (or complex) integers is an identity function. So this seems promising.
But what does this do to the euclidean algorithm? (Are there examples where it breaks? If so, what has to happen for it to work with gaussian integers?) Thanks, -- Raul On Mon, Oct 14, 2019 at 4:42 PM Marshall Lochbaum <[email protected]> wrote: > > Here's a description of my floor model and how I arrived at it (after > discussion with colleagues at Dyalog). There's some code at the bottom > to generate pictures, which will probably help when reading. It's not > quite identical to the proposal for Dyalog APL: Dyalog's real floor uses > absolute tolerance around 0, so I've dropped some 1>.'s. > > My primary design goals for a tolerant complex floor were that: > > - It should be identical to the real tolerant floor on real numbers (in > my mind, anything else is a bug). > - If c = z for a complex integer c, then c = <.z . > - The floor should be relatively stable around other rational numbers, > that is, a small-denominator rational number is never too close to a > boundary. This means residue | is stable on small enough complex > integers. > > Based on these criteria I developed the following definition: > > Given an argument z and comparison tolerance ct, > - If z tolerantly equal to the nearest integer, its floor is that integer. > - Otherwise, let f =. <.!.0&.+. z and consider 'p q' =. +.f-~z+0j1*ct*|z . > - If 1 >!.0 p+q, return f. > - Otherwise, if p <!.0 q, return f+0j1. > - Otherwise, return f+1. > > This definition differs from intolerant floor only in the first step and > the added factor 0j1*ct*|z used to define p and q. This factor shifts > the rectangles of numbers with the same floor downward. > > A coefficient of 0j1 is used rather than something like *1j1 in order to > displace every edge of the rectangle and avoid rational points. At a > c+0.5j0.5 for a complex integer c, the boundaries meet in a reverse y > shape. They should be shifted approximately southwest to respect integer > points; shifting purely south does this while leaving c+0.5j0.5 distant > from any individual boundary. It also has the desirable property that > any number which is tolerantly equal to a real number will have a real > floor. A sketch of a proof is that if z = x for a real x, the imaginary > part of z is at least -ct*|z (well, not quite. That's the hard part). > The imaginary part of z+0j1*ct*|z is then nonnegative; if it was > originally negative then q>1 . But p cannot be greater than one, so the > floor of z is f+0j1, a real number. > > The added factor z+0j1*ct*|z is based on z rather than f because this > avoids glitches around integers. It causes the boundaries as a whole to > curve; each rectangle is ever so slightly non-rectangular. > > With this tolerant floor the distance between a number and its floor can > be greater than one. Preventing this from happening was one of > McDonnel's goals in designing intolerant floor because it allows the > proof that the Euclidean algorithm works on real numbers to apply to > complex numbers without modification. However, the deviation is very > small: it is greatest when a number just west of c-0j1*ct*|c (for > integer c) rounds to c-1, a distance of (1+&.*:ct*|c) or (4 o. ct*|c). > This is approximately (1+-:*:ct*|c), which rounds to 1 under double > precision when c is less than 2^17. > > Below is the code I used when experimenting with floor. It generates > pictures of floor with an exaggerated comparison tolerance of sct. > > require 'viewmat' > > off =: (1<!.0+/) *. 0 1~:>:!.0/ > grid =: 0.5j0.5 + 120%~(-i:200)j./i:350 > chg =: (-i:200) ((*./&:*+.*./&:(20&>+.100&<:))&:(120|]) *. > [:(15&>+.16&<)+/&.:*:)&:(60&+) i:350 > sct =: %24 > gshow=: 1 : 'chg * 5%~+/"1 (200*256^3|#.@:+.) u > grid+/300%~0,,((%|)2j1)*j./~i:0.5' > tolf =: 1 : '(((] + [: off -+u) <.!.0)&.:+.)"0' > witheq =: 2 : '(u@[`]@.v <.!.0@:(0.25&+)&.:+.)"0' > eqg =: witheq(|@:-<:sct*>.&:|) > > NB. Intolerant floor > 'rgb' viewmat <.!.0"0 gshow > NB. J's current tolerant floor > 'rgb' viewmat (sct%%:2)"_ tolf gshow > NB. Proposed tolerant floor > 'rgb' viewmat ((0,sct)*+/&.:*:@:[)tolf eqg gshow > NB. Another interesting model > 'rgb' viewmat (-(]*[:(,~-@-.)|@-/@[)sct*+/&.:*:@:[)tolf > witheq(([:+./|@:-<:sct*>.&:|)0 0.5j0.5+]) gshow > > Marshall > > On Fri, Oct 11, 2019 at 04:51:41PM +0000, R.E. Boss wrote: > > > Namens Marshall Lochbaum > > > Verzonden: vrijdag 11 oktober 2019 17:07 > > (...) > > > J's implementation seems to be an attempt to follow the XAPL standard > > > (ISO/IEC 13751:2001), which is not freely available. The standard is > > > ambiguous, since it uses the undefined terms "fractional-parts" and > > > "nearer". It's unclear whether these should be subject to comparison > > > tolerance, and it looks like the documentation and implementation have > > > interpreted it two different ways. > > > > > > I think that the fully tolerant interpretation used in documentation is > > > slightly > > > better, but I consider XAPL's definition to be borderline nonsensical in > > > either > > > case. As a Dyalog APL implementer I have done some work on designing a > > > better specification which I'd be happy to share. > > > > I would be happy to read it. > > > > > > R.E. Boss > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
