[racket] how to get exact results from get-text-extent

From: Neil Toronto (neil.toronto at gmail.com)
Date: Tue Dec 2 22:17:11 EST 2014

Here are some options for representing lengths.

  * Fixed-point numbers; i.e. a fixnum n represents n/2^k (where k = 16 
for TeX). These are cheap and easy until you want to multiply or divide 
them. Then they get more expensive and bit-shifty. You can forget about 
doing anything else quickly. On the plus side, if you allow arbitrary 
integers, lengths that fit in a fixnum are still reasonably fast to 
operate on, and there's no limit on maximum length.

  * Flonums. With these, you can exactly represent lengths up to 2^36 = 
68719476736 points at TeX's 1/2^16-point precision. In Racket, they're 
just about as fast as fixnums, unless a result is put in a struct or is 
heap-allocated. Those results are 2x-3x slower.

  * Exact rationals. Exact for arithmetic, slow, and generally grow 
without bound as the number of operations that produces them increases. 
Non-arithmetic forces deciding on a precision, but can be done with just 
a little pain by converting to bigfloats and back.

  * Double-doubles; i.e. two flonums that represent one value, for about 
106 bits precision. (So at TeX's precision, they exactly represent 
lengths up to 2^90 = 1237940039285380274899124224 points.) 10x slower 
than flonums, and 4x more annoying to work with.

  * Bigfloats. About 100x slower than flonums. The default precision of 
128 bits is likely way more than you'll ever need for layout.

Here's the thing: layout code will do a lot more than compute 
arithmetic. Indexing two structs to get operands to add together takes 
more time than actually adding them; sometimes a lot more. IMO, this 
makes the speed of fixnums vs. flonums, or even fixnums vs. integers 
(usually), a non-issue. You may even be able to get away with using 
bigfloats if you need them.

Here's what I'd do: decide on a smallest fractional point and a longest 
length, and determine how many bits that requires. If 52 bits is enough, 
use flonums. If it's not, write a prototype using bigfloats. If that's 
too slow, try double-doubles or fixed-point numbers.

(If you use fixed-point numbers, double the number of fractional bits to 
make area calculations exact and square roots decently precise. The 
latter can be computed using `integer-sqrt` without too much trouble.)

Neil ⊥

On 12/01/2014 07:07 PM, Matthew Butterick wrote:
> Right, I meant "exact" in the Racket sense of "exact rational."
> The broader issue I'm thinking about is what kind of units to use in a
> typesetting system in order to get the best balance of precision and speed.
> For instance, the flexibility of a 64-bit flonum doesn't necessarily buy
> you anything over a 64-bit fixnum, since typesetting systems have a
> practical limit on both precision (in the subpixel direction) and scale
> (in the megapixel direction).
> TeX, for instance, is based on a "scaled point" which represents
> 1/65536th of a point, with a max dimension of 2^30 scaled points, or
> about 19 feet. One could imagine a 64-bit version of this concept that
> extends both the scale and precision (to ludicrous degrees) while
> remaining a fixnum (which I gather from the docs are typically cheapest).
> On Mon, Dec 1, 2014 at 2:01 PM, Matthew Flatt <mflatt at cs.utah.edu
> <mailto:mflatt at cs.utah.edu>> wrote:
>     We should probably improve the contracts on `racket/draw` to promise
>     flonum results for text metrics. The intent is to make metric-derived
>     calculations have a predictable cost, instead of potentially triggering
>     expensive exact arithmetic.
>     When you say that Pango produces "exact" results, do you mean "integer"
>     or "exact rational"? The latter is certainly true: Pango's raw API
>     produces integers to be divided by 1024 to convert to drawing units.
>     Taking that conversion into account, Pango doesn't always produce
>     integer drawing units (at least on some platforms; I'm not sure about
>     all). Even so, the intent is that representing an integer divided by
>     1024 as a flonum will not normally lose any prevision (i.e., for normal
>     drawing sizes), and so `inexact->exact` on the immediate result from
>     `racket/draw` recovers the exact Pango result when exact arithmetic is
>     specifically wanted.
>     At Mon, 1 Dec 2014 11:56:12 -0800, Matthew Butterick wrote:
>      > The `get-text-extent` method in racket/draw does not
>     contractually guarantee
>      > either exact or inexact numbers, though in practice I find it
>     produces inexact.
>      >
>      > This function, however, calls into the Pango text-layout system.
>     I find that
>      > when I invoke Pango's text measuring directly through the FFI, it
>     produces
>      > exact results.
>      >
>      > Is this difference in behavior deliberate, or does
>     `get-text-extent` preserve
>      > exactness under certain circumstances?
>      >
>      >
>      > ____________________
>      >   Racket Users list:
>      > http://lists.racket-lang.org/users
> ____________________
>    Racket Users list:
>    http://lists.racket-lang.org/users

Posted on the users mailing list.