Package math

Class PrimeSieve

For a period I worked with modular arithmetic especially with the ring of integers modulo n and in this branch of mathematics prime numbers play a crucial role.

I needed to know which numbers of a given interval was prime, the smallest prime greater than a given number or the greatest prime less than a given number and I had to do it quickly, possibly in O(1).

For this purpose I developed the PrimeSieve. It is an implementation of the algorithm known as Sieve Of Eratosthenes. Numbers are represented using bits. The implementation is optimized so that only odd numbers that are not multiples of 3 are represented. This allows the PrimeSieve to find and keep track of all primes between 0 and 412316859839. This limit is determined by the greatest size of an array in Java. According to the Java documentation this size is Integer.MAX_VALUE but, by testing this class, I found out that it is actually Integer.MAX_VALUE - 2.

Of course this limit can be bypassed using multiple arrays, but it is out of the purpose of this class. Besides, allocating such a big array, will need 16Gb of memory and, even if this class takes advantage of the Java Fork/Join framework to operate in parallel, sieving all those primes will take a remarkable amount of time. I have tested this class on a AMD FX(tm)-8350 Eight-Core Processor and it took an average of 166446ms to find all primes less or equal to 412316859839 i.e. it was able to sieve about 2500 million numbers per second.

Classes CU, BI and BD

First of all I had to deal with java.lang.BigDecimal and java.lang.Comparable and it’s such a pain! The lack of support for comparing and performing mathematical operations with objects in Java is really frustrating.
A statement like:

if( a + b < c && c < d + e )
  // do something...

assuming to consider null to be less than non-null, it becomes:

BigDecimal sumAB;
if( a == null )
    sumAB = b;
else if( b == null )
    sumAB = a;
else 
    sumAB = a.sum(b);

BigDecimal sumDE;
if( d == null )
    sumDE = e;
else if( e == null )
    sumDE = d;
else 
    sumDE = d.sum(e);

boolean sumABltC;
if( sumAB == null )
    sumABltC = c != null;
else if( c == null )
    sumABltC = false;
else
    sumABltC = sumAB.compareTo(c) < 0;

boolean cLTsumDE;
if( c == null )
    cLTsumDE = sumDE != null;
else if( sumDE == null )
    cLTsumDE = false;
else
    cLTsumDE = c.compareTo(sumDE) < 0;

if( summABltC && cLTsumDE )
  // do something...

that, from my point of view, is really awful!

Therefore I have developed this three utility classes that provide a collection of static null-safe methods to facilitate working with certain type of classes:

• CU stands for Comparable Utils and provides a list of convenience methods that allow to perform all the most common comparison checks: <, <=, ==, !=, >= and >.
• BI stands for BigInteger Utils and provides a list of convenience methods that allow to perform all the most common operations with BigInteger objects.
• BD stands for BigDecimal Utils and provides a list of convenience methods that allow to perform all the most common operations with BigDecimal objects.

The names of this classes are short on purpose because are intended to be used inside comparison and algebraic statements and need to be easy to read.

Using this classes the previous example becomes:

if( BD.lt(BD.sum(a,b),c) && BD.lt(c,BD.sum(d,e)) )
  // do something...

By using static imports it becomes even more readable:

if( lt(sum(a,b),c) && lt(c,sum(d,e)) )
  // do something...

The most important thing to notice in the last two examples is that we don’t need to check for the BigDecimal instances to be not null because the utility methods are null-safe.

Class Interval

In mathematics, given a set S and a total order relation ≼ over the elements of S, we define an interval I as a subset of S such that: given x,y ∊ I | x ≼ y we have that ∀ s ∊ S if x ≼ s ≼ y then s ∊ I.

An interval can be empty, it can have a lower bound value called inf, it can have an upper bound value called sup, and it can also be unbounded. The upper and lower bounds can be included in the interval, in this case we say that the interval is closed, or they may be excluded from the interval, in this case we say that the interval is open.

The mathematical definition of interval can be applied to any set of comparable objects, it is not restricted to numbers. It could be applied to strings, dates, bit arrays or any other comparable object.

I wasn’t able to find a rigorous implementation of the concept of interval, able to handle any type of comparable object and able to handle unbounded intervals, so I decided to write it by myself.