Rational Numbers

One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.

Copyright © 2011 Jay Reynolds Freeman, all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
EMail: Jay_Reynolds_Freeman@mac.com.

Scheme has a recommended but optional built-in feature that very few other programming languages have; namely, rational numbers in which the numerator and denominator are stored separately, so that reading and displaying numbers in traditional fractional form is possible and leads to sensible values. For example, if you type in

Wraith Scheme will note that the number as a fraction and will read in its numerator and denominator -- respectively 1 and 3 -- and store them both in an internal data structure that I call a long ratnum, that represents the number. Later on, if that number is to be written out, Wraith Scheme will write the numerator first, then a "/", and finally the denominator, so that what you will see will be

just as you typed it in.

Without this feature, even if you were using a language that recognized "1/3" as a number at all, probably the best you could hope for would be that on reading "1/3", the system would do a floating-point division of 1.00 by 3.00 and take the floating-point result to represent the number, so that what appeared when you printed it out might be something like

This last is actually close enough to 1/3 for many practical purposes, but if you start bandying it about, all of your friends who are mathematicians will sneer at you, and we can't have that, now can we?

Having this form of rationals allows you to do arithmetic with fractions in the form you learned in grammar school, so that for example

and so on. Computations with fractions are sometimes useful, both for practical purposes and for pure mathematical work, so you may find this capability handy now and then.

Wraith Scheme's implementation of this kind of rationals is less capable than the most general kind that the R5 report recommends. This tutorial describes some of its limitations, and also describes some related procedures that Wraith Scheme provides as enhancements.

The fundamental problem is that Wraith Scheme uses 64-bit signed integers to represent the numerators and denominators of fractions. That sounds pretty big -- the allowable range is from -9223372036854775807 through 9223372036854775807 -- but it isn't really: If you start doing arithmetic calculations with fractions, you are forever reducing things to lowest common denominators, and it usually doesn't take very many such reductions before the denominator gets too large for a 64-bit signed integer. Some Scheme implementations implement bignums, which are integers of arbitrary size. An implementation of rationals that stored numerator and denominator as bignums could represent any rational. Wraith Scheme does not have bignums, though, and I have not been planning on putting them in. (Let's be honest: I said for a long time that I wasn't going to put in complex numbers or rationals with long ratnums, and now Wraith Scheme has both of those, so who knows for sure. At any rate, there are no bignums in Wraith Scheme now.)

Furthermore, calculations with long ratnums are often complicated: They take more computer operations than the corresponding calculations with floating-point numbers, for example. Thus they are slow.

There are other issues with fractions that are more matters of appearance. First, it is difficult to present fractions in a clean-looking table -- they tend to have very different numbers of characters, and are hard to format neatly. Second, we are all mostly more familiar with numbers in decimal format than with fractions. (Quick, which is bigger, 25478319/76384402 or 31721/94818?) The conventional "display", "write" and "number->string" procedures of Scheme make it difficult to pull out a decimal representation of a number when you want one, though Wraith Scheme has some enhancements to help out. These matters are probably minor, though, compared to the 64-bit signed integer limitation.

In any case, my fix for all this was to try to set things up so that you can calculate with fancy rationals if you wish, but also to arrange that they will not crop up in engineering and scientific calculations where they are presumably unwanted and where the longer calculations might slow things down. I did this by arranging that most Wraith Scheme procedures that can in principle give a "long ratnum" style rational as an answer will not do so unless all of their inputs are also long ratnums. If you would like a shorter description for that, you might consider that long ratnums are anticontagious. (Forms of numbers that are contagious have the opposite property: Putting just one of a contagious numeric form into a calculation usually guarantees that the result will be in the same form. Floating-point numbers are contagious in most computer languages.)

Thus for example:

It is possible to use long ratnums as the real and imaginary parts of complex numbers, but the syntax is a little misleading if you are not used to it. For example,

is a number that might be represented in more conventional typography as

even though it reads as if it were

Unfortunately, the syntax requires the form "1+1/2i", whether it is clear or not. (The rule is that the imaginary part is printed out, followed immediately by "i".) I think that all that proves is that the designers of Scheme weren't thinking about complex numbers with imaginary parts expressed as fractions. Also unfortunately, it would be a bad idea for me to change numeric syntax in Wraith Scheme; if I did, then someone might try to read numeric output created by Wraith Scheme, while using another Scheme implementation, and the reads would fail.

Wraith Scheme has all of the special R5 Scheme procedures for dealing with rationals -- those are "numerator", "denominator", and "rationalize". You can read all about them in the R5 report or in the Wraith Scheme Dictionary. It also has a few more procedures, as enhancements.

First, since divisions like "(/ 1 3)" do not return long ratnums in Wraith Scheme, I have provided procedure "e::make-long-ratnum" as a substitute:

Procedure "e::make-long-ratnum" reports an error if either of its arguments is outside the range of a 64-bit signed integer. You won't need it if you are typing in a long ratnum as a constant -- for that purpose you just type in whatever fraction you want, like "1/3". Where this procedure will be useful is if you have calculated the numerator and denominator separately in a Scheme program, and want to make a long ratnum out of them.

Procedure "e::derationalize" divides the numerator of a long ratnum by its denominator and returns the result:

Procedure "e::coercible-to-long-ratnum?" asks whether an object can be coerced to a long ratnum; its primary use is likely with numbers, but it will accept any Scheme object as an argument. Procedure "e::coerce-to-long-ratnum-if-possible" performs the indicated coercion; the long ratnum that it returns is as close to the given number as Wraith Scheme can make it.

The "#i" in the last result is because the input contained a decimal point and so was presumed inexact.

One of the interesting mathematical uses of fractions is to create and manipulate continued fractions. Wraith Scheme has two procedures -- enhancements -- for dealing with continued fractions. Procedure "e::real->continued-fraction-list" accepts a real number in the range where it can be converted to a long ratnum using 64-bit signed integers, and returns a list of the integers in its continued fraction expansion. (Purists will note that there are two such lists for any given rational; the one provided by the implementation is the short one.)

Procedure "e::continued-fraction-list->real" accepts a continued fraction list, such as generated by "e::real->continued-fraction-list", and produces the indicated real number.

The return from "e::real-continued-fraction-list" means that 37/11 can be written as the continued fraction:

The two instances of "e::continued-fraction-list->real" just given comprise an example of the existence of two different continued fraction expansions for a given number; namely, 37/11.

-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)

Wraith Face