<div dir="ltr"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-size:12.7272720336914px">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.</span></blockquote><div><span style="font-size:12.7272720336914px"><br></span></div><div><span style="font-size:12.7272720336914px">What's the best way to impose systematic number typing on existing untyped code, for instance, forcing everything to be a flonum? Does it require switching to Typed Racket? Or does mean </span>making explicit calls to `exact->inexact` and using the flonum math operators? Or some other technique?</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-size:12.7272720336914px">Indexing two structs to get operands to add together takes more time than actually adding them;</span></blockquote><div class="gmail_extra"><span style="font-size:12.7272720336914px"><br></span></div><div class="gmail_extra">What are the preferred data structures for optimizing math performance, if structs are too slow? Vectors?</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 2, 2014 at 7:17 PM, Neil Toronto <span dir="ltr"><<a href="mailto:neil.toronto@gmail.com" target="_blank">neil.toronto@gmail.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Here are some options for representing lengths.<br>
<br>
* 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.<br>
<br>
* 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.<br>
<br>
* 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.<br>
<br>
* 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.<br>
<br>
* Bigfloats. About 100x slower than flonums. The default precision of 128 bits is likely way more than you'll ever need for layout.<br>
<br>
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.<br>
<br>
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.<br>
<br>
(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.)<span class=""><font color="#888888"><br>
<br>
Neil ⊥</font></span><span class=""><br>
<br>
On 12/01/2014 07:07 PM, Matthew Butterick wrote:<br>
</span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">
Right, I meant "exact" in the Racket sense of "exact rational."<br>
<br>
The broader issue I'm thinking about is what kind of units to use in a<br>
typesetting system in order to get the best balance of precision and speed.<br>
<br>
For instance, the flexibility of a 64-bit flonum doesn't necessarily buy<br>
you anything over a 64-bit fixnum, since typesetting systems have a<br>
practical limit on both precision (in the subpixel direction) and scale<br>
(in the megapixel direction).<br>
<br>
TeX, for instance, is based on a "scaled point" which represents<br>
1/65536th of a point, with a max dimension of 2^30 scaled points, or<br>
about 19 feet. One could imagine a 64-bit version of this concept that<br>
extends both the scale and precision (to ludicrous degrees) while<br>
remaining a fixnum (which I gather from the docs are typically cheapest).<br>
<br>
<br>
<br>
<br>
<br>
On Mon, Dec 1, 2014 at 2:01 PM, Matthew Flatt <<a href="mailto:mflatt@cs.utah.edu" target="_blank">mflatt@cs.utah.edu</a><br></span><div><div class="h5">
<mailto:<a href="mailto:mflatt@cs.utah.edu" target="_blank">mflatt@cs.utah.edu</a>>> wrote:<br>
<br>
We should probably improve the contracts on `racket/draw` to promise<br>
flonum results for text metrics. The intent is to make metric-derived<br>
calculations have a predictable cost, instead of potentially triggering<br>
expensive exact arithmetic.<br>
<br>
When you say that Pango produces "exact" results, do you mean "integer"<br>
or "exact rational"? The latter is certainly true: Pango's raw API<br>
produces integers to be divided by 1024 to convert to drawing units.<br>
Taking that conversion into account, Pango doesn't always produce<br>
integer drawing units (at least on some platforms; I'm not sure about<br>
all). Even so, the intent is that representing an integer divided by<br>
1024 as a flonum will not normally lose any prevision (i.e., for normal<br>
drawing sizes), and so `inexact->exact` on the immediate result from<br>
`racket/draw` recovers the exact Pango result when exact arithmetic is<br>
specifically wanted.<br>
<br>
At Mon, 1 Dec 2014 11:56:12 -0800, Matthew Butterick wrote:<br>
> The `get-text-extent` method in racket/draw does not<br>
contractually guarantee<br>
> either exact or inexact numbers, though in practice I find it<br>
produces inexact.<br>
><br>
> This function, however, calls into the Pango text-layout system.<br>
I find that<br>
> when I invoke Pango's text measuring directly through the FFI, it<br>
produces<br>
> exact results.<br>
><br>
> Is this difference in behavior deliberate, or does<br>
`get-text-extent` preserve<br>
> exactness under certain circumstances?<br>
><br>
><br>
> ____________________<br>
> Racket Users list:<br>
> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/<u></u>users</a><br>
<br>
<br>
<br>
<br>
____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/<u></u>users</a><br>
<br>
</div></div></blockquote><div class=""><div class="h5">
<br>
____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/<u></u>users</a><br>
</div></div></blockquote></div></div></div>