rntz

no profile record

投稿

Evaluation order and nontermination in query languages

rntz.net

1 ポイント投稿者 rntz14 日前0 コメント

Deconstructing Datalog

rntz.net

18 ポイント投稿者 rntz先月0 コメント

rntz

5 か月前議論

why the sharp divide around december 2022, with almost none imported before that and plenty after?

rntz

9 年前議論

Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)

rntz

9 年前議論

Huh, is this the stuff you're talking about:

    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf
    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf
    https://www.youtube.com/watch?v=sz9ZlZIRDAg
    https://hackage.haskell.org/package/discrimination

I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.

rntz

9 年前議論

I'm tempted to suggest

    (low / 2) + (high / 2)

but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop worrying about overflow altogether.

rntz

9 年前議論

The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.

rntz

10 年前議論

Chez is known for being very fast, and for using state-of-the-art compiler technology.