Invariant Properties

  • rss
  • Home

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.

Categories
Uncategorized
Comments rss
Comments rss
Trackback
Trackback

« Something Worse Than IInterface Getting an Infinite List of Primes in Java »

Leave a Reply

Click here to cancel reply.

You must be logged in to post a comment.

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,793 spam blocked by Akismet
rss Comments rss valid xhtml 1.1 design by jide powered by Wordpress get firefox