Hello, a quit funny hugs session: Prelude> 0.5::Rational 1 % 2 Prelude> 0.1::Rational 13421773 % 134217728 Prelude> 13421773/134217728 0.1 I do not know how this fraction is calculated, but it does not fit my expectations :-) Ok, ok, it is no bug... Ciao, Steffen -- Steffen Mazanek - www.steffen-mazanek.de - GPG: 791F DCB3 Haskell, that's where I just curry until fail, unwords any error, drop all undefined, maybe break, otherwise in sequence span isControl and take max $, id: (d:[])
On 2003-07-05 at 19:43+0200 Steffen Mazanek wrote:
Hello,
a quit funny hugs session:
Prelude> 0.5::Rational 1 % 2 Prelude> 0.1::Rational 13421773 % 134217728 Prelude> 13421773/134217728 0.1
I do not know how this fraction is calculated, but it does not fit my expectations :-)
Remember that internally arithmetic is binary, and that 0.1 can't be expressed exactly as a floating point number. I think that's the explanation.
Ok, ok, it is no bug...
No, I think it is a bug: 0.1 ought to be equivalent to fromRational (1%10), but Hugs isn't intended for numerical work. GHCi gets the right answer. Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk
On Sat, Jul 05, 2003 at 08:24:32PM +0100, Jon Fairbairn wrote:
On 2003-07-05 at 19:43+0200 Steffen Mazanek wrote:
a quit funny hugs session:
Prelude> 0.5::Rational 1 % 2 Prelude> 0.1::Rational 13421773 % 134217728 Prelude> 13421773/134217728 0.1
I do not know how this fraction is calculated, but it does not fit my expectations :-)
Remember that internally arithmetic is binary, and that 0.1 can't be expressed exactly as a floating point number. I think that's the explanation.
Ok, ok, it is no bug...
No, I think it is a bug: 0.1 ought to be equivalent to fromRational (1%10), but Hugs isn't intended for numerical work. GHCi gets the right answer.
Yes, Hugs represents floating point literals in binary, and it's not intended for the numeric work. But the CVS version already contains a hack that usually converts these literals back to the right Rational: Prelude> 0.1::Rational 1 % 10 Prelude> 0.0123456789::Rational 123456789 % 10000000000 Prelude> 2.2e-9::Rational 11 % 5000000000 The real fix would be to keep the literals as Rationals, but this would be too expensive in the Hugs setting.
Jon Fairbairn comments //Steffen Mazanek//:
Prelude> 0.1::Rational 13421773 % 134217728 Prelude> 13421773/134217728 0.1
I do not know how this fraction is calculated, but it does not fit my expectations :-)
Remember that internally arithmetic is binary, and that 0.1 can't be expressed exactly as a floating point number. I think that's the explanation.
Ok, ok, it is no bug...
No, I think it is a bug: 0.1 ought to be equivalent to fromRational (1%10), but Hugs isn't intended for numerical work. GHCi gets the right answer.
This is less a bug than a Nessie monster which haunts Hugs some centuries already, and on Internet the issue has been discussed at least 4 times. The old, experimental Gofer Prelude numeric functions were sometimes abominable, since Mark Jones concentrated on other things, and nobody really complained, people were busy with other stuff as well. But I can't understand why this continues until now. The obvious technique to convert floats to rationals is the continued fraction expansion which gives the simplified answer fast. I don't understand the remark that the internal arithmetic is binary. Sure, it is, so what? Why Ross Paterson underlies this as well? He concludes:
The real fix would be to keep the literals as Rationals, but this would be too expensive in the Hugs setting.
Andrew Bromage says some words about errors and representation. I think that the problem can (perhaps should) be dealt with at a higher level. What's wrong with conversion functions like those below. First, convert a float to a lazy list of coeffs. of a regular continued fraction: tocfrac x = let n = floor x y = x-fromInteger n in n : if y==0.0 then [] else tocfrac (recip y) and then reconstruct using Euler sequences as described in Knuth or perhaps an optimized method, the one I cite is not very efficient. It gives a list of (N,D) -- *all* rational approximants of the original float. continuant l@(_:ql) = zip (tail (euseq l)) (euseq ql) where euseq [] = [] euseq (x:q) = eus 1 x q eus p0 p1 (a:cq) = p0 : eus p1 (a*p1+p0) cq eus p0 p1 [] = [p0,p1] Now, test it: pp=3.141592653589793 r=take 10 (continuant (tocfrac pp)) You should get [(3,1),(22,7),(333,106),(355,113),(103993,33102),(104348,33215), ... etc;, anyway all that is already inexact... For 0.1 one gets [(0,1),(1,10)] Jerzy Karczmarczuk
On 2003-07-07 at 12:01+0200 Jerzy Karczmarczuk wrote:
Jon Fairbairn comments //Steffen Mazanek//:
Prelude> 0.1::Rational 13421773 % 134217728 Prelude> 13421773/134217728 0.1
I do not know how this fraction is calculated, but it does not fit my expectations :-)
Remember that internally arithmetic is binary, and that 0.1 can't be expressed exactly as a floating point number. I think that's the explanation.
I don't understand the remark that the internal arithmetic is binary. Sure, it is, so what?
My comment was perhaps too brief. As far as I am concerned, a constant with a decimal point in it should go like this: CCCCC.DD...DD \__d__/ becomes fromRational (CCCCCDD...DD % 100...00) and there's no problem in getting an accurate Rational (what you say about conversions applies if the desired result is some kind of float). However, if the conversion goes via float, and I think doing that is a bug, the fact that 1/5 has an infinite expansion in binary explains the peculiar numbers that Hugs produces in its Rational. It's an explanation of what happens, not what should be! During the revision of the report I said something to the effect that Int, Float and Double do not belong in the language proper. The suggestion was rejected for (I think) sociological reasons, but I still stand by it. While they should of course be provided in the standard libraries, they only serve to confuse things as far as the language design is concerned. Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk 31 Chalmers Road jf@cl.cam.ac.uk Cambridge CB1 3SZ +44 1223 570179 (after 14:00 only, please!)
On Mon, Jul 07, 2003 at 12:01:09PM +0200, Jerzy Karczmarczuk wrote:
This is less a bug than a Nessie monster which haunts Hugs some centuries already, and on Internet the issue has been discussed at least 4 times. The old, experimental Gofer Prelude numeric functions were sometimes abominable, since Mark Jones concentrated on other things, and nobody really complained, people were busy with other stuff as well.
But I can't understand why this continues until now. The obvious technique to convert floats to rationals is the continued fraction expansion which gives the simplified answer fast.
That would be because resources for Hugs maintenance are extremely limited, and expertise in numerical methods even more lacking. (e.g.: which approximant in the series should be chosen?) I think that if someone who knows about these things submitted a patch, and it didn't increase the size of the Prelude (by much), it would be gratefully accepted. (That's probably true of all of Hugs.) However, as far as I know, the outstanding numeric bugs in the Prelude are - floating point literals of type Ratio t (mostly fixed in CVS), and - the show instances for Float and Double (because the correct Numeric.showFloat would make the Prelude too large)
I don't understand the remark that the internal arithmetic is binary. Sure, it is, so what?
In the case of 0.1::Rational, it shouldn't be using floating point. The Report says this means fromRational (1%10), i.e. 1%10. If Hugs implemented the Haskell definition directly, the question of approximation wouldn't arise. GHC does it that way, and usually removes the fromRational at compile time, but Hugs isn't that clever.
On Mon, Jul 07, 2003 at 01:09:53PM +0200, Wolfgang Jeltsch wrote:
On Monday, 2003-07-07, 13:05, CEST, Ross Paterson wrote:
In the case of 0.1::Rational, it shouldn't be using floating point. The Report says this means fromRational (1%10), i.e. 1%10.
In which paragraph of the report is this specified?
I take that as the meaning of the part you're reading (6.4.1), though it would be better if it said "the appropriate value" rather than "a value".
Ross Paterson wrote:
In the case of 0.1::Rational, it shouldn't be using floating point. The Report says this means fromRational (1%10), i.e. 1%10.
Aha. Now I have a little chance to die less naïve. All my conversion proposals are simply out of place, since there should be nothing to convert. And I understand the reluctance of Jón to accept the numerical types as belonging to the language... ... and I begin once again to appreciate the Scheme idea of having the distinction between exact and inexact numbers. Of course, you are right reminding that when floats are engaged there is fuzziness in the conversion:
(e.g.: which approximant in the series should be chosen?)
but I believe (still naïvely??) that those socio-psycho-pragmatisms which played some role in the definition of the language should be better tuned. If I were to write pi = 3.1415926536 :: Rational I suppose that I would like to see rather 355/113 or something close, than 3926990817/1250000000 or similar. GHCI doesn't make me happier than Hugs: 221069929751607/70368744177664. Thus, perhaps one day we might think about parametrizing the 'conversion' of *explicit* decimal numbers, and -- as some other language permit -- make it possible and practical to use any other base different from 10. What do you think? Such parametrization (perhaps with some global default) would also help the user who permits himself to write x = 1.875987 :: Rational to assess the error introduced by the representation conversion. Jerzy Karczmarczuk
On 2003-07-07 at 13:40+0200 Jerzy Karczmarczuk wrote:
[...] I believe (still naïvely??) that those socio-psycho-pragmatisms which played some role in the definition of the language should be better tuned. If I were to write
pi = 3.1415926536 :: Rational
I suppose that I would like to see rather 355/113 or something close, than 3926990817/1250000000 or similar.
If it's a _Rational_, surely you want it to be exactly the same as you get for 31415926536%10000000000?
GHCI doesn't make me happier than Hugs: 221069929751607/70368744177664.
That doesn't happen for me: Prelude> :m Ratio Prelude Ratio> 31415926536%10000000000 3926990817 % 1250000000 Prelude Ratio> 3.1415926536::Rational 3926990817 % 1250000000 Prelude Ratio> What did you do to get it?
Thus, perhaps one day we might think about parametrizing the 'conversion' of *explicit* decimal numbers, and -- as some other language permit -- make it possible and practical to use any other base different from 10. What do you think?
There might be a use for that, but one can already write 0x55%2^32 so I'm not sure that there would be much call for it, given what I say below
Such parametrization (perhaps with some global default) would also help the user who permits himself to write x = 1.875987 :: Rational to assess the error introduced by the representation conversion.
I think that <decimal number> :: Rational ought not to introduce any error at all! As to exact v inexact numbers, in a sense we already have that distinction. Integer and Rational are (in correct implementations!) exact, Int, Float and Double are inexact. One could express my objection to the design as: relegate all inexactitudes to libraries. Cheers, Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk
In article <3F095C21.8020601@info.unicaen.fr>,
Jerzy Karczmarczuk
If I were to write
pi = 3.1415926536 :: Rational
I suppose that I would like to see rather 355/113 or something close, than 3926990817/1250000000 or similar.
There should be a separate syntax for that. As it stands, the string "3.1415926536" unambiguously specifies a rational number. Perhaps something like "3.1415926536..." should be interpreted as the 'simplest' rational that agrees with the given digits, which would then be passed to fromRational. Also, it might be nice to be able to specify the recurring digits of other rationals, for instance 0._3 = 1/3 0.29_54 = 13/44 etc. -- Ashley Yakeley, Seattle WA
Ashley Yakeley
There should be a separate syntax for that. As it stands, the string "3.1415926536" unambiguously specifies a rational number. Perhaps something like "3.1415926536..." should be interpreted as the 'simplest' rational that agrees with the given digits, which would then be passed to fromRational.
I.e. for 3.14, allow any rational number in [3.14,3.15), or perhaps (3.135,3.145]? Or restrict it to just the rational number in range with the least total digits? -kzm -- If I haven't seen further, it is by standing in the footprints of giants
In article
I.e. for 3.14, allow any rational number in [3.14,3.15), or perhaps (3.135,3.145]?
Specifically the simplest rational in the range (I prefer the second one, "round half even"). One rational is simpler than another if both its numerator and denominator are closer to zero. In any given range, there is one rational that is simpler than all the others. I have a function that finds this rational, because I had to implement it for HScheme, because there's a function specified in R5RS called "rationalize" that must do this. In this case it tells me the simplest rational is 22/7. -- Ashley Yakeley, Seattle WA
G'day all. On Mon, Jul 07, 2003 at 12:01:09PM +0200, Jerzy Karczmarczuk wrote:
I don't understand the remark that the internal arithmetic is binary. Sure, it is, so what?
The reason is that you can get the Rational representation even faster than using continued fractions. :-) toFrac :: (RealFloat a) => a -> Rational toFrac x | m == 0 = 0 | otherwise = fromInteger m * 2^^(toInteger n) where (m,n) = decodeFloat x Prelude> toFrac 0.1 13421773 % 134217728 Cheers, Andrew Bromage
Andrew J Bromage wrote:
On Mon, Jul 07, 2003 at 12:01:09PM +0200, Jerzy Karczmarczuk wrote:
I don't understand the remark that the internal arithmetic is binary. Sure, it is, so what?
The reason is that you can get the Rational representation even faster than using continued fractions. :-)
toFrac :: (RealFloat a) => a -> Rational toFrac x | m == 0 = 0 | otherwise = fromInteger m * 2^^(toInteger n) where (m,n) = decodeFloat x
Prelude> toFrac 0.1 13421773 % 134217728
But I knew that, as anybody else. And *this* is what worries me. I am not sure that what we really need in this context is just speed... Or even the *ultimate* precision... Do you mind a Polish historical/religious anecdote? There was once upon a time, some 500 years ago, a painter called Kmita. A very good Christian, very pious and correct. He painted mainly the Trinity members, ocasionally Virgin Mary, and some saints. And when he painted God Father, he did it on his knees, so strong was his faith and catholic worship. Finally our Lord got annoyed. He descended from the painting, looked upon the kneeled Kmita, and said: "You, Kmita! Don't paint me on your knees! Paint me WELL!" ////////////////////////////////////////////////////////////////////////////// Jon Fairbairn comments my complaint:
GHCI doesn't make me happier than Hugs: 221069929751607/70368744177664.
That doesn't happen for me:
Prelude> :m Ratio Prelude Ratio> 31415926536%10000000000 3926990817 % 1250000000 Prelude Ratio> 3.1415926536::Rational 3926990817 % 1250000000 Prelude Ratio>
What did you do to get it?
I should have been more precise: your, the last value comes from Ghci, and I obtained it as well. The first one is the outcome of Hugs (old version, Feb. 2001). About exact/inexact 'pi' = 3.1415926536
If it's a _Rational_, surely you want it to be exactly the same as you get for 31415926536%10000000000?
No. If 'you' means concretely me, then no. Simply no. Writing pi = 3.1415926536 :: Rational and expecting to continue the computations with an exact fraction 31415926536%10000000000, with the well known explosion of Nums & Dens seems pragmatically silly. I stop here, since there is nothing to say. If the Language Report says that the construction: v = ZZZZZZZZZZ :: Rational is to be *exact*, whatever ZZZZZZZZZZ may be, let it be. Tu l'as voulu, Georges Dandin. I see that people are abhorred by the perspective of seeing it as a demand for - possibly approximate - conversion. I am abhorred by the fact that adding ... :: Rational changes the lexical meaning of a literal. Thank you for inspiring discussion. Jerzy Karczmarczuk Caen, France
On 2003-07-08 at 10:15+0200 Jerzy Karczmarczuk wrote:
If it's a _Rational_, surely you want it to be exactly the same as you get for 31415926536%10000000000?
No. If 'you' means concretely me, then no. Simply no. Writing pi = 3.1415926536 :: Rational
and expecting to continue the computations with an exact fraction 31415926536%10000000000, with the well known explosion of Nums & Dens seems pragmatically silly.
Ah, well, I'd say that writing pi = 3.1415926536 :: Rational is just misleading -- we all know jolly well that pi isn't a rational, so anyone who writes that deserves what they get. Now, if you were to write pi = 3.1415926536 :: Real I'd be happy to argue over just what the conversion is supposed to do. Unfortunately we don't have Real (in libraries as far as I remember -- if you have a continued fraction implementation of it, it ought to go to the libraries list). Cheers, Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk 31 Chalmers Road jf@cl.cam.ac.uk Cambridge CB1 3SZ +44 1223 570179 (after 14:00 only, please!)
On Tue, 08 Jul 2003 13:06:23 +0100
Jon Fairbairn
On 2003-07-08 at 10:15+0200 Jerzy Karczmarczuk wrote:
If it's a _Rational_, surely you want it to be exactly the same as you get for 31415926536%10000000000?
No. If 'you' means concretely me, then no. Simply no. Writing pi = 3.1415926536 :: Rational
and expecting to continue the computations with an exact fraction 31415926536%10000000000, with the well known explosion of Nums & Dens seems pragmatically silly.
Ah, well, I'd say that writing
pi = 3.1415926536 :: Rational
is just misleading -- we all know jolly well that pi isn't a rational, so anyone who writes that deserves what they get.
Now, if you were to write
pi = 3.1415926536 :: Real
I'd be happy to argue over just what the conversion is supposed to do. Unfortunately we don't have Real (in libraries as far as I remember -- if you have a continued fraction implementation of it, it ought to go to the libraries list).
There's an exact real library in haskell-libs using Linear Fractional Transformations, http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/haskell-libs/libs/exactreal/.
G'day all. On Tue, Jul 08, 2003 at 01:06:23PM +0100, Jon Fairbairn wrote:
Unfortunately we don't have Real (in libraries as far as I remember -- if you have a continued fraction implementation of it, it ought to go to the libraries list).
Not one, but TWO implementations! One using continued fractions, one using LFTs. http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/haskell-libs/libs/exactreal/ Cheers, Andrew Bromage
G'day all. On Sat, Jul 05, 2003 at 07:43:18PM +0200, Steffen Mazanek wrote:
Prelude> 0.1::Rational 13421773 % 134217728
That's allowed. The Rational only has to be correct to the limit of machine precision. (Incidentally, if it's any help in working out how this Rational was computed, the denominator is 2^27.)
Prelude> 13421773/134217728 0.1
Also allowed for the same reason.
Ok, ok, it is no bug...
No, but this might be: Prelude> 13421773/134217728 - 0.1 1.4901161138336505e-9 I think that the language spec is sufficiently vague on this point that Hugs' behaviour is reasonable. When using floating point, you have to work with the numeric error rather than ignore it. Cheers, Andrew Bromage
On Monday, 2003-07-07, 01:37, CEST, Andrew J Bromage wrote:
[...]
On Sat, Jul 05, 2003 at 07:43:18PM +0200, Steffen Mazanek wrote:
Prelude> 0.1::Rational 13421773 % 134217728
That's allowed. The Rational only has to be correct to the limit of machine precision. (Incidentally, if it's any help in working out how this Rational was computed, the denominator is 2^27.)
The Haskell 98 Report, § 6.4.1: Similarly, a floating literal stands for an application of fromRational to a value of type Rational (that is, Ratio Integer). This only talks about "*a* value of type Rational", not about how this value is choosen for a given literal. But since it's a Rational, the most natural way seems to calculate an exact value. For a literal a1 ... an.b1 ... bm, the value could be a1 ... anb1 ... bm % (10 ^ m). Why isn't this forced by the standard?
[...]
Wolfgang
participants (9)
-
Andrew J Bromage -
Ashley Yakeley -
Derek Elkins -
Jerzy Karczmarczuk -
Jon Fairbairn -
ketil＠ii.uib.no -
Ross Paterson -
Steffen Mazanek -
Wolfgang Jeltsch