(parse-decimal-fraction <string>) --> <rational> ?
- From: rem642b@xxxxxxxxx (Robert Maas, see http://tinyurl.com/uh3t)
- Date: Mon, 31 Mar 2008 12:56:03 -0700
Has anybody well-written a function to parse a string containing
decimal-fraction notation *exactly* to the correct rational number,
*rather*than* to some floating point approximation? For example:
(parse-decimal-fraction "3.7") => 37/10
(not 15518925/4194304)
(not even 4165829655317709/1125899906842624)
(parse-decimal-fraction "3.701234501234501234501234567")
=> 3701234501234501234501234567/1000000000000000000000000000
(not 1499/405)
(not 6168718/1666665)
(not 15524103/4194304)
(not even 4167219580142631/1125899906842624)
(parse-decimal-fraction "0.101" :radix 2) => 5/8
Ideally it would take all the same keyword arguments as
parse-integer, with analagous semantics. But a lesser attempt would
still be useful for some applications, so I'm curious to learn
about all the various versions of such a function that folks have
written in Common Lisp.
It would be somewhat equivalent to this java.math.BigDecimal constructor:
<http://java.sun.com/j2se/1.3/docs/api/java/math/BigDecimal.html#BigDecimal(java.lang.String)>
public BigDecimal(String val)
Translates the String representation of a BigDecmal [sic] into a
BigDecimal. The String representation consists of an optional
sign ('+' or '-') followed by a sequence of zero or more
decimal digits ("the integer"), optionally followed by a
fraction, optionally followed by an exponent.
The fraction consists of of [sic] a decimal point followed by zero or
more decimal digits. The string must contain at least one digit
in either the integer or the fraction. ...
except that this is a special-case class rather than a subset of
rationals (Java doesn't have a rational-number class or datatype anyway).
Rationale: What got me to thinking about this is that my HelloPlus
WebPage has recently included Flying Thunder as the 7th language
capable of fully using CGI (including properly decoding
encoded-form-contents to create a "map" i.e. associative array of
some type), after {php, perl, lisp, c, c++, java} were included
previously:
<http://www.rawbw.com/~rem/HelloPlus/hellos.html#step3>
and when I find time and energy I'm proably going to include Flying
Thunder in my CookBook/Matrix also:
<http://www.rawbw.com/~rem/HelloPlus/CookBook/Matrix.html>
and I plan shortly to write up a demo of safely parsing integers in
Flying Thunder to add to the demos in the other six languages I
already have:
<http://www.rawbw.com/~rem/HelloPlus/CookBook/h4s.html>
So I have been asking myself over and over what would make a good
*second* example to include there. Finally today I've decided that
parsing decimal integers would be good, if there's existing code to
do it using any of the various languages. Well as you see Java has
it built-in, so I *should* include it, but it would be a bit of
work to implement it in Lisp also, wouldn't want Java to show up
Lisp would I, but then I thought I'll post this newsgroup article
asking who already did it so I can just show their example instead
of coding the whole thing from scratch. A crude version wouldn't be
too hard (scan for strings of decimal digits separated by #\. and
call parse-integer to convert the integer and fraction part to
integers then do arithmetic to divide the fraction integer by the
appropriate power of ten to get a true fraction part then add to
the integer part. But to include the keyword parameters too would
be more work than I feel like doing when I'm already busy on
another medium-size project, hence my desire to find the
parse-decimal-fraction code already well written.
Aside: This topic gets me back to thinking about interval
arithmetic, including my new idea yesterday that interval
arithmetic would make a great project for my first signficant use
of generic functions in Common Lisp. I could have several different
kinds of real-metric (complete-ordered-field) interval-arithmetic objects:
- Fixed intervals:
- Rational endpoints
- Floating-point endpoints (single and double precision)
- Integer-with-power-of-two endpoints (like BigFloats from MacLisp)
- Integer-with-power-of-ten endpoints (like BigDecimal from Java)
- Rational-with-power-of-two endpoints (brand-new AFAIK)
- Rational-with-power-of-ten endpoints (brand-new AFAIK)
- Infinite-precision mathematical real numbers by lazy-evaluation
- Nested intervals (where each interval can be any kind of fixed interval)
- Ordinary continued fractions
(every term except first must be positive integer)
- Redundant continued fractions
(every term except first must equal positive integer plus 0 or 1/2)
- Ordinary decimal (or other radix) notation.
- Redundant decimal (or other radix) notation (using hexadecimal
notation ABCDE for positive overflow past nine, and IBM 026
keypunch notation JKLMN for negative overfow past zero, for printing)
- Isolated zero of polynomial function within known-monotonic interval
- Alternating Taylor series
- Transcendental functions (trigonometric/logarithmetic/exponential/power)
- Isolated zero of transcendental functions within known-monotonic interval
- Set-theoretic Dedekind cuts (predicate that tells whether given
rational number is in upper or lower cut, but hangs on exact
rational-real not *known* to be rational when compared to itself,
but uses continued fraction (a la rationalize) to guess at the
most likely rational)
The basic arithmetic functions would be replaced by plus minus
times quotient which would be generic functions whereby ordinary
data types and interval types could be freely mixed, and a keyword
argument could specify the desired type of interval result if the
default isn't wanted. Also, providing just a single parameter to
plus or times, plus the keyword for desired result type, would
coerce the value to the new type, usually by wrapping a
lazy-evaluation continution around it. Either a type specifier or a
sample value could be used.
(setq x (plus 3/7 :result-type :decimal))
=> [OrdinaryDecimal "0.4" [Continuation for 285714...]]
(refine-interval x)
=> [OrdinaryDecimal "0.42" [Continuation for 857142...]]
(setq y (plus 1/13 :result-type x))
=> [OrdinaryDecimal "0.0" [Continuation for 769230...]]
(refine-interval y)
=> [OrdinaryDecimal "0.07" [Continuation for 692307...]]
(setq z (plus y :result-type '(:nested :rational 10))
=> [NestedRationalIntervals 7/100 8/100 <link to above object>]
(setq w (plus y :result-type '(:nested :rational :floating 10))
=> [FloatingDecimal -2
[NestedRationalIntervals [7 8] <link to earlier 692307... continuation>]
(setq xx (plus x :result-type w))
=> [FloatingDecimal -1
[NestedRationalIntervals [42 43] <link to earlier 857142... continuation>]
(refine-interval xx :relative-precision 1/3)
=> [FloatingDecimal -1
<some interval narrower than [42 43] by at least a factor of 3.
probably [214/5 429/10], reduced from [428/10 429/10]>
<some continuation on further narrowing that interval>]
BTW: Yesterday I got so inspired on this new idea that I took some
time off from my current medium-sized project to toy with a new
better algorithm for finding (real) zeroes of a polynomial as
interval arithmetic continuations. Of course a variation of
Newton's method is used once we already have a good-enough
preliminary interval around the exact zero. (I worked out the best
way to adapt Newton's method a few months ago but haven't gotten
around to programming it.) But yesterday I thought of an
easy-to-program apparently-fail-proof algorithm for isolating the
(real) zeroes and then automatically narrowing those isolation
intervals to the point where good Newton's method behaviour is
assured immediately, and spent a little bit too much of my time
playing around with the algorithm to get a "feel" for how it would
really work. Maybe after I finish the current medium-sized project
(involving using 15-dimensional ProxHash vectors to build a
nearest-neighbor network for a set of nearly three hundred records
in a corpus, using a new idea I had a few months ago but didn't
previously try implementing),
I might feel like spending the time to implement my pre-Newton
zero-isolating algorithm and then put it up as a Web demo. Of
course the first thing it will do is take the GCD between the
polynomial and its first derivative to find all multiple zeroes and
divide them out to get a squarefree polynomial which is much easier
to work with when doing interval arithmetic.
.
- Prev by Date: Re: indent for CL
- Next by Date: Re: Two questions about eq
- Previous by thread: Appropriate case for a macro?
- Index(es):
Relevant Pages
|
