I ran into problems of the kind
CL-USER> (floor -0.1 0.02)
-6
0.019999996
I know this is caused by inexact floating-point representation of
rational numbers. I thought about my algorithm, and I think that
working with ratios would solve my problem.
However, I need to convert the input of the function (which can be
anything, integer, ratio, double-float) to a ratio.[1] How can I do
this? (coerce 0.1 'ratio) doesn't work, and the HyperSpec on ratio [2]
didn't help much.
[1] inexact conversion, eg finding the nearest ratio within an epsilon
would work too
[2] http://www.lispworks.com/documentation/HyperSpec/Body/t_ratio.htm
On Jul 23, 11:42 am, Tamas Papp <······@gmail.com> wrote:
> [1] inexact conversion, eg finding the nearest ratio within an epsilon
> would work too
If you're doing floating-point operations, "Nearest ratio within an
epsilon" (a.k.a. "interval arithmetic") is a harder problem than you
might think, unless your algorithm is trivial. Applied naively,
interval arithmetic is generally non-useful. If you're working with
rational numbers, you might choose "nearest ratio within an epsilon,"
based on some criterion of minimizing the length of the
representation, but this is only useful for display purposes and not
for making the code faster. (Alternately, you could just get the
final result as a rational number, and then divide the numerator by
the denominator as floating-point numbers and get an approximate
result which is accurate to within machine epsilon.)
Alternately, just use floating-point numbers (or DOUBLE-FLOAT's, to
increase precision) and rationalize them when you're done.
mfh
"Mark H." <············@gmail.com> writes:
> On Jul 23, 11:42 am, Tamas Papp <······@gmail.com> wrote:
>> [1] inexact conversion, eg finding the nearest ratio within an epsilon
>> would work too
>
> If you're doing floating-point operations, "Nearest ratio within an
> epsilon" (a.k.a. "interval arithmetic") is a harder problem than you
> might think, unless your algorithm is trivial. Applied naively,
> interval arithmetic is generally non-useful. If you're working with
> rational numbers, you might choose "nearest ratio within an epsilon,"
> based on some criterion of minimizing the length of the
> representation, but this is only useful for display purposes and not
> for making the code faster. (Alternately, you could just get the
> final result as a rational number, and then divide the numerator by
> the denominator as floating-point numbers and get an approximate
> result which is accurate to within machine epsilon.)
>
> Alternately, just use floating-point numbers (or DOUBLE-FLOAT's, to
> increase precision) and rationalize them when you're done.
Thanks Mark,
I am using this code for pretty labelling of axes, so rational is
exactly what I need.
Tamas
I have some Java [sigh] code that halfway solves this problem. I'd be
happy to send it by e-mail if you're interested.
The code is designed for this problem: given two longitude values on a
map, find a number of ticks between them that will look nice when
printed in decimal degrees. Given 71.449430 and 109.48973 and asked
for 3 ticks, the code should find 72, 90, 108. These are desirable
because they're integers, and because the step-size between them (18)
is a divisor of 360. To apply my code to your problem, there is a
parameter to change from 360 to an appropriate power of 10.
The main idea is to multiply by powers of 10 until you get enough
freedom to choose the ticks using integers. For instance, to find 3
ticks between 0.0523 and 0.0547,
change 0.0523--0.0547 to
0.523--0.547
5.23--5.47
52.3--54.7 [there is one integer tick between these]
523--547 [there are over 20 integer ticks between these; choose the
best three]
···············@yahoo.com writes:
> I have some Java [sigh] code that halfway solves this problem. I'd be
> happy to send it by e-mail if you're interested.
>
> The code is designed for this problem: given two longitude values on a
> map, find a number of ticks between them that will look nice when
> printed in decimal degrees. Given 71.449430 and 109.48973 and asked
> for 3 ticks, the code should find 72, 90, 108. These are desirable
> because they're integers, and because the step-size between them (18)
> is a divisor of 360. To apply my code to your problem, there is a
> parameter to change from 360 to an appropriate power of 10.
>
> The main idea is to multiply by powers of 10 until you get enough
> freedom to choose the ticks using integers. For instance, to find 3
> ticks between 0.0523 and 0.0547,
> change 0.0523--0.0547 to
> 0.523--0.547
> 5.23--5.47
> 52.3--54.7 [there is one integer tick between these]
> 523--547 [there are over 20 integer ticks between these; choose the
> best three]
Thanks, but I already have this:
(defun pretty-axis-positions (lower upper n &optional (round-to '(1 2 5)))
"Supply suitably rounded numbers between lower and upper, with
at most n (or, in rare cases, n+1) numbers. Returns multiple
values, a list with the positions and an exponent which can be
used for rounding these numbers. When
lower=upper, (values (lower) nil) is returned. round-to should
be a list of numbers that divide 10, mantissas are rounded to
these values.
Examples:
(pretty-axis-positions 1 2.1 2) => (1 3/2 2 5/2), -1
(pretty-axis-positions 417 972 3) => (400, 500, 600, 700, 800, 900, 1000), 2
"
;; convert endpoints to rational numbers
(let ((lower (rationalize lower))
(upper (rationalize upper)))
;; check input
(assert (<= 0 n) (n) "n=~A is not positive" n)
(assert (<= lower upper) (lower upper)
"~A <= ~A does not hold." lower upper)
;; trivial axis: return single point
(when (= lower upper)
(return-from pretty-axis-positions (values (list lower) nil)))
;; non-trivial axis
(let* ((raw-step (/ (- upper lower) (1+ n)))
(exponent (floor (log raw-step 10)))
(mantissa (/ raw-step (expt 10 exponent)))
(step-first-digit (or (find-if (lambda (s) (<= mantissa s))
round-to) 10))
(step (* step-first-digit
(expt 10 exponent)))
(start (* (ceiling lower step) step))
(end (* (floor upper step) step)))
;; correct exponent if step-first-digit is 10
(if (= step-first-digit 10)
(incf exponent))
;; collect marks
(iter
(for label-pos :from start :to end :by step)
(collecting label-pos :into positions)
(finally
(return (values positions exponent)))))))
Improvements are of course welcome, I didn't bother about the rare
case when I get n+1 values since it happens rarely.
Tamas
>>>>> "Tamas" == Tamas Papp <······@gmail.com> writes:
Tamas> Thanks, but I already have this:
[snip]
There's a nice TOMS routine available from netlib that chooses nice
axis values. It's in Fortran, but it's really quite straightforward.
It had 3 routines:
1) Choose nice labels, but not necessarily the exact number of
intervals you specified.
2) Choose nice labels, with exactly the number of intervals you said.
3) Like 1), but for logarithmic axes.
I used to have a Lisp translation, but I've misplaced it. :-(
Ray
+ Tamas Papp <······@gmail.com>:
| However, I need to convert the input of the function (which can be
| anything, integer, ratio, double-float) to a ratio.[1] How can I do
| this? (coerce 0.1 'ratio) doesn't work, and the HyperSpec on ratio [2]
| didn't help much.
If you had browsed the Numbers chapter you just might have come across
RATIONAL and RATIONALIZE.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell