Andrew Koenig <ark@research.att.com>:

Eric> APL faced this problem twenty-five years ago. I like its Eric> solution; a `fuzz' variable defining the Eric> close-enough-for-equality range.

I used to like APL's approach, but I've changed my mind.

Part of the reason is that there are some places where unfuzzed comparison is essential, such as sorting. Another part is that fuzzy comparison destroys substitutability: If a==b, it is not always true that f(a)==f(b).

Much as I like APL, I'd rather use Scheme's numeric model.

Good points...but the fuzz variable could default to zero. It didn't in APL, which I always thought a mistake. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

Guido> [Andrew Koenig]

...

Much as I like APL, I'd rather use Scheme's numeric model.

Guido> I've heard that before, but I've also heard criticism of Guido> Scheme's numeric model. "It works in Scheme" doesn't give me Guido> the warm fuzzy feeling that it's been tried in real life. ...and "It works in APL" does? More seriously, there aren't that many languages with infinite-precision rationals, which means there aren't all that many precedents. I find the partial ordering among Python's types interesting. If we use "<" to mean "is a strict subset of", then int < long < rational (except perhaps on machines with 64-bit int, which opens a different can of worms entirely) int < float < rational float < complex Excluding complex, then, adding rational to the numeric types makes the numeric types a lattice. We could make all of the numeric types a lattice by adding a "complex rational" type: complex rational | \___ | \ rational complex / \ ____/ / \ / long float \ __/ \ / \ / int What's nice about a lattice is that for any two types T1 and T2, there is a unique minimum type T of which T1 and T2 are both subsets (not necessarily proper subsets, because T1 could be a subset of T2 or vice versa).

[Eric S. Raymond]

...

1) Should future division return rationals rather than floats.

+1 for returning rationals. It's the right thing -- and if it fails, it will fail noisily, right?

While I agree with the theoretical arguments, I have the practical fear that rationals could grow very big, rather quickly, in the course of a long computation involving them in various ways. By big, I mean the numerator and denominator of the fraction taken in isolation, not the number itself. Consider inversions of an integer matrices, approximations with truncated series, or worse things like, maybe, discrete Fourier transforms. Bigger rationals are, slower they become, and more memory they take. The danger is that programmers may get surprised or hurt by Python performance degradation, raising frequent and recurrent questions here and elsewhere. On the other hand, I would love if Python was not loosing precision on non-truncating integer division, so let me try a bit to destroy my own fears. On average, most programs will not use matrices of rational numbers, nor play with series. Moreover, most programs do not use so many different numeric variables anyway, nor perform long computations involving them. Many programs do not go beyond adding or subtracting one, once in a while! So, I would guess that _on the average_, using rational numbers might be acceptable and go almost unnoticed by most people. So it might be more worth accepting as a community to warn programmers who are more prone to numerical algorithms of the intrinsic dangers of integer division in Python. But those feelings are no proof of anything. How do we get the confirmation that using rationals in Python would be easy going and innocuous in practice, beforehand? It would surely be nice relying in such a feature! -- François Pinard http://www.iro.umontreal.ca/~pinard

But those feelings are no proof of anything. How do we get the confirmation that using rationals in Python would be easy going and innocuous in practice, beforehand?

By adding them to the language but as an isolated type. The right conversions should happen when you mix rationals with other types of numbers (int/long -> rational -> float -> complex), but no operations should return rationals unless a rational goes in. --Guido van Rossum (home page: http://www.python.org/~guido/)

Greg> 1/3 --> float Greg> 1//3 --> int Greg> 1///3 --> rational Greg> (Okay, a 3-char operator is a bit verbose, but I can't Greg> think of anything else that looks division-like just at Greg> the moment.) I can't resist: A one-l lama is a priest, A two-l llama is a beast, But I'll bet you a silk pyjama There isn't any three-l lllama. --Ogden Nash PS: When I first saw this poem, it was accompanied by a claim (in a footnote) that a three-l lllama is a substantial conflagration. -- Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

Greg Ewing <greg@cosc.canterbury.ac.nz>:

Andrew Koenig <ark@research.att.com>:

...

A one-l lama is a priest, A two-l llama is a beast, But I'll bet you a silk pyjama There isn't any three-l lllama.

--Ogden Nash

PS: When I first saw this poem, it was accompanied by a claim (in a footnote) that a three-l lllama is a substantial conflagration.

:-) !!!

I have a vision of an obscure corner of Tibet featuring an order of special firefighting lamas, ready at a moment's notice to jump on their llamas and race off to do battle with a lllama...

:-) By the way, the footnote read as follows: "The author's attention has been called to a type of conflagration known as a three-alarmer. Pooh."

And whenever I see "1/3" now I'm going to want to pronouce it "one lama three". What have you done to me?

Oh, ghods. You realize this is turning into a classic Jargon File entry, don't you? @hd{lama} @g{n.} [Python] The division operator /; thus 1/3 is pronounced "one lama three". Coined during and October 2002 on the Python-development mailing list. Someone proposed that /, //, and /// should stand for integer-, rational-, and float-valued division, and someone else quoted Ogden Nash's poem @uref{http://www.cs.rice.edu/~ssiyer/minstrels/poems/1080.html, The Lama}. Amidst talk of firefighting llamas in Tibet, the analogy stuck. Of course, I can't actually add this. The last three words aren't true. Yet.,, -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a>

"Eric S. Raymond" <esr@thyrsus.com>:

By the way, the footnote read as follows:

"The author's attention has been called to a type of conflagration known as a three-alarmer. Pooh."

This is getting weird. I did a Google search for "lllama" and found this, apparently related to some sort of roleplaying game: From: Alex Yeager (YeagerAW@maritz.com) Date: Mon, 25 May 1998 Type: Plot Name: Three-L Lllama Graphic: A building on fire. Quote: Ogden Nash was wrong! They DO exist! Text: Disaster! This is an Instant Attack to Destroy any Place. Its Power is 12, increased by four for every undrawn Plot you throw onto the blaze. If the Place is Coastal, it may spend its token to defend itself. If the attack succeeds, the target is Devastated. If it succeeds by more than 6, the target is destroyed! Quote2: So where do I claim those silk pajamas?... Requirements: none Illamanated Conspiracy Proposed by "Yeager, Alex" (YeagerAW@Maritz.com) on Mon, 25 May 1998. So, was this Lllama spell inspired by the "three-alarmer" pun, or is it just a strange coincidence? Or is it some secret plot by the PSU to stop us sleeping at nights? Inquiring minds probably don't really want to know... Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

On Thursday 03 October 2002 02:42 am, Greg Ewing wrote: ...

1///3 --> rational

(Okay, a 3-char operator is a bit verbose, but I can't think of anything else that looks division-like just at the moment.)

1\3 ... ? Alex

Alex Martelli wrote:

On Thursday 03 October 2002 02:42 am, Greg Ewing wrote: ...

...

1///3 --> rational

(Okay, a 3-char operator is a bit verbose, but I can't think of anything else that looks division-like just at the moment.)

1\3 ... ?

I predict this will be the Perl 6 solution if they run into this problem: http://www.myfonts.com/Character00F7Style1150.html Today, it has a certain impractical elegance, which is not usually a phrase I associate with Perl. But a few years from now it may be practical. Paul Prescod

[Greg Ewing]

Maybe there should be a separate operator for rational division?

1/3 --> float 1//3 --> int 1///3 --> rational

(Okay, a 3-char operator is a bit verbose, but I can't think of anything else that looks division-like just at the moment.)

I much like Emacs Calc usage of 3:2 or 1:1:2 (no embedded space) for a fraction constant, read or printed. I find this more legible and comfortable to read than 3/2 or `1 1/2'. There is a Calc setting to decide if division generates floats or fractions, but Guido is probably right in choosing that `/' should not be magical enough to produce rationals. One might presume that introducing `:' between numbers at the syntactic level has just no chance to ever work. But _maybe_ it could be more tractable at the lexical level without bringing too much confusion, and for numerical _constants_ only -- 3:2 is one number, has never been two. Rationals could be got through a cast or constructor, or by introducing rational objects into the computation, like rational constants would be. -- François Pinard http://www.iro.umontreal.ca/~pinard

[Guido]

I think the slice notation e.g. x[1:4] kills that idea.

Well, at least {'a':'b', 1:2:3:4:5:6} is unambiguous <wink>. not-to-mention-attractive-ly y'rs - tim

Greg> Guido: >> I think the slice notation e.g. x[1:4] kills that idea. Greg> Maybe if ":" were a sliceobject-creating operator usable anwyere, Greg> not just in [...], and you added arithmetic methods to Greg> sliceobjects so you could use them as rationals... Does x[1:4] return a slice out of x or x[rational(1,4)]? Skip

Skip> Does x[1:4] return a slice out of x or x[rational(1,4)]? Greg> If rationals and slice objects were the same thing, Greg> it wouldn't matter! But then how would you distinguish between x[1:4] and x[2:8]? -- Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

Greg> If rationals and slice objects were the same thing, Greg> it wouldn't matter! Andrew> But then how would you distinguish between x[1:4] and x[2:8]? Greg> Well, if you reduced the rational to lowest terms you Greg> would have to keep the original values around for when Greg> you were using it as a slice object... In that case, wouldn't you have a situation where a==b, a and b are the same type, but x[a]!=x[b]? -- Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark

Greg Ewing <greg@cosc.canterbury.ac.nz> writes:

Andrew> In that case, wouldn't you have a situation where a==b, a and Andrew> b are the same type, but x[a]!=x[b]?

Yes. Not such a good idea, I suppose.

I've just had another idea:

{2/3}

2r/3 would be nicer IMO. -- David Abrahams * Boost Consulting dave@boost-consulting.com * http://www.boost-consulting.com

Guido van Rossum <guido@python.org> writes:

...

2r/3 would be nicer IMO.

Or 2/3r. (The r binds only to the 3, but of course the binary operator rules kick in with the same effect.)

Frankly, this is the only sane notation for rationals I've seen so far in this discussion.

I liked 2r/3 because it gives the sense that r/ is the rational division operator, where // is the whatever-the-hell-it-is division operator. I don't know if it works in the grammar to be able to say x r/ y though. Does it? -- David Abrahams * Boost Consulting dave@boost-consulting.com * http://www.boost-consulting.com

Guido van Rossum <guido@python.org> writes:

...

I liked 2r/3 because it gives the sense that r/ is the rational division operator, where // is the whatever-the-hell-it-is division operator. I don't know if it works in the grammar to be able to say

x r/ y

though. Does it?

That would require changes to the tokenizer.

But I am against r/ on different grounds: it's not the kind of grouping of symbols that one would expect. People are used to 12L, 1j and then it's a small step to 2r.

You're right. And now that I look at it, if 2r is a rational with value 2, and if you can divide ints by rationals, then 1/2r makes a lot of sense. I wasn't looking at it that way (but I am now, and liking it).

There were also precedents for r"..." and u"...": C's w"...". If you want a precedent for 2/, you'd have to search in Lisp or Forth or other (nearly) grammar-less languages.

Oh, please, don't remind me about those funky Forth symbols. I guess it has less to do with grammar than with lexemes, though. -- David Abrahams * Boost Consulting dave@boost-consulting.com * http://www.boost-consulting.com

Noting that Scheme has two sets of optional numeric literal prefixes: #b #o #d #h number is binary, octal, decimal (the default), or hex #e #i number is exact or inexact This avoids conflating exactness with representation, and, e.g., #e#b1.001 is exactly 9/8 (although that Dr. Scheme allows a radix point in a binary literal appears to be an extension of the Scheme std). By default, a numeric literal is inexect iff it contains a radix point or an exponent, but #e or #i can override that.

(exact? 2) #t (exact? #i2) #f

(exact? 6.02e23) #f (exact? #e6.02e23) #t

I think this works very well. The same rule about default exactness would be appropriate for Python too, and an r suffix meaning what a #e prefix means in Scheme would be a fine idea by my lights (the effect of an #i prefix can be gotten via including a decimal point for decimal literals, and inexact literals in other bases are rarely useful).

[Guido]

I don't think Python needs the full matrix of exact and inexact versions of all kind of numbers. I see not enough need for inexact ints or rationals, nor for exact floats or complex numbers.

#i3 is "an inexact integer" in Scheme, but that says nothing about how it's *implemented*. In fact, it's almost certainly implemented as a float, much as #e3.0 is almost certainly implemented as an integer. Scheme hides the internal implementation, so that the programmer doesn't need to care; the flip side is that programmers who do care can't force the issue in a portable way.

So I'd like to continue our partition of numeric types as follows:

exact | inexact ------------------------------------ int/long rational | float complex

But we can do this, which is pretty much what Tim proposes in the end:

1 -> int 1.0 -> float

1r -> rational 1.0r -> rational

Yes, that's exactly what I was proposing. s/r/#i/ and it's the same as Scheme's rules, although Scheme doesn't promise anything about internal representation.

If we ever add a fixed-point decimal type, that could use 'f' for a suffix. If we ever add a floating-point decimal type (like the one Aahz is working on -- I mistakenly called it a fixed-point type before) then it could use 'd' as a suffix, or it could become the default and we could use 'b' as a suffix to get binary floating point.

Etc.

But I also agree with a recent trend in this thread: let's not rush to add syntax. Let's first add rationals to the library.

I hereby declare this thread closed. (Ha, ha. :-)

You should have put that sentence first -- my editor still doesn't go backwards <wink>.

I've just had another idea:

{2/3}

This can't be confused with a dict, because there's no ":" in it.

On the slight chance that you're serious, I'd like to reserve {...} without colons for set notation, see PEP 218. --Guido van Rossum (home page: http://www.python.org/~guido/)

Greg Ewing wrote:

I have to agree that would be a better use for them.

So, I'm now reduced to suggesting

<2/3>

Is that going to be easy to parse?

...

...

1 <5/2> -3 1

Cheers, Brian

...

...

...

...

"GE" == Greg Ewing <greg@cosc.canterbury.ac.nz> writes:

GE> I have to agree that would be a better use for them. GE> So, I'm now reduced to suggesting GE> <2/3> Everyone's missing the obvious: 2÷3 :) -Barry

Greg Ewing wrote:

So, I'm now reduced to suggesting

<2/3>

How about 2r3, which could be pronounced "2 rational 3" and is syntactically very similar to the universal 2e3? Paul Hughett

"M.-A. Lemburg" <mal@lemburg.com> writes:

What's so hard about rat(2,3) ?

And if that doesn't look right, simply do:

R = rat(1,1)

2/R/3

This works without any changes to the language.

My thoughts are moving towards that. I also wouldn't especially mind seeing rationals added to the standard library instead of the core, though I'm not sure how that effects Numeric. The two best suggestions (IMHO) I've seen so far are the above and Guido's 2/3r where that is actually the int 2 over the rational 3r. -- Christopher A. Craig <list-python@ccraig.org> "Going to school make a person educated, any more than going to a garage makes a person a car" Slashdot

...

...

...

...

"TW" == Thomas Wouters <thomas@xs4all.net> writes:

TW> I have to agree with MAL. I know, rationally, why a rational TW> literal (or is it literal rational ?) is desirable, but it TW> feels like clutter and all of the proposed syntactic solutions TW> strike me as bad ideas. I'd much rather have the above (which TW> deals with everyone else's favorite data type and their TW> requests to have builtin support for it at the same time) than TW> a not-quite-perfect way to spell a rational literally. It seems to me that Python has a tradition of deferring syntax decisions until way after the more important issues have been worked out. Perhaps we should do the same here, IOW, get the rational library into the core and see if a rational literal makes that big a difference for readability or maintainability. It may not, but then at least we'll still have rationals. -Barry

On Tue, Oct 08, 2002 at 08:41:31AM -0400, Paul Hughett wrote:

Greg Ewing wrote:

...

So, I'm now reduced to suggesting

...

<2/3>

How about 2r3, which could be pronounced "2 rational 3" and is syntactically very similar to the universal 2e3?

2e3 may be universal, I wouldn't say it's very universally used. I personally never use the e-notation, and I can't say I find it very readable. Who do we expect to use rationals ? Is it something we want newbies to learn ? Will high/grade-school students with not compsci/math background to recognize the e-notation be using rationals ? I'm not going all happy-dayzy about rationals in the first place, but I know that is because I understand the implementation and tradeoffs of floating point, and they are what I want :) I'd also say rational-literals are not that important. Looking at my own Python code, I very rarely need a floating-point literal to start with. Strings, plenty, dicts and lists fairly often, integers every now and then, but floating point numbers very rarely, and almost all of them are just '0.0' or an integer expressed as float to force float-division. Most of my float objects come from (library) functions that return them. If we expect newbies to prefer rationals over fp, we need syntax that is clear to them (which may very well be just 'rat()'.) If we expect hard-core mathers like Tim and Moshe and Chris Tismer and even Guido to use them, I'd say we don't need syntax support for them and can just live with rat(). And I have to say some of the proposals for literal rationals I saw were very disturbingly sick. Some of you need help, and some need to spend less time using XML :-) Beautiful-is-better-than-ug'ly y'rs, -- Thomas Wouters <thomas@xs4all.net> Hi! I'm a .signature virus! copy me into your .signature file to help me spread!

On Tue, Oct 08, 2002 at 03:55:49PM +0200, Thomas Wouters wrote:

I'd also say rational-literals are not that important. Looking at my own Python code, I very rarely need a floating-point literal to start with. Strings, plenty, dicts and lists fairly often, integers every now and then, but floating point numbers very rarely, and almost all of them are just '0.0' or an integer expressed as float to force float-division. Most of my float objects come from (library) functions that return them.

Having nice-looking literals is important even if they are not actually typed in the source code too often. The literal form is also the repr() for all built-in numeric types so far. I don't think we should break that. What would your like to see as the repr() of a rational number? The answer to this will also determine what you type in your source. Note that repr(n) is not necessarily str(n):

...

...

repr(f) '0.59999999999999998' str(f) '0.6'

So we could have:

...

...

repr(r) '3/5r' # or 'rat(3, 6)' str(r) '3/5'

Oren

On Tue, Oct 08, 2002 at 12:09:57PM -0400, Guido van Rossum wrote:

...

'3/5'

I'd like at least one of those return '0.6' or '0.6r'.

Why should any of them go through a potetially lossy transformation? If you need to approximate a ratio as a finite decimal fraction it should be explicit: str(float(r)). I think it will also make a good visual cue to always use rational notation for rationals and decimal fractions for floats. The result of repr() should eval() back to exactly the same object. The result of str() should be the 'pretty' representation because this is the form displayed by print statements and %s formatting. I find '2/3' prettier than '0.666666666667' pretty-is-in-the-eyes-of-the-beholder-ly yours, Oren

On Tue, Oct 08, 2002 at 10:18:46PM -0400, Tim Peters wrote:

...

If you need to approximate a ratio as a finite decimal fraction it should be explicit: str(float(r)). I think it will also make a good visual cue to always use rational notation for rationals and decimal fractions for floats.

The trailing 'r' *is* rational notation, and stuff like this probably isn't a good idea for str():

I'm not sure I follow. What 'stuff' is not a good idea for str() and why? By rational notation I meant the division form, not the trailing r or any other syntax used by the language to indicate the type.

...

#e6.02e-45 301/50000000000000000000000000000000000000000000000

6.02e-45r would be clearer to virtually anyone.

Again, I'm not sure I follow your logic. How likely is an arbitrary rational number to have a denominator ending with lots of zeros?

...

(+ 312 (/ 1 3)) 937/3

would likely be clearer to virtually anyone as 312+1/3r too.

Yes, in this case it is much clearer.

But most of all, I agree that if you're working with rationals, you don't want to lose information silently, not even in a "pleasant" string.

...

The result of repr() should eval() back to exactly the same object. The result of str() should be the 'pretty' representation because this is the form displayed by print statements and %s formatting. I find '2/3' prettier than '0.666666666667'

2/3r works for both for me. 0.666...7 doesn't work for me at all as a stringification of a rational (if I want to approximate, I'll ask for an approximation).

Works for repr, str, or both? The str() of long omits the trailing L. I don't think rationals should show the trailing r. Oren

Tim Peters <tim.one@comcast.net> writes:

...

2/3r works for both for me. 0.666...7 doesn't work for me at all as a stringification of a rational (if I want to approximate, I'll ask for an approximation).

I agree. I initially thought about returning a decimal with str(), but for that reason chose not to. It might be nice to have a method that returned the best floating point decimal approximation to within n decimal digits or shorter, but I don't want a builtin to make an arbitrary decision on where to cut off precision.

I do like the idea of str() returning the form 5+3/2r, though.

Well, that would completely kills any possibility of ever making 1/3 return a rational (currently the main argument against it is the expectation amongst the current user base that it will be a float). I really don't think that this would be reasonable at all: Python 3.0 (#2345, Mar 12 2005, 11:32:10) Type "help", "copyright", "credits" or "license" for more information.

...

...

print 25/7 25/7

--Guido van Rossum (home page: http://www.python.org/~guido/)

Tim Peters <tim.one@comcast.net> writes:

If you haven't yet, you should strive to understand Moshe Zadka's prototype rational implementation in Python CVS nondist/sandbox/ (which has all the approximation functions you could need). Unfortunately, the SourceForge Python Numerics list:

https://sourceforge.net/mailarchive/forum.php?forum_id=2280

appears to have lost almost all the voluminous discussions that went into that, retaining mostly a random sampling of spam.

I have read the module. I really liked his (your?) trim code and I used that algorithm in cRat and my rational patch. I don't think I'd use any of that for generating decimal (or binary) float approximations, though. Trim introduces some error into the calculation which is then furthered by the float division. You can provably generate the closest scaled long of a given size (and thus hopefully the closest float) with one shift and one long integer division. -- Christopher A. Craig <list-python@ccraig.org> "It mearly pleases me to behave in a certain way to what appears to be a cat" -- The Ruler of the Universe (The Restaurant at the End of the Universe)

Oren Tirosh <oren-py-d@hishome.net>:

What would your like to see as the repr() of a rational number? The answer to this will also determine what you type in your source.

I think it's the other way around -- what you type in the source determines what repr() should return. If a constructor, e.g. rat(2,3) is used, then the repr() should be likewise. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

[Guido van Rossum]

...

But _maybe_ it could be more tractable at the lexical level without bringing too much confusion, and for numerical _constants_ only -- 3:2 is one number, has never been two.

I think the slice notation e.g. x[1:4] kills that idea.

And it kills it dead indeed, at least, in my opinion. [M.-A. Lemburg]

Are you sure that you really want a special syntax for this rather than just a simply constructor like rat(2,3) ?

This is what I currently do whenever I need rationals. It might not be as elegant as the `:' would have been, but it works well in practice. I guess I would prefer ^rat(2, 3)" over any non-elegant or non-natural notation for rational constants. We do not necessarily ought to have a special notation hardwired in Python syntax. If Guido was adding complex numbers today instead of long ago, I wonder if he would allow a special notation for them, or just suggest a constructor.

Note that intution isn't going to help here because you are missing a precision indicator. mxNumber has a constructor called FareyRational() which converts floats to rationals: [...]

Interesting, I'll save it. I use continued fraction expansion to get the "best" rational fitting a float within a tolerance, and wonder how Farey will be similar/different. Tim will surely tell us, out of his head! :-) -- François Pinard http://www.iro.umontreal.ca/~pinard

>> If Guido was adding complex numbers today instead of long ago, I >> wonder if he would allow a special notation for them, or just suggest >> a constructor. Guido> At the time I believe there was heavy pressure from the Numeric Guido> crowd to allow a special notation. I'm not so sure if I should Guido> have given in though. However, 1+4j can be peephole optimized into a compile-time constant whereas complex(1,4) can't. This is generally not a big deal, but to people who deal with complex numbers a lot (and tend to be more sensitive to optimization issues) it can be. I believe when I tested my peephole optimizer using pybench several years ago, the complex number tests showed the most improvement because I could collapse constant expressions. Of course, people using lots of complex numbers probably initialize their complex constants outside of loops. ;-) Skip

Tim Peters wrote:

[François Pinard]

...

... Interesting, I'll save it. I use continued fraction expansion to get the "best" rational fitting a float within a tolerance, and wonder how Farey will be similar/different. Tim will surely tell us, out of his head! :-)

Your wish is granted <wink>: Moshe Zadka's prototype implementation of rationals is still sitting in Python CVS nondist/sandox/rational/. Its _trim function is one I worked on with him, and uses c.f. expansion to find "the best" rational approximating a given rational, among all rationals with denominator no larger than argument max_d. The Farey method is almost identical, except potentially much slower. It's almost what "the usual" continued fraction algorithm would do if you couldn't use integer division to do a whole bunch of steps in one gulp; e.g., whenever the c.f. expansion gets a partial quotient of N, the Farey method does N distinct steps.

But isn't division much more costly than addition and multiplication if you have long integers to deal with ? (I can't tell, because the works are done by GMP in mxNumber)

About "almost identical": c.f. expansion produces a sequence of rationals alternately smaller and larger than the target, each one (much) closer than the last. The Farey method also looks at rationals "between" those; _trim does too, but only at the endpoint, when max_d is between the denominators of two successive c.f. convergents.

Moshe's package also has an _approximate function, to find "the smallest" rational within a given absolute distance of an input rational; that's probably closest to what you're doing now. _trim answers questions like "what's the best approximation to pi with denominator no greater than 6?". Neither of the adjacent convergents 3/1 and 22/7 is the correct answer to that; 19/6 is correct. Note that the c.f. expansion gets 22/7 because the previous two convergents were 1/0 and 3/1, the next partial quotient is 7, and then the next convergent is

1 + 3*7 22 ------- = -- 0 + 1*7 7

If the partial quotient *had* been 6, it would have given 19/6 instead. That's what the tail end of _trim deduces.

The Farey method does this one step at a time, going from (and skipping to then end of process)

1/0 3/1

as bounds to

3/1 4/1

and then

3/1 7/2

and then

3/1 10/3

and then

3/1 13/4

and then

3/1 16/5

and then, finally

3/1 19/6

Especially when coded in Python, it's much more efficient to deduce this in one gulp (via exploiting division).

How useful are .trim() and .approximate() in practice ? If they are, then I could put them on the TODO list for mxNumber. -- Marc-Andre Lemburg CEO eGenix.com Software GmbH _______________________________________________________________________ eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/

Tim Peters wrote:

[M.-A. Lemburg]

...

... But isn't division much more costly than addition and multiplication if you have long integers to deal with ? (I can't tell, because the works are done by GMP in mxNumber)

There's no real bound on how large partial quotients can get, and rationals can grow extremely large. Dividing once to get, e.g., 10000, is enormously cheaper than going around a Python loop 10000 times, and creating and destroying several times that many temporary longs, just to avoid one relatively fast C-speed longint division with a small quotient.

Well, I'm working with GMP here, so temporary longs are not that expensive (plus they reuse already allocated memory). That's why I was asking.

It's essentially the same as figuring out "the fastest" way to code a gcd, and that's a very tricky problem at the Python level. Partial quotients are *usually* 1, and then subtraction is cheaper, and it's also possible to meld both approaches to exploit that.

I see. Thanks.

...

... How useful are .trim() and .approximate() in practice ?

You're going to get as many responses to that as Guido got to his query about how mxNumber users like its type hierarchy <wink>.

:-)

...

If they are, then I could put them on the TODO list for mxNumber.

They're useful for people who want to mix rationals with approximation, and that's an unlikely intersection outside of expert use. _trim is essentially what fixed-slash and floating-slash arithmetics use under the covers to keep rigorous bounds on memory use, in exchange for losing information. How useful is that in practice? Beats me; it depends so much on whose practice we're talking about <wink>.

Point taken. I just added the Farey algorithm to mxNumber because it seemed like a nice way of limiting the size of the integers involved in the rational representation of floats. It sometimes even helps to e.g. backpatch rounding/representation errors in floating point calculations when you know that your dealing with small denominator rationals:

...

...

1/3.0 0.33333333333333331 FareyRational(1/3.0, 100) 1/3

-- Marc-Andre Lemburg CEO eGenix.com Software GmbH _______________________________________________________________________ eGenix.com -- Makers of the Python mx Extensions: mxDateTime,mxODBC,... Python Consulting: http://www.egenix.com/ Python Software: http://www.egenix.com/files/python/

Note that I started to work on mxNumber to get a feeling for how well rationals et al. fit the existing world. Turns out that having separate types is a goo[d] thing.

Any mxNumber users out there who have experience with mxRational? --Guido van Rossum (home page: http://www.python.org/~guido/)

Raymond Hettinger <python@rcn.com>:

The HP32SII calculator implements a useful rational model using flags and a maximum denominator register. If the first flag is clear, fractions are have denominators upto the maximum value. If only the first flag is set, fractions always use the maximum denominator as the denominator and are then reduced (i.e. if the max is 8, then .5 is represented as 1/2 and .1 is represented as 1/8).

I can see that being useful when you're doing calculations with, e.g. measurements in 64ths of an inch and you don't care if anything smaller than that isn't quite exact. But I get the impression that the folks who want rationals in Python want them precisely because they're *always* exact. If you couldn't rely on them to always be exact, it would defeat the purpose. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

Raymond Hettinger <python@rcn.com>:

For that, I propose maxdenom=None to let the rationals grow without bound.

A global setting for this would have all the same problems we've just gone over in relation to the "fuzz" setting. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+

Raymond Hettinger wrote: ...

There should be a builtin variable (overriddable within some inner scope) for a maximum denominator magnitude. It should default to some value where performance tanks. If set to None, then no limit would apply.

The HP32SII calculator implements a useful rational model using flags and a maximum denominator register. If the first flag is clear, fractions are have denominators upto the maximum value. If only the first flag is set, fractions always use the maximum denominator as the denominator and are then reduced (i.e. if the max is 8, then .5 is represented as 1/2 and .1 is represented as 1/8).

Makes very much sense to me. -- Christian Tismer :^) <mailto:tismer@tismer.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 pager +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/

[Guido]

... Not clear at all. ABC did this, and we found that a common problem was that a program doing numeric stuff would run very slowly (i.e. the opposite of failing noisily).

Time for my yearly repetition of that I believe that, at least for me, many (perhaps most, but not all) of the surprises in ABC were due to that "floating-point literals" (like 6.02e23) were also treated as exact rationals.

... The problem with a fuzz variable is that there's only one, and library modules may end up fighting over the right value for what they are trying to accomplish. Making it a per-module variable causes the opposite set of problems.

Knuth defines a much more sophisticated notion of "fuzzy comparison" for floats (TAoCP Vol 2). That never caught on either. I'm never clear on what people think they're *solving* with suggestions like these -- binary floating-point is so horrendously at odds with "common sense" regardless that it solves nothing. In APL there was a particular reason for it, in order to create arrays of booleans from whole-array comparison operators efficiently, but that didn't make it a useful *scalar* gimmick there either, and in my brief APL days the damn fuzz destroyed more careful numeric algorithms than it helped for that reason.

I'm all for adding rationals to the language -- but I'd like them segregated until we have a lot more experience with how they behave.

They behave most like precocious children with voracious appetite <wink>.

Christopher> For what it's worth, the current implementation is Christopher> nothing this complicated. Like every other numeric Christopher> operation, compares of rationals with floats coerce to Christopher> floats. So as a result rational(x)==float(x) iff Christopher> float(rational(x))==float(x). Attractive as this strategy may be from an implementation viewpoint, it means that comparisons do not have the order-relation properties that algorithms such as sort expect. A similar problem exists today for comparisons between float and long, by the way. -- Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark