Wu-Decimal, a Decimal Package for Lisp - Download

Brought to you by Wukix, creator of mocl - Lisp for iOS and Android

Abstract

Floats (i.e. IEEE 754 numbers) are "considered harmful" for certain applications. A commonly used alternative is a decimal type. We were unsatisfied with the built-in capabilities of Common Lisp in this area, so we have developed a Common Lisp package we call Wu-Decimal. We are offering the source code under the 2-clause BSD license.

Contents

  1. Introduction
  2. Theory
  3. Usage
  4. Download
  5. Feedback

Introduction

Floats (i.e. IEEE 754 numbers) are an approximation. If you cash a $250 check at the bank they aren't allowed to give you $200 back and say that it is the approximate value of your check. Similarly, if a programmer is out there programming systems that compute, for instance, payroll, they probably should avoid using floats unless they're deliberately trying to exploit float errors to achieve some kind of Superman III-like outcome. This isn't to say that floats are inherently bad; they are of course critical in many applications such as games and scientific computing. Mainly, for those calculations that involve money and are not performance critical, floats offer few advantages and substantial disadvantages over BigDecimal/Decimal/decimal (Java/C#/python respectively) and the like. Why leave room for error if you can compute things perfectly at no loss in performance? For this kind of scenario decimals are the right choice.

Looking at the Decimal situation in Common Lisp, CL actually already has excellent support for numbers: arbitrary-precision integers, fractions, and even complex numbers. However, there really isn't a true Decimal type. Instead, you have the functions rational and rationalize, which will convert floats into fractions. Working with decimal numbers through rational/rationalize seems like a bit of a kludge. Numeric literals are first converted to floats before being converted to fractions, so (rational .1) can return 13421773/134217728 rather than 1/10 (this is actually the example given by the CL spec). Rationalize (in contrast with rational) apparently attempts to deduce what the true original number was, so that 0.1 actually returns 1/10, but even this involves first approximating .1 as a float. Even excluding input issues, as you work with the numbers and print them to the screen, the default (aesthetic) representation is still a fraction. You're thinking $29.95 and Lisp is printing out 599/20.

Desiring something a little cleaner, we at Wukix put together a solution that we think does the job in an elegant way. We were able to do this in a way that builds on top of CL's good support for numbers rather than working outside of it. Consequently all regular numeric operations work without modification; e.g. multiplication works with '*' like usual:

CL-USER> (* #$29.95 #$0.75)
#$22.4625

For reference, below is the result in SBCL using the default setting of single floats. Decide for yourself whether being off by 0.000002 is important.

CL-USER> (* 29.95 0.75)
22.462502

Theory

CL does not allow the end-user to overload the behavior of *, +, and so on. If we want to introduce our own numeric type and preserve the convenience of these operators, then we have to work within the framework of the existing types. In our case, that means storing values as Lisp ratios. It turns out that for a Decimal type, this actually works really well. If you ever learned about the sets of numbers and so on (integers, rationals, and reals, respectively), you might recall that the reals are super-infinite ("uncountable"), more infinite than the rationals . This might lead us to believe that we can't represent our hypothetical Decimal type using , but in fact we can. If we limit our considerations to only numbers that have finite decimal digits, which is all we really care about anyway, then we can represent our Decimal type as a subtype (conceptually speaking) of Lisp's Ratio type. This works fine as long as your payroll (or what have you) isn't defined in terms of Pi, or some other infinitely repeating number (though that would be "Googley"). We will call our hypothetical set of finite decimal numbers and define it as follows:

Which is to formally say that every number representable by our Decimal type has a corresponding fraction with a denominator that is a power of 10.

Reading/Parsing

captures our desired number set based on the intuitive notion that for any of our decimal numbers , we can construct a rational fraction of equal value by shifting 's digits leftward until we have an integer, and then we divide this integer by the appropriate power of 10 to make the fraction equal in value to . For example, 1.25 would become 125/100. This provides the basis for a reader macro: we parse the decimal number input and convert it to a Lisp ratio.

Printing

Now that we have a method of constructing a fraction from a decimal number, the remaining challenge is the reverse problem: printing a decimal number from a fraction. Since we are working with the existing types and representing our decimal numbers as Lisp ratios, we need some way to distinguish between ratios that can be printed as finite decimal numbers, and those that cannot. The goal is to obtain behavior like the following:

CL-USER> #$0.33 ;converts to 33/100 then is printed
#$0.33
CL-USER> 1/3 ;prints as a ratio since it would repeat otherwise
1/3
CL-USER> #$0.5 ;converts to 1/2 then is printed
#$0.5
CL-USER> 1/2 ;prints as a decimal since it does not repeat
#$0.5

Lisp gives us the ability to obtain the numerator and denominator from any ratio. However, to test decimal-ness we can't simply check if the denominator is a power of ten. Lisp reduces all ratios so that, for example, an input of 5/10 would become 1/2. Based on our definition of , we need some test that can determine whether or not there exists a fraction equal to the fraction at hand where is a power of 10.

To devise such a test, we first note that 10 is itself a composite number of . Similarly, will factor as . Since we assume they can only differ by the presence of some constant that will cancel out, i.e. . Going on the restriction that the denominator cb must be a power of 10, factoring cb as means b can only be some power of 2, some power of 5, or a product of some power of 2 and some power of 5. In other words, b is of the form , and applying c "fixes" the denominator so that m=n.

Now that we know what the denominator b looks like, we can test ratios to see if they belong to our set of decimal numbers or not. If they do not belong, Lisp can print them as ratios like usual. If they do belong, they can be passed to a function that will print them as decimal numbers. For the latter category, we accomplish this printing by finding . Once we have it, a decimal point can be inserted within the digits of its numerator to produce our printed representation.

Usage

Once you have installed and loaded the package, enable Wu-Decimal like so:

CL-USER> (wu-decimal:enable-reader-macro)
T
CL-USER> (wu-decimal:enable-decimal-printing-for-ratios)
NIL

After enabling reading and printing, you can use decimals with the '#$' macro:

CL-USER> #$10000.1234567890123456789
#$10000.1234567890123456789
CL-USER> (+ #$10000.1234567890123456789 2)
#$10002.1234567890123456789
CL-USER> 1/1000
#$0.001

Be aware that in the case of a ratio like 1/1000, it prints as a decimal as above. As mentioned in the theory section, this is a consequence of repurposing ratios for the decimal type, and applies to all ratios that can be printed completely as a decimal number (ratios that would be repeating forever, like 1/3 continue to print as ratios). If for some reason this is a problem, you can disable decimal printing with disable-decimal-printing-for-ratios.

CL-USER> (format nil "~A" #$99.95)
"99.95"

Aesthetic printing omits the '#$'.

Download

Please do not link to these downloads directly, as the URLs are subject to change. Instead, link to this page (or this download section within the page).

License

Wu-Decimal is offered under the 2-clause "simplified" BSD license, also known as the FreeBSD license.

Installation

Wu-Decimal uses ASDF or XCVB.

Feedback

We welcome any comments, suggestions, or bug-fixes. Please direct all correspondence to Javascript Required. Thank you.

© 2011 Wukix, Inc.