Monday, February 18, 2008

Typesafe Ranged Integers in Scala

For the past few weeks I've been working on a basic numeric library for Scala for eventual contribution to the Scalax project. My goal is to create an extensible, type-safe library that provides numeric types that are easy to use and more closely resemble their mathematical foundations than the primitive operations on which they are built. My initial focus has been on building a working rational numbers implementation with unlimited precision integers. However, today on the Scala mailing lists, someone raised the issue that Scala's use of primitive numbers doesn't belong in such a high-level language. When I read this, I thought "Hmmmm, my library helps with that."

Integer Underflow and Overflow

First, let's consider integer underflow and overflow. The standard Java/Scala integer type is a 32-bit twos-complement signed integer. That means it can representing numbers between 2147483647 and -2147483648 inclusive. Often times this is plenty range, so what we really want is for exceptions to be thrown when underflow and overflow. So consider the following:

scala> import scalax.math.Int32Domain._
import scalax.math.Int32Domain._

scala> val a: Int32 = 5
a: scalax.math.Int32Domain.Int32 = 5

scala> val b: Int32 = 7
b: scalax.math.Int32Domain.Int32 = 7

scala> a + b
res0: scalax.math.Int32Domain.N = 12

scala> a * b
res1: scalax.math.Int32Domain.N = 35

scala> val i: Int32 = 2147483647
i: scalax.math.Int32Domain.Int32 = 2147483647

scala> i + 1
java.lang.ArithmeticException: result exceeds maximum value: 2147483647
at scalax.math.Int32Domain$Int32.checkRange(int32.scala:55)
at scalax.math.Int32Domain$Int32.$plus(int32.scala:60)
at .(:8)
at .()
at RequestResult$.(:3)
at RequestResult$.()
at RequestResult$result()
at sun.reflect.NativeMethodAccess...

Magic! Overflow has been detected. Well, not quite magic. The way it works (and I'm sure it could work much, much better, I just through this together tonight) is that it converts the 32-bit integers into 64-bit integers prior to calculations, performs the calculations, then checks the result to ensure that it is within range. If it is within range, then the result is converted back into a 32-bit integer and returned. Between the usage of an object instead of a primitive and all this extra work for range checking, this class is probably at least an order-of-magnitude slower that using primitive Ints.

Bounded Ranges

Now let's consider bounded ranges. In order to accomplish this, we simply create an object that extends Int32 and overrides its minimum and maximum value.

scala> object SmallDomain extends scalax.math.Int32Domain {
| override val max: N = 10
| override val min: N = -10
| }
defined module SmallDomain

scala> val d = SmallDomain.Integer(5)
d: SmallDomain.N = 5

Now we have a domain that is limited from -10 to 10 inclusive. Attempting to mix integers from this domain with integers from other domains will yield a type error:

scala> i + d
:9: error: type mismatch;
found : SmallDomain.N
required: scalax.math.Int32Domain.N
i + d
^

scala> d + i
:9: error: type mismatch;
found : scalax.math.Int32Domain.Int32
required: SmallDomain.N
i + a
^

Even if you had a Int32 within the range of SmallDomain, you would still receive the type error. Also, as you can see, Int32 will not allow itself to be mixed with an integer from SmallDomain. If you look at the code (which I'll publish soon, I promise) for Int32Domain and its superclasses, you will see a lot of complex stuff involving mixins and type constructors. However, the end class is easily extensible by the user and still provides good type safety.

Rationals

I mentioned rationals at the beginning of this blog, so I thought I would give a little sneak-peak:

scala> import scalax.math.BigRationalDomain._
import scalax.math.BigRationalDomain._

scala> val a = Integer(3)
a: scalax.math.BigRationalDomain.IS = 3

scala> val b = Integer(7)
b: scalax.math.BigRationalDomain.IS = 7

scala> a / b
res0: scalax.math.BigRationalDomain.N = 3/7

scala> a.inverse
res1: scalax.math.BigRationalDomain.N = 1/3

scala> a.inverse * a
res2: scalax.math.BigRationalDomain.N = 1

scala> (a / b)^2345
res3: scalax.math.BigRationalDomain.N = 70687450412160609527952431393691553815800419127671886519112946722799601077076407951140254943159198319665943578284183744314587093153151823879346566151398437630838022610858501398173872472014103905434680267558985498302895510754430260294086995134629615707980341285332639084519209821403179213183556756416404920769037158823806045214292550723098516538040...

scala> a * b
res4: scalax.math.BigRationalDomain.I = 21

scala> Integer(3) / Integer(6)
res5: scalax.math.BigRationalDomain.N = 1/2

Notice how an integer times an integer equals an integer, but an integer divided by an integer equals a rational. This is because integer is a subtype of rational, because in all integers are rationals, but not all rationals are integers.

More to come soon!

Sphere: Related Content

10 comments:

Chris W. Hansen said...
This comment has been removed by the author.
Chris W. Hansen said...

I'm sure you know how to improve your over/underflow detection, but here's a link:
http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/overflow.html

I think this library is a great idea, and I'm glad you are contributing. I hope to contribute to a project such as scalax myself in the near future.

Viktor said...

Good looking stuff Mr Engbrecht!

Erik Engbrecht said...

Chris,
I at one time probably knew a good way to detect overflow but I don't know. A couple weeks ago I did some research on doing it in Java, and I mostly found complaints about how even on processors that have over/underflow bits Java provides no way to access them. I was also in a hurry to throw together this post, so I didn't do any more research.

Anyway, thanks for the link. I'll be sure to put a respectable method of overflow detection in before making it public.

Anonymous said...

Hi Erik. James Watson here. I think something like this might work for under/over detection. Sorry it's Java. I've let my Scala skills lapse lately.

int result = a + b;

if (b > 0 && a > result) throw new RuntimeException("overflow");

if (b < 0 && a < result) throw new RuntimeException("underflow");

Anonymous said...

Good looking stuff Mr Engbrecht!

Personally, I always use the BigInt type in order to avoid overflow. I think, this should be the default implementation of int. Perhaps, the code would be a bit slower. But it would be less error-prone. This is the important point.

Erik Engbrecht said...

James,
That works for addition, but not for multiplication. But it is a faster way for addition.

Anonymous - Yup, I think in general inifite-precision integers (as in memory-bounded integers) are the way to go.

Anonymous said...

Erik-

Yeah, that won't help for multiplication but you might be able to do something with doing a division and make sure the result is what you started with. I'm not sure this would be any faster than what you've got though.

-James

Chris W. Hansen said...

Re: overflow detection

Addition:
- can only occur if both have the same sign, which means
1. both positive and result is negative
2. both negative and result is positive

Multiplication:
The magnitude of the result must be greater than each of the magnitudes of the multipliers. In order to determine this, we could use Math.abs, except that Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE, so it fails on this boundary case.
This is on the right track, but I'm sure there is a better way.

posicionamiento web natural said...

Thanks for your post, very useful information.