PEP 327: Decimal Data Type

[Josiah Carlson]

> Was your implementation the 'not too bad to get working' or the 'doing
> it well'?

I thought it did pretty well.  But then again, I didn't really much 
worry about it or use it much.  I merely tested to make sure it did the 
right thing and forgot about it.

> For instance, there is the greatest common divisor that you need for
> normalising the rationals. 
> 
> I used the Euclidean algorithm for the GCD. Not too bad, certainly
> better than using prime factorisation, but as I understand it doing
> the job well means using a better algorithm for this - though I never
> did bother looking up the details.

I also used Euclid's GCD, but last time I checked, it is a pretty 
reasonable algorithm.  Runs in log(n) time, where n is the maximum of 
either value.  Technically, it runs linear in the amount of space that 
it takes up, which is about as well as you can do.

> Actually, as far as I remember, just doing the arbitrary length
> integer division functions took me more than your 45 minutes. The long
> division algorithm is simple in principle, but I seem to remember
> messing up the decision of how many bits to shift the divisor after a
> subtraction. Of course in Python, that's already done.

Ahh, integer division.  I solved a related problem with long integers 
for Python in a programming competition my senior year of college 
(everyone else was using Java, the suckers) in about 15 minutes.  We 
were to calculate 1/n, for some arbitrarily large n (where 1/n was a 
fraction that could be represented by base-10 integer division).  Aside 
from I/O, it was 9 lines.

Honestly, I never implemented integer division in my rational type.  For 
casts to floats, 
float(self.numerator)/float(self.denominator)+self.whole seemed just 
fine (I was using rationals with denominators in the range of 2-100 and 
total value < 1000).

Thinking about it now, it wouldn't be very difficult to pull out my 1/n 
code and adapt it to the general integer division problem.  Perhaps 
something to do later.

> Maybe I was just having a bad day. Maybe I remember it worse than it
> really was. Still, 45 minutes doesn't seem too realistic in my memory,
> even for the 'not too bad to get working' case.

For all the standard operations on a rational type, all you need is to 
make sure all you have is two pairs of numerators and denominators, then 
all the numeric manipulation is trivial:
a.n = a.numerator * a.whole*a.denominator
a.d = a.denominator
b.n = b.numerator * b.whole*b.denominator
b.d = b.denominator

a + b = rational(a.n*b.d + b.n*a.d, a.d*b.d)
a - b = rational(a.n*b.d - b.n*a.d, a.d*b.d)
a * b = rational(a.n*b.n, a.d*b.d)
a / b = rational(a.n*b.d, a.d*b.n)
a ** b, b is an integer >= 1 (binary exponentiation)


One must remember to normalize on initialization, but that's not 
difficult.  Functionally that's how my rational turned out.  It wasn't 
terribly full featured, but it worked well for what I was doing.

  - Josiah