Invariant Properties

  • rss
  • Home

Getting an Infinite List of Primes in Java

Bear Giles | June 29, 2014

A common problem is to determine the prime factorization of a number. The brute force approach is trial division (Wikipedia, Khan Academy) but that requires a lot of wasted effort if multiple numbers must be factored.

One widely used solution is the Sieve of Eratosthenes (Wikipedia, Math World). It is easy to modify the Sieve of Eratosthenes to contain the largest prime factor of each composite number. This makes it extremely cheap to subsequently compute the prime factorization of numbers.

If we only care about primality we can either use a bitmap with the Sieve of Eratosthenes, or use the Sieve of Atkin).

(Sidenote: for clarity I’m leaving out the common optimizations that follow from the facts that a prime number is always “1 mod 2, n > 2” and “1 or 5 mod 6, n > 5”. This can substantially reduce the amount of memory required for a sieve.)

  1. public enum SieveOfEratosthenes {
  2.     SIEVE;
  3.    
  4.     private int[] sieve;
  5.  
  6.     private SieveOfEratosthenes() {
  7.         // initialize with first million primes - 15485865
  8.         // initialize with first 10k primes - 104729
  9.         sieve = initialize(104729);
  10.     }
  11.  
  12.     /**
  13.      * Initialize the sieve.
  14.      */
  15.     private int[] initialize(int sieveSize) {
  16.         long sqrt = Math.round(Math.ceil(Math.sqrt(sieveSize)));
  17.         long actualSieveSize = (int) (sqrt * sqrt);
  18.  
  19.         // data is initialized to zero
  20.         int[] sieve = new int[actualSieveSize];
  21.  
  22.         for (int x = 2; x < sqrt; x++) {
  23.             if (sieve[x] == 0) {
  24.                 for (int y = 2 * x; y < actualSieveSize; y += x) {
  25.                     sieve[y] = x;
  26.                 }
  27.             }
  28.         }
  29.  
  30.         return sieve;
  31.     }
  32.  
  33.     /**
  34.      * Is this a prime number?
  35.      *
  36.      * @FIXME handle n >= sieve.length!
  37.      *
  38.      * @param n
  39.      * @return true if prime
  40.      * @throws IllegalArgumentException
  41.      *             if negative number
  42.      */
  43.     public boolean isPrime(int n) {
  44.         if (n < 0) {
  45.             throw new IllegalArgumentException("value must be non-zero");
  46.         }
  47.  
  48.         boolean isPrime = sieve[n] == 0;
  49.  
  50.         return isPrime;
  51.     }
  52.  
  53.     /**
  54.      * Factorize a number
  55.      *
  56.      * @FIXME handle n >= sieve.length!
  57.      *
  58.      * @param n
  59.      * @return map of prime divisors (key) and exponent(value)
  60.      * @throws IllegalArgumentException
  61.      *             if negative number
  62.      */
  63.     private Map<Integer, Integer> factorize(int n) {
  64.         if (n < 0) {
  65.             throw new IllegalArgumentException("value must be non-zero");
  66.         }
  67.  
  68.         final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>();
  69.  
  70.         for (int factor = sieve[n]; factor > 0; factor = sieve[n]) {
  71.             if (factors.containsKey(factor)) {
  72.                 factors.put(factor, 1 + factors.get(factor));
  73.             } else {
  74.                 factors.put(factor, 1);
  75.             }
  76.  
  77.             n /= factor;
  78.         }
  79.  
  80.         // must add final term
  81.         if (factors.containsKey(n)) {
  82.             factors.put(n, 1 + factors.get(n));
  83.         } else {
  84.             factors.put(n, 1);
  85.         }
  86.  
  87.         return factors;
  88.     }
  89.  
  90.     /**
  91.      * Convert a factorization to a human-friendly string. The format is a
  92.      * comma-delimited list where each element is either a prime number p (as
  93.      * "p"), or the nth power of a prime number as "p^n".
  94.      *
  95.      * @param factors
  96.      *            factorization
  97.      * @return string representation of factorization.
  98.      * @throws IllegalArgumentException
  99.      *             if negative number
  100.      */
  101.     public String toString(Map factors) {
  102.         StringBuilder sb = new StringBuilder(20);
  103.  
  104.         for (Map.Entry entry : factors.entrySet()) {
  105.             sb.append(", ");
  106.  
  107.             if (entry.getValue() == 1) {
  108.                 sb.append(String.valueOf(entry.getKey()));
  109.             } else {
  110.                 sb.append(String.valueOf(entry.getKey()));
  111.                 sb.append("^");
  112.                 sb.append(String.valueOf(entry.getValue()));
  113.             }
  114.         }
  115.  
  116.         return sb.substring(2);
  117.     }
  118. }
public enum SieveOfEratosthenes {
    SIEVE;
    
    private int[] sieve;

    private SieveOfEratosthenes() {
        // initialize with first million primes - 15485865
        // initialize with first 10k primes - 104729
        sieve = initialize(104729);
    }

    /**
     * Initialize the sieve.
     */
    private int[] initialize(int sieveSize) {
        long sqrt = Math.round(Math.ceil(Math.sqrt(sieveSize)));
        long actualSieveSize = (int) (sqrt * sqrt);

        // data is initialized to zero
        int[] sieve = new int[actualSieveSize];

        for (int x = 2; x < sqrt; x++) {
            if (sieve[x] == 0) {
                for (int y = 2 * x; y < actualSieveSize; y += x) {
                    sieve[y] = x;
                }
            }
        }

        return sieve;
    }

    /**
     * Is this a prime number?
     *
     * @FIXME handle n >= sieve.length!
     * 
     * @param n
     * @return true if prime
     * @throws IllegalArgumentException
     *             if negative number
     */
    public boolean isPrime(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        boolean isPrime = sieve[n] == 0;

        return isPrime;
    }

    /**
     * Factorize a number
     *
     * @FIXME handle n >= sieve.length!
     * 
     * @param n
     * @return map of prime divisors (key) and exponent(value)
     * @throws IllegalArgumentException
     *             if negative number
     */
    private Map<Integer, Integer> factorize(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>();

        for (int factor = sieve[n]; factor > 0; factor = sieve[n]) {
            if (factors.containsKey(factor)) {
                factors.put(factor, 1 + factors.get(factor));
            } else {
                factors.put(factor, 1);
            }

            n /= factor;
        }

        // must add final term
        if (factors.containsKey(n)) {
            factors.put(n, 1 + factors.get(n));
        } else {
            factors.put(n, 1);
        }

        return factors;
    }

    /**
     * Convert a factorization to a human-friendly string. The format is a
     * comma-delimited list where each element is either a prime number p (as
     * "p"), or the nth power of a prime number as "p^n".
     * 
     * @param factors
     *            factorization
     * @return string representation of factorization.
     * @throws IllegalArgumentException
     *             if negative number
     */
    public String toString(Map factors) {
        StringBuilder sb = new StringBuilder(20);

        for (Map.Entry entry : factors.entrySet()) {
            sb.append(", ");

            if (entry.getValue() == 1) {
                sb.append(String.valueOf(entry.getKey()));
            } else {
                sb.append(String.valueOf(entry.getKey()));
                sb.append("^");
                sb.append(String.valueOf(entry.getValue()));
            }
        }

        return sb.substring(2);
    }
}

This code has a major weakness – it will fail if the requested number is out of range. There is an easy fix – we can dynamically resize the sieve as required. We use a Lock to ensure multithreaded calls don’t get the sieve in an intermediate state. We need to be careful to avoid getting into a deadlock between the read and write locks.

  1.     private final ReadWriteLock lock = new ReentrantReadWriteLock();
  2.  
  3.     /**
  4.      * Initialize the sieve. This method is called when it is necessary to grow
  5.      * the sieve.
  6.      */
  7.     private void reinitialize(int n) {
  8.         try {
  9.             lock.writeLock().lock();
  10.             // allocate 50% more than required to minimize thrashing.
  11.             initialize((3 * n) / 2);
  12.         } finally {
  13.             lock.writeLock().unlock();
  14.         }
  15.     }
  16.  
  17.     /**
  18.      * Is this a prime number?
  19.      *
  20.      * @param n
  21.      * @return true if prime
  22.      * @throws IllegalArgumentException
  23.      *             if negative number
  24.      */
  25.     public boolean isPrime(int n) {
  26.         if (n < 0) {
  27.             throw new IllegalArgumentException("value must be non-zero");
  28.         }
  29.  
  30.         if (n > sieve.length) {
  31.             reinitialize(n);
  32.         }
  33.  
  34.         boolean isPrime = false;
  35.         try {
  36.             lock.readLock().lock();
  37.             isPrime = sieve[n] == 0;
  38.         } finally {
  39.             lock.readLock().unlock();
  40.         }
  41.  
  42.         return isPrime;
  43.     }
  44.  
  45.     /**
  46.      * Factorize a number
  47.      *
  48.      * @param n
  49.      * @return map of prime divisors (key) and exponent(value)
  50.      * @throws IllegalArgumentException
  51.      *             if negative number
  52.      */
  53.     private Map<Integer, Integer> factorize(int n) {
  54.         if (n < 0) {
  55.             throw new IllegalArgumentException("value must be non-zero");
  56.         }
  57.  
  58.         final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>();
  59.  
  60.         try {
  61.             if (n > sieve.length) {
  62.                 reinitialize(n);
  63.             }
  64.  
  65.             lock.readLock().lock();
  66.             for (int factor = sieve[n]; factor > 0; factor = sieve[n]) {
  67.                 if (factors.containsKey(factor)) {
  68.                     factors.put(factor, 1 + factors.get(factor));
  69.                 } else {
  70.                     factors.put(factor, 1);
  71.                 }
  72.  
  73.                 n /= factor;
  74.             }
  75.         } finally {
  76.             lock.readLock().unlock();
  77.         }
  78.  
  79.         // must add final term
  80.         if (factors.containsKey(n)) {
  81.             factors.put(n, 1 + factors.get(n));
  82.         } else {
  83.             factors.put(n, 1);
  84.         }
  85.  
  86.         return factors;
  87.     }
    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    /**
     * Initialize the sieve. This method is called when it is necessary to grow
     * the sieve.
     */
    private void reinitialize(int n) {
        try {
            lock.writeLock().lock();
            // allocate 50% more than required to minimize thrashing.
            initialize((3 * n) / 2);
        } finally {
            lock.writeLock().unlock();
        }
    }

    /**
     * Is this a prime number?
     * 
     * @param n
     * @return true if prime
     * @throws IllegalArgumentException
     *             if negative number
     */
    public boolean isPrime(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        if (n > sieve.length) {
            reinitialize(n);
        }

        boolean isPrime = false;
        try {
            lock.readLock().lock();
            isPrime = sieve[n] == 0;
        } finally {
            lock.readLock().unlock();
        }

        return isPrime;
    }

    /**
     * Factorize a number
     * 
     * @param n
     * @return map of prime divisors (key) and exponent(value)
     * @throws IllegalArgumentException
     *             if negative number
     */
    private Map<Integer, Integer> factorize(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        final Map<Integer, Integer> factors = new TreeMap<Integer, Integer>();

        try {
            if (n > sieve.length) {
                reinitialize(n);
            }

            lock.readLock().lock();
            for (int factor = sieve[n]; factor > 0; factor = sieve[n]) {
                if (factors.containsKey(factor)) {
                    factors.put(factor, 1 + factors.get(factor));
                } else {
                    factors.put(factor, 1);
                }

                n /= factor;
            }
        } finally {
            lock.readLock().unlock();
        }

        // must add final term
        if (factors.containsKey(n)) {
            factors.put(n, 1 + factors.get(n));
        } else {
            factors.put(n, 1);
        }

        return factors;
    }

Iterable<Integer> and foreach loops

In the real world it’s often easier to use a foreach loop (or explicit Iterator) than to probe a table item by item. Fortunately it’s easy to create an iterator that’s built on top of our self-growing sieve.

  1.    /**
  2.      * @see java.util.List#get(int)
  3.      *
  4.      * We can use a cache of the first few (1000? 10,000?) primes
  5.      * for improved performance.
  6.      *
  7.      * @param n
  8.      * @return nth prime (starting with 2)
  9.      * @throws IllegalArgumentException
  10.      *             if negative number
  11.      */
  12.     public Integer get(int n) {
  13.         if (n < 0) {
  14.             throw new IllegalArgumentException("value must be non-zero");
  15.         }
  16.  
  17.         Iterator<Integer> iter = iterator();
  18.         for (int i = 0; i < n; i++) {
  19.             iter.next();
  20.         }
  21.  
  22.         return iter.next();
  23.     }
  24.  
  25.     /**
  26.      * @see java.util.List#indexOf(java.lang.Object)
  27.      */
  28.     public int indexOf(Integer n) {
  29.         if (!isPrime(n)) {
  30.             return -1;
  31.         }
  32.  
  33.         int index = 0;
  34.         for (int i : sieve) {
  35.             if (i == n) {
  36.                 return index;
  37.             }
  38.             index++;
  39.         }
  40.         return -1;
  41.     }
  42.    /**
  43.      * @see java.lang.Iterable#iterator()
  44.      */
  45.     public Iterator<Integer> iterator() {
  46.         return new EratosthenesListIterator();
  47.     }
  48.  
  49.     public ListIterator<Integer> listIterator() {
  50.         return new EratosthenesListIterator();
  51.     }
  52.  
  53.     /**
  54.      * List iterator.
  55.      *
  56.      * @author Bear Giles <bgiles@coyotesong.com>
  57.      */
  58.     static class EratosthenesListIterator extends AbstractListIterator<Integer> {
  59.         int offset = 2;
  60.  
  61.         /**
  62.          * @see com.invariantproperties.projecteuler.AbstractListIterator#getNext()
  63.          */
  64.         @Override
  65.         protected Integer getNext() {
  66.             while (true) {
  67.                 offset++;
  68.                 if (SIEVE.isPrime(offset)) {
  69.                     return offset;
  70.                 }
  71.             }
  72.  
  73.             // we'll always find a value since we dynamically resize the sieve.
  74.         }
  75.  
  76.         /**
  77.          * @see com.invariantproperties.projecteuler.AbstractListIterator#getPrevious()
  78.          */
  79.         @Override
  80.         protected Integer getPrevious() {
  81.             while (offset > 0) {
  82.                 offset--;
  83.                 if (SIEVE.isPrime(offset)) {
  84.                     return offset;
  85.                 }
  86.             }
  87.  
  88.             // we only get here if something went horribly wrong
  89.             throw new NoSuchElementException();
  90.         }
  91.     }
  92. }
   /**
     * @see java.util.List#get(int)
     *
     * We can use a cache of the first few (1000? 10,000?) primes
     * for improved performance.
     *
     * @param n
     * @return nth prime (starting with 2)
     * @throws IllegalArgumentException
     *             if negative number
     */
    public Integer get(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("value must be non-zero");
        }

        Iterator<Integer> iter = iterator();
        for (int i = 0; i < n; i++) {
            iter.next();
        }

        return iter.next();
    }

    /**
     * @see java.util.List#indexOf(java.lang.Object)
     */
    public int indexOf(Integer n) {
        if (!isPrime(n)) {
            return -1;
        }

        int index = 0;
        for (int i : sieve) {
            if (i == n) {
                return index;
            }
            index++;
        }
        return -1;
    }
   /**
     * @see java.lang.Iterable#iterator()
     */
    public Iterator<Integer> iterator() {
        return new EratosthenesListIterator();
    }

    public ListIterator<Integer> listIterator() {
        return new EratosthenesListIterator();
    }

    /**
     * List iterator.
     *
     * @author Bear Giles <bgiles@coyotesong.com>
     */
    static class EratosthenesListIterator extends AbstractListIterator<Integer> {
        int offset = 2;

        /**
         * @see com.invariantproperties.projecteuler.AbstractListIterator#getNext()
         */
        @Override
        protected Integer getNext() {
            while (true) {
                offset++;
                if (SIEVE.isPrime(offset)) {
                    return offset;
                }
            }
 
            // we'll always find a value since we dynamically resize the sieve.
        }

        /**
         * @see com.invariantproperties.projecteuler.AbstractListIterator#getPrevious()
         */
        @Override
        protected Integer getPrevious() {
            while (offset > 0) {
                offset--;
                if (SIEVE.isPrime(offset)) {
                    return offset;
                }
            }

            // we only get here if something went horribly wrong
            throw new NoSuchElementException();
        }
    }
}

IMPORTANT: The code

  1. for (int prime : SieveOfEratosthenes.SIEVE) { ... }
for (int prime : SieveOfEratosthenes.SIEVE) { ... }

is essentially an infinite loop. It will only stop once the JVM exhausts the heap space when allocating a new sieve.

In practice this means that the maximum prime we can maintain in our sieve is around 1 GB. That requires 4 GB with 4-byte ints. If we only care about primality and use a common optimization that 4 GB can hold information on 64 GB values. For simplicity we can call this 9-to-10 digit numbers (base 10).

What if we put our sieve on a disk?

There is no reason why the sieve has to remain in memory. Our iterator can quietly load values from disk instead of an in-memory cache. A 4 TB disk, probably accessed in raw mode, would seem to bump the size of our sieve to 14-to-15 digit numbers (base 10). In fact it will be a bit less because we’ll have to double the size of our primitive types from int to long, and then probably to an even larger format.

More! More! More!

We can dramatically increase the effective size of our sieve by noting that we only have to compute sqrt(n) to initialize a sieve of n values. We can flip that and say that a fully populated sieve of n values can be used to populate another sieve of n2 values. In this case we’ll want to only populate a band, not the full n2 sieve. Our in-memory sieve can now cover values up to roughly 40 digit numbers (base 10), and the disk-based sieve jumps to as much as 60 digit numbers (base 10), minus the space require for the larger values.

There is no reason why this approach can’t be taken even further – use a small sieve to bootstrap a larger transient sieve and use it, in turn, to populate an even larger sieve.

But how long will this take?

Aye, there’s the rub. The cost to initialize a sieve of n values is O(n2). You can use various tweaks to reduce the constants but at the end of the day you’re visiting every node once (O(n)), and then visiting some rolling value proportional to n beyond each of those points. For what it’s worth this is a problem where keeping the CPU’s cache architecture could make a big difference.

In practical terms any recent system should be able to create a sieve containing the first million primes within a few seconds. Bump the sieve to the first billion primes and the time has probably leapt to a week, maybe a month if limited JVM heap space forces us to use the disk heavily. My gut instinct is that it will take a server farm months to years to populate a TB disk

Why bother?

For most of us the main takeaway is a demonstration of how to start a collection with a small seed, say a sieve with n = 1000, and transparently grow it as required. This is easy with prime numbers but it isn’t a huge stretch to imagine the same approach being used with, oh, RSS feeds. We’re used to thinking of Iterators as some boring aspect of Collections but in fact they give us a lot of flexibility when used as part of an Iterable.

There is also a practical reason for a large prime sieve – factoring large numbers. There are several good algorithms for factoring large numbers but they’re expensive – even “small” numbers may take months or years on a server farm. That’s why the first step is always doing trial division with “small” primes – something that may take a day by itself.

Source Code

The good news is that I have published the source code for this… and the bad news is it’s part of ongoing doodling when I’m doing Project Euler problems. (There are no solutions here – it’s entirely explorations of ideas inspired by the problems. So the code is a little rough and should not be used to decide whether or not to bring me in for an interview (unless you’re impressed): http://github.com/beargiles/projecteuler.

Comments
No Comments »
Categories
java, math
Comments rss Comments rss
Trackback Trackback

Fibonacci and Lucas Sequences

Bear Giles | June 24, 2014

This posts touches on three of my favorite topics – math, transferring knowledge through experience (tutorial unit tests) and the importance of research.

Most developers are aware of the Fibonacci sequence, mostly through job interviews.

To briefly recap the series is defined as

F(n) = F(n-1) + F(n-2), n > 2
F(1) = F(2) = 1

There’s a variant definition

F(n) = F(n-1) + F(n-2), n > 1
F(1) = 1
F(0) = 0

There are four well-known solutions to the white-board question “write code to calculate F(n)”.

Recursion – you need to mention this to show that you’re comfortable with recursion but you must also mention that it’s a Really Bad Idea since it requires O(2n) time and space stack since you double the work for each n.

Recursion with memoization – this can be a good approach if you point out it’s a good generalization. Basically it’s recursion but you maintain a cache (the memoization) so you only need to make the recursive call once – subsequent recursive calls just look up the cached value. This is a flexible technique since it can be used for any pure recursive function. (That is, a recursive function that depends solely on its inputs and has no side effects.) The first calls require O(n) time, stack and heap space. I don’t recall if it matters if you do the recursive call on the smaller or larger value first.

If you have a persistent cache subsequent calls require O(1) time and stack space and O(n) heap space.

Iteration – if you can’t cache the values (or just want to efficiently initialize a cache) you can use an iterative approach. It requires O(n) time but only O(1) stack and heap space.

Direct approximation – finally there is a well-known approximation using φ, or a variant using sqrt(5). It is O(1) for time, stack space, and heap space. It’s a good approach if you 1) use a lookup table for the smallest values and 2) make sure n is not too big.

The last point is often overlooked. The approximation only works as long as you don’t exceed the precision of your floating point number. F(100,000) should be good. F(1,000,000,000,000) may not be. The iterative approach isn’t practical with numbers this large.

Research

Did you know there’s two other solutions with performance O(lg(n)) (per Wikipedia) in time and space? (I’m not convinced it’s O(lg(n)) since it’s not a divide-and-conquer algorithm – the two recursive calls do not split the initial work between them – but with memoization it’s definitely less than O(n). I suspect but can’t quickly prove it’s O(lg2(n)).)

Per Wikipedia we know

F(2n-1) = F2(n) + F2(n-1)
F(2n) = F(n)(F(n) + 2F(n-1))

It is straightforward to rewrite this as a recursive method for F(n).

There is another property that considers three cases – F(3n-2), F(3n-1) and F(3n). See the code for details.

These sites provide many additional properties of the Fibonacci and related Lucas sequences. Few developers will ever need to know these properties but in those rare cases an hour of research can save days of work.

Implementation

We can now use our research to implement suitable methods for the Fibonacci and Lucas sequences.

Fibonacci calculation

(This code does not show an optimization using direct approximation for uncached values for sufficiently small n.)

  1.     /**
  2.      * Get specified Fibonacci number.
  3.      * @param n
  4.      * @return
  5.      */
  6.     @Override
  7.     public BigInteger get(int n) {
  8.         if (n < 0) {
  9.             throw new IllegalArgumentException("index must be non-negative");
  10.         }
  11.  
  12.         BigInteger value = null;
  13.  
  14.         synchronized (cache) {
  15.             value = cache.get(n);
  16.  
  17.             if (value == null) {
  18.                 int m = n / 3;
  19.  
  20.                 switch (n % 3) {
  21.                 case 0:
  22.                     value = TWO.multiply(get(m).pow(3))
  23.                                .add(THREE.multiply(get(m + 1)).multiply(get(m))
  24.                                          .multiply(get(m - 1)));
  25.  
  26.                     break;
  27.  
  28.                 case 1:
  29.                     value = get(m + 1).pow(3)
  30.                                 .add(THREE.multiply(get(m + 1)
  31.                                                         .multiply(get(m).pow(2))))
  32.                                 .subtract(get(m).pow(3));
  33.  
  34.                     break;
  35.  
  36.                 case 2:
  37.                     value = get(m + 1).pow(3)
  38.                                 .add(THREE.multiply(get(m + 1).pow(2)
  39.                                                         .multiply(get(m))))
  40.                                 .add(get(m).pow(3));
  41.  
  42.                     break;
  43.                 }
  44.  
  45.                 cache.put(n, value);
  46.             }
  47.         }
  48.  
  49.         return value;
  50.     }
    /**
     * Get specified Fibonacci number.
     * @param n
     * @return
     */
    @Override
    public BigInteger get(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("index must be non-negative");
        }

        BigInteger value = null;

        synchronized (cache) {
            value = cache.get(n);

            if (value == null) {
                int m = n / 3;

                switch (n % 3) {
                case 0:
                    value = TWO.multiply(get(m).pow(3))
                               .add(THREE.multiply(get(m + 1)).multiply(get(m))
                                         .multiply(get(m - 1)));

                    break;

                case 1:
                    value = get(m + 1).pow(3)
                                .add(THREE.multiply(get(m + 1)
                                                        .multiply(get(m).pow(2))))
                                .subtract(get(m).pow(3));

                    break;

                case 2:
                    value = get(m + 1).pow(3)
                                .add(THREE.multiply(get(m + 1).pow(2)
                                                        .multiply(get(m))))
                                .add(get(m).pow(3));

                    break;
                }

                cache.put(n, value);
            }
        }

        return value;
    }

Fibonacci Iterator

  1.     /**
  2.      * ListIterator class.
  3.      * @author bgiles
  4.      */
  5.     private static final class FibonacciIterator extends ListIterator {
  6.         private BigInteger x = BigInteger.ZERO;
  7.         private BigInteger y = BigInteger.ONE;
  8.  
  9.         public FibonacciIterator() {
  10.         }
  11.  
  12.         public FibonacciIterator(int startIndex, FibonacciNumber fibonacci) {
  13.             this.idx = startIndex;
  14.             this.x = fibonacci.get(idx);
  15.             this.y = fibonacci.get(idx + 1);
  16.         }
  17.  
  18.         protected BigInteger getNext() {
  19.             BigInteger t = x;
  20.             x = y;
  21.             y = t.add(x);
  22.  
  23.             return t;
  24.         }
  25.  
  26.         protected BigInteger getPrevious() {
  27.             BigInteger t = y;
  28.             y = x;
  29.             x = t.subtract(x);
  30.  
  31.             return x;
  32.         }
  33.     }
    /**
     * ListIterator class.
     * @author bgiles
     */
    private static final class FibonacciIterator extends ListIterator {
        private BigInteger x = BigInteger.ZERO;
        private BigInteger y = BigInteger.ONE;

        public FibonacciIterator() {
        }

        public FibonacciIterator(int startIndex, FibonacciNumber fibonacci) {
            this.idx = startIndex;
            this.x = fibonacci.get(idx);
            this.y = fibonacci.get(idx + 1);
        }

        protected BigInteger getNext() {
            BigInteger t = x;
            x = y;
            y = t.add(x);

            return t;
        }

        protected BigInteger getPrevious() {
            BigInteger t = y;
            y = x;
            x = t.subtract(x);

            return x;
        }
    }

Lucas calculation

  1.     /**
  2.      * Get specified Lucas number.
  3.      * @param n
  4.      * @return
  5.      */
  6.     public BigInteger get(int n) {
  7.         if (n < 0) {
  8.             throw new IllegalArgumentException("index must be non-negative");
  9.         }
  10.  
  11.         BigInteger value = null;
  12.  
  13.         synchronized (cache) {
  14.             value = cache.get(n);
  15.  
  16.             if (value == null) {
  17.                 value = Sequences.FIBONACCI.get(n + 1)
  18.                                            .add(Sequences.FIBONACCI.get(n - 1));
  19.                 cache.put(n, value);
  20.             }
  21.         }
  22.  
  23.         return value;
  24.     }
    /**
     * Get specified Lucas number.
     * @param n
     * @return
     */
    public BigInteger get(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("index must be non-negative");
        }

        BigInteger value = null;

        synchronized (cache) {
            value = cache.get(n);

            if (value == null) {
                value = Sequences.FIBONACCI.get(n + 1)
                                           .add(Sequences.FIBONACCI.get(n - 1));
                cache.put(n, value);
            }
        }

        return value;
    }

Lucas iterator

  1.    /**
  2.      * ListIterator class.
  3.      * @author bgiles
  4.      */
  5.     private static final class LucasIterator extends ListIterator {
  6.         private BigInteger x = TWO;
  7.         private BigInteger y = BigInteger.ONE;
  8.  
  9.         public LucasIterator() {
  10.         }
  11.  
  12.         public LucasIterator(int startIndex, LucasNumber lucas) {
  13.             idx = startIndex;
  14.             this.x = lucas.get(idx);
  15.             this.y = lucas.get(idx + 1);
  16.         }
  17.  
  18.         protected BigInteger getNext() {
  19.             BigInteger t = x;
  20.             x = y;
  21.             y = t.add(x);
  22.  
  23.             return t;
  24.         }
  25.  
  26.         protected BigInteger getPrevious() {
  27.             BigInteger t = y;
  28.             y = x;
  29.             x = t.subtract(x);
  30.  
  31.             return x;
  32.         }
  33.     }
   /**
     * ListIterator class.
     * @author bgiles
     */
    private static final class LucasIterator extends ListIterator {
        private BigInteger x = TWO;
        private BigInteger y = BigInteger.ONE;

        public LucasIterator() {
        }

        public LucasIterator(int startIndex, LucasNumber lucas) {
            idx = startIndex;
            this.x = lucas.get(idx);
            this.y = lucas.get(idx + 1);
        }

        protected BigInteger getNext() {
            BigInteger t = x;
            x = y;
            y = t.add(x);

            return t;
        }

        protected BigInteger getPrevious() {
            BigInteger t = y;
            y = x;
            x = t.subtract(x);

            return x;
        }
    }

Education

What is the best way to educate other developers about the existence of these unexpected relationships? Code, of course!

What is the best way to educate other developers about the existence of code that demonstrates these relationships? Unit tests, of course!

It is straightforward to write unit tests that simultaneous verify our implementation and inform other developers about tricks they can use to improve their code. The key is to provide a link to additional information.

Fibonacci Sequence

  1. public class FibonacciNumberTest extends AbstractRecurrenceSequenceTest {
  2.     private static final BigInteger MINUS_ONE = BigInteger.valueOf(-1);
  3.  
  4.     /**
  5.      * Constructor
  6.      */
  7.     public FibonacciNumberTest() throws NoSuchMethodException {
  8.         super(FibonacciNumber.class);
  9.     }
  10.  
  11.     /**
  12.      * Get number of tests to run.
  13.      */
  14.     @Override
  15.     public int getMaxTests() {
  16.         return 300;
  17.     }
  18.  
  19.     /**
  20.      * Verify the definition is properly implemented.
  21.      *
  22.      * @return
  23.      */
  24.     @Test
  25.     @Override
  26.     public void verifyDefinition() {
  27.         for (int n = 2; n < getMaxTests(); n++) {
  28.             BigInteger u = seq.get(n);
  29.             BigInteger v = seq.get(n - 1);
  30.             BigInteger w = seq.get(n - 2);
  31.             Assert.assertEquals(u, v.add(w));
  32.         }
  33.     }
  34.  
  35.     /**
  36.      * Verify initial terms.
  37.      */
  38.     @Test
  39.     @Override
  40.     public void verifyInitialTerms() {
  41.         verifyInitialTerms(Arrays.asList(ZERO, ONE, ONE, TWO, THREE, FIVE, EIGHT));
  42.     }
  43.  
  44.     /**
  45.      * Verify that every third term is even and the other two terms are odd.
  46.      * This is a subset of the general divisibility property.
  47.      *
  48.      * @return
  49.      */
  50.     @Test
  51.     public void verifyEvenDivisibility() {
  52.         for (int n = 0; n < getMaxTests(); n += 3) {
  53.             Assert.assertEquals(ZERO, seq.get(n).mod(TWO));
  54.             Assert.assertEquals(ONE, seq.get(n + 1).mod(TWO));
  55.             Assert.assertEquals(ONE, seq.get(n + 2).mod(TWO));
  56.         }
  57.     }
  58.  
  59.     /**
  60.      * Verify general divisibility property.
  61.      *
  62.      * @return
  63.      */
  64.     @Test
  65.     public void verifyDivisibility() {
  66.         for (int d = 3; d < getMaxTests(); d++) {
  67.             BigInteger divisor = seq.get(d);
  68.  
  69.             for (int n = 0; n < getMaxTests(); n += d) {
  70.                 Assert.assertEquals(ZERO, seq.get(n).mod(divisor));
  71.  
  72.                 for (int i = 1; (i < d) && ((n + i) < getMaxTests()); i++) {
  73.                     Assert.assertFalse(ZERO.equals(seq.get(n + i).mod(divisor)));
  74.                 }
  75.             }
  76.         }
  77.     }
  78.  
  79.     /**
  80.      * Verify the property that gcd(F(m), F(n)) = F(gcd(m,n)). This is a
  81.      * stronger statement than the divisibility property.
  82.      */
  83.     @Test
  84.     public void verifyGcd() {
  85.         for (int m = 3; m < getMaxTests(); m++) {
  86.             for (int n = m + 1; n < getMaxTests(); n++) {
  87.                 BigInteger gcd1 = seq.get(m).gcd(seq.get(n));
  88.                 int gcd2 = BigInteger.valueOf(m).gcd(BigInteger.valueOf(n))
  89.                                      .intValue();
  90.                 Assert.assertEquals(gcd1, seq.get(gcd2));
  91.             }
  92.         }
  93.     }
  94.  
  95.     /**
  96.      * Verify second identity (per Wikipedia): sum(F(i)) = F(n+2)-1
  97.      */
  98.     @Test
  99.     public void verifySecondIdentity() {
  100.         BigInteger sum = ZERO;
  101.  
  102.         for (int n = 0; n < getMaxTests(); n++) {
  103.             sum = sum.add(seq.get(n));
  104.             Assert.assertEquals(sum, seq.get(n + 2).subtract(ONE));
  105.         }
  106.     }
  107.  
  108.     /**
  109.      * Verify third identity (per Wikipedia): sum(F(2i)) = F(2n+1)-1 and
  110.      * sum(F(2i+1)) = F(2n)
  111.      */
  112.     @Test
  113.     public void verifyThirdIdentity() {
  114.         BigInteger sum = ZERO;
  115.  
  116.         for (int n = 0; n < getMaxTests(); n += 2) {
  117.             sum = sum.add(seq.get(n));
  118.             Assert.assertEquals(sum, seq.get(n + 1).subtract(ONE));
  119.         }
  120.  
  121.         sum = ZERO;
  122.  
  123.         for (int n = 1; n < getMaxTests(); n += 2) {
  124.             sum = sum.add(seq.get(n));
  125.             Assert.assertEquals(sum, seq.get(n + 1));
  126.         }
  127.     }
  128.  
  129.     /**
  130.      * Verify fourth identity (per Wikipedia): sum(iF(i)) = nF(n+2) - F(n+3) + 2
  131.      */
  132.     @Test
  133.     public void verifyFourthIdentity() {
  134.         BigInteger sum = ZERO;
  135.  
  136.         for (int n = 0; n < getMaxTests(); n++) {
  137.             sum = sum.add(BigInteger.valueOf(n).multiply(seq.get(n)));
  138.  
  139.             BigInteger x = BigInteger.valueOf(n).multiply(seq.get(n + 2))
  140.                                      .subtract(seq.get(n + 3)).add(TWO);
  141.             Assert.assertEquals(sum, x);
  142.         }
  143.     }
  144.  
  145.     /**
  146.      * Verify fifth identity (per Wikipedia): sum(F(i)^2) = F(n)F(n+1)
  147.      */
  148.     public void verifyFifthIdentity() {
  149.         BigInteger sum = ZERO;
  150.  
  151.         for (int n = 0; n < getMaxTests(); n += 2) {
  152.             BigInteger u = seq.get(n);
  153.             BigInteger v = seq.get(n + 1);
  154.             sum = sum.add(u.pow(2));
  155.             Assert.assertEquals(sum, u.multiply(v));
  156.         }
  157.     }
  158.  
  159.     /**
  160.      * Verify Cassini&#039;s Identity - F(n-1)F(n+1) - F(n)^2 = -1^n
  161.      */
  162.     @Test
  163.     public void verifyCassiniIdentity() {
  164.         for (int n = 2; n < getMaxTests(); n += 2) {
  165.             BigInteger u = seq.get(n - 1);
  166.             BigInteger v = seq.get(n);
  167.             BigInteger w = seq.get(n + 1);
  168.  
  169.             BigInteger x = w.multiply(u).subtract(v.pow(2));
  170.             Assert.assertEquals(ONE, x);
  171.         }
  172.  
  173.         for (int n = 1; n < getMaxTests(); n += 2) {
  174.             BigInteger u = seq.get(n - 1);
  175.             BigInteger v = seq.get(n);
  176.             BigInteger w = seq.get(n + 1);
  177.  
  178.             BigInteger x = w.multiply(u).subtract(v.pow(2));
  179.             Assert.assertEquals(MINUS_ONE, x);
  180.         }
  181.     }
  182.  
  183.     /**
  184.      * Verify doubling: F(2n-1) = F(n)^2 + F(n-1)^2 and F(2n) =
  185.      * F(n)(F(n-1)+F(n+1)) = F(n)(2*F(n-1)+F(n).
  186.      */
  187.     @Test
  188.     public void verifyDoubling() {
  189.         for (int n = 1; n < getMaxTests(); n++) {
  190.             BigInteger u = seq.get(n - 1);
  191.             BigInteger v = seq.get(n);
  192.             BigInteger w = seq.get(n + 1);
  193.  
  194.             BigInteger x = v.multiply(v).add(u.pow(2));
  195.             Assert.assertEquals(seq.get((2 * n) - 1), x);
  196.  
  197.             x = v.multiply(u.add(w));
  198.             Assert.assertEquals(seq.get(2 * n), x);
  199.  
  200.             x = v.multiply(v.add(TWO.multiply(u)));
  201.             Assert.assertEquals(seq.get(2 * n), x);
  202.         }
  203.     }
  204.  
  205.     /**
  206.      * Verify tripling.
  207.      */
  208.     @Test
  209.     public void verifyTripling() {
  210.         for (int n = 1; n < getMaxTests(); n++) {
  211.             BigInteger u = seq.get(n - 1);
  212.             BigInteger v = seq.get(n);
  213.             BigInteger w = seq.get(n + 1);
  214.  
  215.             BigInteger x = TWO.multiply(v.pow(3))
  216.                               .add(THREE.multiply(v).multiply(u).multiply(w));
  217.             Assert.assertEquals(seq.get(3 * n), x);
  218.  
  219.             x = w.pow(3).add(THREE.multiply(w).multiply(v.pow(2)))
  220.                  .subtract(v.pow(3));
  221.             Assert.assertEquals(seq.get((3 * n) + 1), x);
  222.  
  223.             x = w.pow(3).add(THREE.multiply(w.pow(2)).multiply(v)).add(v.pow(3));
  224.             Assert.assertEquals(seq.get((3 * n) + 2), x);
  225.         }
  226.     }
  227. }
public class FibonacciNumberTest extends AbstractRecurrenceSequenceTest {
    private static final BigInteger MINUS_ONE = BigInteger.valueOf(-1);

    /**
     * Constructor
     */
    public FibonacciNumberTest() throws NoSuchMethodException {
        super(FibonacciNumber.class);
    }

    /**
     * Get number of tests to run.
     */
    @Override
    public int getMaxTests() {
        return 300;
    }

    /**
     * Verify the definition is properly implemented.
     *
     * @return
     */
    @Test
    @Override
    public void verifyDefinition() {
        for (int n = 2; n < getMaxTests(); n++) {
            BigInteger u = seq.get(n);
            BigInteger v = seq.get(n - 1);
            BigInteger w = seq.get(n - 2);
            Assert.assertEquals(u, v.add(w));
        }
    }

    /**
     * Verify initial terms.
     */
    @Test
    @Override
    public void verifyInitialTerms() {
        verifyInitialTerms(Arrays.asList(ZERO, ONE, ONE, TWO, THREE, FIVE, EIGHT));
    }

    /**
     * Verify that every third term is even and the other two terms are odd.
     * This is a subset of the general divisibility property.
     *
     * @return
     */
    @Test
    public void verifyEvenDivisibility() {
        for (int n = 0; n < getMaxTests(); n += 3) {
            Assert.assertEquals(ZERO, seq.get(n).mod(TWO));
            Assert.assertEquals(ONE, seq.get(n + 1).mod(TWO));
            Assert.assertEquals(ONE, seq.get(n + 2).mod(TWO));
        }
    }

    /**
     * Verify general divisibility property.
     *
     * @return
     */
    @Test
    public void verifyDivisibility() {
        for (int d = 3; d < getMaxTests(); d++) {
            BigInteger divisor = seq.get(d);

            for (int n = 0; n < getMaxTests(); n += d) {
                Assert.assertEquals(ZERO, seq.get(n).mod(divisor));

                for (int i = 1; (i < d) && ((n + i) < getMaxTests()); i++) {
                    Assert.assertFalse(ZERO.equals(seq.get(n + i).mod(divisor)));
                }
            }
        }
    }

    /**
     * Verify the property that gcd(F(m), F(n)) = F(gcd(m,n)). This is a
     * stronger statement than the divisibility property.
     */
    @Test
    public void verifyGcd() {
        for (int m = 3; m < getMaxTests(); m++) {
            for (int n = m + 1; n < getMaxTests(); n++) {
                BigInteger gcd1 = seq.get(m).gcd(seq.get(n));
                int gcd2 = BigInteger.valueOf(m).gcd(BigInteger.valueOf(n))
                                     .intValue();
                Assert.assertEquals(gcd1, seq.get(gcd2));
            }
        }
    }

    /**
     * Verify second identity (per Wikipedia): sum(F(i)) = F(n+2)-1
     */
    @Test
    public void verifySecondIdentity() {
        BigInteger sum = ZERO;

        for (int n = 0; n < getMaxTests(); n++) {
            sum = sum.add(seq.get(n));
            Assert.assertEquals(sum, seq.get(n + 2).subtract(ONE));
        }
    }

    /**
     * Verify third identity (per Wikipedia): sum(F(2i)) = F(2n+1)-1 and
     * sum(F(2i+1)) = F(2n)
     */
    @Test
    public void verifyThirdIdentity() {
        BigInteger sum = ZERO;

        for (int n = 0; n < getMaxTests(); n += 2) {
            sum = sum.add(seq.get(n));
            Assert.assertEquals(sum, seq.get(n + 1).subtract(ONE));
        }

        sum = ZERO;

        for (int n = 1; n < getMaxTests(); n += 2) {
            sum = sum.add(seq.get(n));
            Assert.assertEquals(sum, seq.get(n + 1));
        }
    }

    /**
     * Verify fourth identity (per Wikipedia): sum(iF(i)) = nF(n+2) - F(n+3) + 2
     */
    @Test
    public void verifyFourthIdentity() {
        BigInteger sum = ZERO;

        for (int n = 0; n < getMaxTests(); n++) {
            sum = sum.add(BigInteger.valueOf(n).multiply(seq.get(n)));

            BigInteger x = BigInteger.valueOf(n).multiply(seq.get(n + 2))
                                     .subtract(seq.get(n + 3)).add(TWO);
            Assert.assertEquals(sum, x);
        }
    }

    /**
     * Verify fifth identity (per Wikipedia): sum(F(i)^2) = F(n)F(n+1)
     */
    public void verifyFifthIdentity() {
        BigInteger sum = ZERO;

        for (int n = 0; n < getMaxTests(); n += 2) {
            BigInteger u = seq.get(n);
            BigInteger v = seq.get(n + 1);
            sum = sum.add(u.pow(2));
            Assert.assertEquals(sum, u.multiply(v));
        }
    }

    /**
     * Verify Cassini&#039;s Identity - F(n-1)F(n+1) - F(n)^2 = -1^n
     */
    @Test
    public void verifyCassiniIdentity() {
        for (int n = 2; n < getMaxTests(); n += 2) {
            BigInteger u = seq.get(n - 1);
            BigInteger v = seq.get(n);
            BigInteger w = seq.get(n + 1);

            BigInteger x = w.multiply(u).subtract(v.pow(2));
            Assert.assertEquals(ONE, x);
        }

        for (int n = 1; n < getMaxTests(); n += 2) {
            BigInteger u = seq.get(n - 1);
            BigInteger v = seq.get(n);
            BigInteger w = seq.get(n + 1);

            BigInteger x = w.multiply(u).subtract(v.pow(2));
            Assert.assertEquals(MINUS_ONE, x);
        }
    }

    /**
     * Verify doubling: F(2n-1) = F(n)^2 + F(n-1)^2 and F(2n) =
     * F(n)(F(n-1)+F(n+1)) = F(n)(2*F(n-1)+F(n).
     */
    @Test
    public void verifyDoubling() {
        for (int n = 1; n < getMaxTests(); n++) {
            BigInteger u = seq.get(n - 1);
            BigInteger v = seq.get(n);
            BigInteger w = seq.get(n + 1);

            BigInteger x = v.multiply(v).add(u.pow(2));
            Assert.assertEquals(seq.get((2 * n) - 1), x);

            x = v.multiply(u.add(w));
            Assert.assertEquals(seq.get(2 * n), x);

            x = v.multiply(v.add(TWO.multiply(u)));
            Assert.assertEquals(seq.get(2 * n), x);
        }
    }

    /**
     * Verify tripling.
     */
    @Test
    public void verifyTripling() {
        for (int n = 1; n < getMaxTests(); n++) {
            BigInteger u = seq.get(n - 1);
            BigInteger v = seq.get(n);
            BigInteger w = seq.get(n + 1);

            BigInteger x = TWO.multiply(v.pow(3))
                              .add(THREE.multiply(v).multiply(u).multiply(w));
            Assert.assertEquals(seq.get(3 * n), x);

            x = w.pow(3).add(THREE.multiply(w).multiply(v.pow(2)))
                 .subtract(v.pow(3));
            Assert.assertEquals(seq.get((3 * n) + 1), x);

            x = w.pow(3).add(THREE.multiply(w.pow(2)).multiply(v)).add(v.pow(3));
            Assert.assertEquals(seq.get((3 * n) + 2), x);
        }
    }
}

Lucas Sequence

  1. public class LucasNumberTest extends AbstractRecurrenceSequenceTest {
  2.     private static final FibonacciNumber fibonacci = new FibonacciNumber();
  3.  
  4.     /**
  5.      * Constructor
  6.      */
  7.     public LucasNumberTest() throws NoSuchMethodException {
  8.         super(LucasNumber.class);
  9.     }
  10.  
  11.     /**
  12.      * Get number of tests to run.
  13.      */
  14.     @Override
  15.     public int getMaxTests() {
  16.         return 300;
  17.     }
  18.  
  19.     /**
  20.      * Verify the definition is properly implemented.
  21.      *
  22.      * @return
  23.      */
  24.     @Test
  25.     @Override
  26.     public void verifyDefinition() {
  27.         for (int n = 2; n < getMaxTests(); n++) {
  28.             BigInteger u = seq.get(n);
  29.             BigInteger v = seq.get(n - 1);
  30.             BigInteger w = seq.get(n - 2);
  31.             Assert.assertEquals(u, v.add(w));
  32.         }
  33.     }
  34.  
  35.     /**
  36.      * Verify initial terms.
  37.      */
  38.     @Test
  39.     @Override
  40.     public void verifyInitialTerms() {
  41.         verifyInitialTerms(Arrays.asList(TWO, ONE, THREE, FOUR, SEVEN, ELEVEN,
  42.                 BigInteger.valueOf(18), BigInteger.valueOf(29)));
  43.     }
  44.  
  45.     /**
  46.      * Verify Lucas properties.
  47.      */
  48.     @Test
  49.     public void verifyLucas() {
  50.         // L(n) = F(n-1) + F(n+1)
  51.         for (int n = 2; n < getMaxTests(); n++) {
  52.             Assert.assertEquals(seq.get(n),
  53.                 fibonacci.get(n - 1).add(fibonacci.get(n + 1)));
  54.         }
  55.     }
  56.  
  57.     /**
  58.      *  F(2n) = L(n)F(n)
  59.      */
  60.     @Test
  61.     public void verifyLucas2() {
  62.         for (int n = 2; n < getMaxTests(); n++) {
  63.             Assert.assertEquals(fibonacci.get(2 * n),
  64.                 seq.get(n).multiply(fibonacci.get(n)));
  65.         }
  66.     }
  67.  
  68.     /**
  69.      * F(n) = (L(n-1)+ L(n+1))/5
  70.      */
  71.     @Test
  72.     public void verifyLucas3() {
  73.         for (int n = 2; n < getMaxTests(); n++) {
  74.             Assert.assertEquals(FIVE.multiply(fibonacci.get(n)),
  75.                 seq.get(n - 1).add(seq.get(n + 1)));
  76.         }
  77.     }
  78.  
  79.     /**
  80.      * L(n)^2 = 5 F(n)^2 + 4(-1)^n
  81.      */
  82.     @Test
  83.     public void verifyLucas4() {
  84.         for (int n = 2; n < getMaxTests(); n += 2) {
  85.             Assert.assertEquals(seq.get(n).pow(2),
  86.                 FIVE.multiply(fibonacci.get(n).pow(2)).add(FOUR));
  87.         }
  88.  
  89.         for (int n = 1; n < getMaxTests(); n += 2) {
  90.             Assert.assertEquals(seq.get(n).pow(2),
  91.                 FIVE.multiply(fibonacci.get(n).pow(2)).subtract(FOUR));
  92.         }
  93.     }
  94. }
public class LucasNumberTest extends AbstractRecurrenceSequenceTest {
    private static final FibonacciNumber fibonacci = new FibonacciNumber();

    /**
     * Constructor
     */
    public LucasNumberTest() throws NoSuchMethodException {
        super(LucasNumber.class);
    }

    /**
     * Get number of tests to run.
     */
    @Override
    public int getMaxTests() {
        return 300;
    }

    /**
     * Verify the definition is properly implemented.
     *
     * @return
     */
    @Test
    @Override
    public void verifyDefinition() {
        for (int n = 2; n < getMaxTests(); n++) {
            BigInteger u = seq.get(n);
            BigInteger v = seq.get(n - 1);
            BigInteger w = seq.get(n - 2);
            Assert.assertEquals(u, v.add(w));
        }
    }

    /**
     * Verify initial terms.
     */
    @Test
    @Override
    public void verifyInitialTerms() {
        verifyInitialTerms(Arrays.asList(TWO, ONE, THREE, FOUR, SEVEN, ELEVEN,
                BigInteger.valueOf(18), BigInteger.valueOf(29)));
    }

    /**
     * Verify Lucas properties.
     */
    @Test
    public void verifyLucas() {
        // L(n) = F(n-1) + F(n+1)
        for (int n = 2; n < getMaxTests(); n++) {
            Assert.assertEquals(seq.get(n),
                fibonacci.get(n - 1).add(fibonacci.get(n + 1)));
        }
    }

    /**
     *  F(2n) = L(n)F(n)
     */
    @Test
    public void verifyLucas2() {
        for (int n = 2; n < getMaxTests(); n++) {
            Assert.assertEquals(fibonacci.get(2 * n),
                seq.get(n).multiply(fibonacci.get(n)));
        }
    }

    /**
     * F(n) = (L(n-1)+ L(n+1))/5
     */
    @Test
    public void verifyLucas3() {
        for (int n = 2; n < getMaxTests(); n++) {
            Assert.assertEquals(FIVE.multiply(fibonacci.get(n)),
                seq.get(n - 1).add(seq.get(n + 1)));
        }
    }

    /**
     * L(n)^2 = 5 F(n)^2 + 4(-1)^n
     */
    @Test
    public void verifyLucas4() {
        for (int n = 2; n < getMaxTests(); n += 2) {
            Assert.assertEquals(seq.get(n).pow(2),
                FIVE.multiply(fibonacci.get(n).pow(2)).add(FOUR));
        }

        for (int n = 1; n < getMaxTests(); n += 2) {
            Assert.assertEquals(seq.get(n).pow(2),
                FIVE.multiply(fibonacci.get(n).pow(2)).subtract(FOUR));
        }
    }
}

Conclusion

Obviously developers rarely need to compute Fibonacci numbers unless they’re working on Project Euler problems or at a job interview. This code isn’t going to have direct utility.

At the same time it’s a powerful demonstration of the value of investing an hour or two in research even if you’re sure you already know everything you need to know. You probably don’t need BigInteger implementation but some people might consider the O(lg(n)) approach preferable to the estimate using powers of φ, or could make good use of the relationships discussed on the MathWorld and Wikipedia pages.

Source Code

The good news is that I have published the source code for this… and the bad news is it’s part of ongoing doodling when I’m doing Project Euler problems. (There are no solutions here – it’s entirely explorations of ideas inspired by the problems. So the code is a little rough and should not be used to decide whether or not to bring me in for an interview (unless you’re impressed): http://github.com/beargiles/projecteuler.

Comments
No Comments »
Categories
Uncategorized
Comments rss Comments rss
Trackback Trackback

Archives

  • May 2020 (1)
  • March 2019 (1)
  • August 2018 (1)
  • May 2018 (1)
  • February 2018 (1)
  • November 2017 (4)
  • January 2017 (3)
  • June 2016 (1)
  • May 2016 (1)
  • April 2016 (2)
  • March 2016 (1)
  • February 2016 (3)
  • January 2016 (6)
  • December 2015 (2)
  • November 2015 (3)
  • October 2015 (2)
  • August 2015 (4)
  • July 2015 (2)
  • June 2015 (2)
  • January 2015 (1)
  • December 2014 (6)
  • October 2014 (1)
  • September 2014 (2)
  • August 2014 (1)
  • July 2014 (1)
  • June 2014 (2)
  • May 2014 (2)
  • April 2014 (1)
  • March 2014 (1)
  • February 2014 (3)
  • January 2014 (6)
  • December 2013 (13)
  • November 2013 (6)
  • October 2013 (3)
  • September 2013 (2)
  • August 2013 (5)
  • June 2013 (1)
  • May 2013 (2)
  • March 2013 (1)
  • November 2012 (1)
  • October 2012 (3)
  • September 2012 (2)
  • May 2012 (6)
  • January 2012 (2)
  • December 2011 (12)
  • July 2011 (1)
  • June 2011 (2)
  • May 2011 (5)
  • April 2011 (6)
  • March 2011 (4)
  • February 2011 (3)
  • October 2010 (6)
  • September 2010 (8)

Recent Posts

  • 8-bit Breadboard Computer: Good Encapsulation!
  • Where are all the posts?
  • Better Ad Blocking Through Pi-Hole and Local Caching
  • The difference between APIs and SPIs
  • Hadoop: User Impersonation with Kerberos Authentication

Meta

  • Log in
  • Entries RSS
  • Comments RSS
  • WordPress.org

Pages

  • About Me
  • Notebook: Common XML Tasks
  • Notebook: Database/Webapp Security
  • Notebook: Development Tips

Syndication

Java Code Geeks

Know Your Rights

Support Bloggers' Rights
Demand Your dotRIGHTS

Security

  • Dark Reading
  • Krebs On Security Krebs On Security
  • Naked Security Naked Security
  • Schneier on Security Schneier on Security
  • TaoSecurity TaoSecurity

Politics

  • ACLU ACLU
  • EFF EFF

News

  • Ars technica Ars technica
  • Kevin Drum at Mother Jones Kevin Drum at Mother Jones
  • Raw Story Raw Story
  • Tech Dirt Tech Dirt
  • Vice Vice

Spam Blocked

53,314 spam blocked by Akismet
rss Comments rss valid xhtml 1.1 design by jide powered by Wordpress get firefox