Java: Calculate Fibonacci of an own data type

Question

I have to create my own implementation of the BigInteger class called GrosseZahl (German for “BigNumber”). I already have implemented these methods:

init() Converts an integer or string to an integer array.
less(GrosseZahl value) Returns true, if this number is less than value.
add(GrosseZahl summand)
mult(GrosseZahl factor)
toString()
equals(Object obj)

The last method I have to implement is fib() that calculates the Fibonacci number of this GrosseZahl. I have to use a helper method to calculate it recursively.

I ended up with the following code:

public GrosseZahl fib() {
    GrosseZahl f0 = new GrosseZahl(1);
    GrosseZahl f1 = new GrosseZahl(1);
    GrosseZahl counter = new GrosseZahl(1);

    return this.calcFib(f0, f1, counter);
}

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    if (this.equals(counter))
        return f1;

    counter = counter.add(new GrosseZahl(1));

    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

When I test the class with the following test class, I get a stack overflow error.

package java2;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class GrosseZahl_Test {

    GrosseZahl i0;
    GrosseZahl s0;
    GrosseZahl i1;
    GrosseZahl s1;
    GrosseZahl i55;
    GrosseZahl s55;
    GrosseZahl i60;
    GrosseZahl s60;
    GrosseZahl i99;
    GrosseZahl s99;
    GrosseZahl i100;
    GrosseZahl s100;
    GrosseZahl i12345;
    GrosseZahl s12345;
    GrosseZahl i47340;
    GrosseZahl s12345678901234567890;
    GrosseZahl s10345678901234567891;

    @Before
    public void setUp() throws Exception {
        i0 = new GrosseZahl(0);
        s0 = new GrosseZahl("0");
        i1 = new GrosseZahl(1);
        s1 = new GrosseZahl("1");
        i55 = new GrosseZahl(55);
        s55 = new GrosseZahl("55");
        i60 = new GrosseZahl(60);
        s60 = new GrosseZahl("60");
        i99 = new GrosseZahl(99);
        s99 = new GrosseZahl("99");
        i100 = new GrosseZahl(100);
        s100 = new GrosseZahl("100");
        i12345 = new GrosseZahl(12345);
        s12345 = new GrosseZahl("12345");
        i47340 = new GrosseZahl(47340);
        s12345678901234567890 = new GrosseZahl("12345678901234567890");
        s10345678901234567891 = new GrosseZahl("10345678901234567891");
    }

    /* ... */

    @Test
    public void testFib() {
        assertEquals("1", new GrosseZahl(0).fib().toString());
        assertEquals("1", new GrosseZahl(1).fib().toString());
        assertEquals("2", new GrosseZahl(2).fib().toString());
        assertEquals("3", new GrosseZahl(3).fib().toString());
        assertEquals("5", new GrosseZahl(4).fib().toString());
        assertEquals("8", new GrosseZahl(5).fib().toString());
        assertEquals("89", new GrosseZahl(10).fib().toString());
        assertEquals("1346269", new GrosseZahl(30).fib().toString());
    }

}

Stack overflow error message:

java.lang.StackOverflowError
    at java.util.regex.Pattern.sequence(Pattern.java:2134)
    at java.util.regex.Pattern.expr(Pattern.java:1996)
    at java.util.regex.Pattern.group0(Pattern.java:2827)
    at java.util.regex.Pattern.sequence(Pattern.java:2051)
    at java.util.regex.Pattern.expr(Pattern.java:1996)
    at java.util.regex.Pattern.compile(Pattern.java:1696)
    at java.util.regex.Pattern.<init>(Pattern.java:1351)
    at java.util.regex.Pattern.compile(Pattern.java:1028)
    at java.lang.String.replaceFirst(String.java:2166)
    at java2.GrosseZahl.init(GrosseZahl.java:38)
    at java2.GrosseZahl.<init>(GrosseZahl.java:25)
    at java2.GrosseZahl.add(GrosseZahl.java:112)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:158)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    at java2.GrosseZahl.calcFib(GrosseZahl.java:163)
    /* ... */

Update: I’ve done some research and found out that this is always 0 in the calcFib(...) method, when I run the test (GrosseZahl_Test). So it will never equals the counter and so the if statement will never be true. But why this is always 0? You can test it yourself if you insert System.out.println(this) above the if statement and run the test:

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    System.out.println(this);

    if (this.equals(counter))
        return f1;

    counter = counter.add(new GrosseZahl(1));

    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

If I use the less() method instead of the equals(), it does work:

public GrosseZahl fib() {
    GrosseZahl f0 = GrosseZahl.ONE;
    GrosseZahl f1 = GrosseZahl.ONE;
    GrosseZahl counter = new GrosseZahl(2);

    return this.calcFib(f0, f1, counter);
}

private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
    GrosseZahl f2;

    System.out.println(this);

    if (this.less(counter))
        return f1;

    counter = counter.add(GrosseZahl.ONE);
    f2 = f0.add(f1);
    f0 = f1;

    return calcFib(f1, f2, counter);
}

This is all code of the class GrosseZahl:

package java2;

import java.util.Arrays;

public class GrosseZahl {

    private int[] digits;
    private int length;
    private String value;

    public GrosseZahl(int value) {
        this.value = Integer.toString(value);
        this.init();
    }

    public GrosseZahl(String value) {
        this.value = value;
        this.init();
    }

    private void init() throws NumberFormatException {
        String[] digits;
        String value = this.value;

        if (value.charAt(0) == '-')
            throw new NumberFormatException("Number must be non-negative.");

        if (!value.matches("\\d+"))
            throw new NumberFormatException("Number must only contain digits.");

        value = value.replaceFirst("^0+(?!$)", "");
        digits = value.split("");

        this.length = digits.length;
        this.digits = new int[this.length];

        for (int i = 0; i < this.length; i++) {
            this.digits[i] = Integer.parseInt(digits[i]);
        }
    }

    public boolean less(GrosseZahl value) {
        if (this.length < value.length)
            return true;

        if (this.length == value.length)
            for (int i = 0; i < this.length; i++) {
                if (this.digits[i] < value.digits[i])
                    return true;
                if (this.digits[i] > value.digits[i])
                    return false;
            }

        return false;
    }

    public GrosseZahl add(GrosseZahl summand) {
        GrosseZahl a;
        GrosseZahl b;
        GrosseZahl result;
        StringBuilder number;
        int carry;
        int offset;
        int sum;

        if (!this.less(summand)) {
            a = this;
            b = summand;
        } else {
            a = summand;
            b = this;
        }

        offset = a.length - b.length;
        carry = 0;
        number = new StringBuilder();

        for (int i = a.length - 1; i >= 0; i--) {
            sum = a.digits[i] + carry;

            if (i >= offset)
                sum += b.digits[i - offset];

            if (sum > 9)
                carry = 1;
            else
                carry = 0;

            /*
             * We append the digit because it uses less memory than prepending.
             */
            number.append(sum % 10);
        }

        /*
         * If carry is still one we need to append an one.
         */
        if (carry == 1) {
            number.append(1);
        }

        /*
         * Since we’ve appended the numbers we need to reverse the order.
         */
        result = new GrosseZahl(number.reverse().toString());

        return result;
    }

    public GrosseZahl mult(GrosseZahl factor) {
        GrosseZahl a;
        GrosseZahl b;
        GrosseZahl result;

        a = this;
        b = factor;
        result = new GrosseZahl(0);

        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < b.length; j++) {
                int zeroes = a.length - i + b.length - j - 2;
                int c = a.digits[i] * b.digits[j];

                StringBuilder sum = new StringBuilder();

                sum.append(c);

                for (int k = 0; k < zeroes; k++)
                    sum.append(0);

                result = result.add(new GrosseZahl(sum.toString()));
            }

        return result;
    }

    public GrosseZahl fib() {
        GrosseZahl f0 = new GrosseZahl(1);
        GrosseZahl f1 = new GrosseZahl(1);
        GrosseZahl counter = new GrosseZahl(1);

        return this.calcFib(f0, f1, counter);
    }

    private GrosseZahl calcFib(GrosseZahl f0, GrosseZahl f1, GrosseZahl counter) {
        GrosseZahl f2;

        if (this.equals(counter))
            return f1;

        counter = counter.add(new GrosseZahl(1));

        f2 = f0.add(f1);
        f0 = f1;

        return calcFib(f1, f2, counter);
    }

    @Override
    public String toString() {
        StringBuilder number = new StringBuilder();

        for (int digit : digits)
            number.append(digit);

        return number.toString();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        GrosseZahl other = (GrosseZahl) obj;
        if (!Arrays.equals(digits, other.digits))
            return false;
        if (length != other.length)
            return false;
        return true;
    }

}

I’m new to Java and programming at all, so it’ll nice, if somebody can explain it on this specific error. — ihmels, Apr 14 '15 at 15:07
you save much when you introduce a constant for/replace all occureneces of `new GrosseZahl("1")` ...and if it still does not help you **need to abandon the recursive approach**, and try it iterative! — xerx593, Apr 14 '15 at 15:50

Mark · Answer 1 · 2015-04-14T15:39:10.137

2

In Java there are two types of logical space you can operate on: the heap allocated with the new keyword; and the stack. To perform any instruction in Java the operands must be pushed on to the stack and after the operation is complete the result replaces the operands on the stack. For each method invocation you are push arguments onto the stack which are not removed until the method returns.

Your problem above is you are attempting to use the stack recursively in the method java2.GrosseZahl#calcFib/3. The common approach to dealing with this problem is convert the algorithm to use heap space, which has a lot more space available.

edited Apr 14 '15 at 15:39

answered Apr 14 '15 at 15:30

Mark

1,128
13
21

How do I convert the algorithm to use heap space? – ihmels Apr 14 '15 at 16:52
Remove the tail call at the end of `calcFib/3`, using a logical not of the if condition as the terminal condition of a while statement with the scope from the removed if statement to the end of the method. You would then return result upon termination of the while loop. I've made the assumption your class is equivalent to BigDecimal in all properties, including immutability. Honestly this kind of conversion is nontrivial and should be thought through to ensure all invariant conditions still hold true after your refactoring. – Mark Apr 14 '15 at 17:38
@YannickIhmels you can compute fhe fibonacci series either with dynamic programming (so you do it bottom up and cache previous results) or you can do it analytical. Another way is obviously to increase teh stack size, which is also possible. – Thomas Jungblut Apr 14 '15 at 20:13

score 1 · Answer 2 · edited May 23 '17 at 11:51

1

The java.lang.StackOverflowError error is caused by calling a method inside a method too many times, as explained in this answer.
In this particular case the problem is caused by calling a method from itself (also known as recursion)

private GrosseZahl calcFib(...) {
  ...
  return calcFib(f1, f2, counter);
}

While this is a correct way to calculate the Fibonacci number, it is prone to StackOverflowError because the number of nested method calls increases exponentially. To fix this problem one must use an algorithm without recursion:

private static GrosseZahl calcFib(GrosseZahl x) {
    if(x.equals(GrosseZahl.ZERO)) {
        return GrosseZahl.ZERO;
    } 
    else if( x.equals(GrosseZahl.ONE)) {
        return GrosseZahl.ONE;
    }
    GrosseZahl xn;
    GrosseZahl xn_1 = GrosseZahl.ONE;
    GrosseZahl xn_2 = GrosseZahl.ZERO;
    GrosseZahl n = new GrosseZahl(2);
    do {
        xn = xn_1.add(xn_2);
        xn_2 = xn_1;
        xn_1 = xn;
        n = n.add(GrosseZahl.ONE);
    }
    while(n.less(x));
    return xn;
}

public static final GrosseZahl ZERO = new GrosseZahl(0);
public static final GrosseZahl ONE = new GrosseZahl(1);

edited May 23 '17 at 11:51

Community

1
1

answered Apr 14 '15 at 20:40

Richard

527
3
9

Unless you have `GrosseZahl` check and return the constants `ZERO` and `ONE` the first two if conditions will fail. The double equals infix operator performs physical identity where you desire logical identity. Change the if conditions to utilize the `equals(Object)` or `equals(Grosse)` methods to ensure correctness. – Mark Apr 14 '15 at 21:50
Fixed the code as suggested @Mark, thanks. – Richard Apr 15 '15 at 18:58
Thank you. The iterative approach is much better. But I must use the recursive one because my professor want it. Now I comment out the recursive method and explain in a comment, why I use the iterative method. – ihmels Apr 15 '15 at 19:38
@YannickIhmels Now that you have both you could leave both in and use the recursive version for small numbers and the interative version for large numbers. Then you comment why you did that. – Richard Apr 16 '15 at 13:09

Java: Calculate Fibonacci of an own data type

2 Answers2