CODEWITHSUNDEEP
c#.netstack-overflowbigintegerfibonacci
A. Abramov
A. Abramov

Reputation: 1865

Fibonacci with huge numbers in c#

I`m trying to find the first fib number to contain 1000 digits. Because i have no data-type capeable of holding such a number, i created a class called hugeNumber which holds the digits in a list, with a decimal base. I get a stack overflow at the generation of the list for the "hugenum" class - I am not sure why (is it really not the right way to do it? Is there a better way?)

Here's my code:

class hugeNum
{
    List<int> digits = new List<int>();
    public hugeNum(int basic)
    {
        digits.Add(basic);
    }
    public hugeNum()
    {
    }
    public static hugeNum operator +(hugeNum first, hugeNum second)
    {
        hugeNum generated = new hugeNum();
        hugeNum finalIter = null;
        int carry = 0;
        int i = 0;
        for (i = 0; i<second.digits.Count && i<first.digits.Count; i++)
        {
            generated.digits.Add(first.digits[i] + second.digits[i] + carry);
            if (generated.digits[i] >= 10)
            {
                carry = 1;
                generated.digits[i] -= 10;
            }
            else
                carry = 0;
        }
        finalIter = first;
        if (i==first.digits.Count)
        {
            finalIter = second;
        }
        while (i<finalIter.digits.Count)
        {
            generated.digits.Add(finalIter.digits[i]);
            i++;
        }
        return generated;
    }
    public int amountOfDigits()
    {
        return this.digits.Count;
    }
}
class Program
{
    public static int fibHugesUntilIter(hugeNum huge1, hugeNum huge2, int reqDigits, int iter)
    {
        if (huge2.amountOfDigits() == reqDigits)
            return iter;
        return fibHugesUntilIter(huge2, huge1 + huge2, reqDigits, iter + 1);
    }
    static void Main(string[] args)
    {
        Console.WriteLine(fibHugesUntilIter(new hugeNum(1), new hugeNum(1), 1000, 1));
    }
}

Upvotes: 2

Views: 1781

Answers (1)

AndreyAkinshin
AndreyAkinshin

Reputation: 19031

You can use BigInteger without recursion:

public static int FibHugesUntil(BigInteger huge1, BigInteger huge2, int reqDigits)
{
    int number = 1;
    while (huge2.ToString().Length < reqDigits)
    {
        var huge3 = huge1 + huge2;
        huge1 = huge2;
        huge2 = huge3;
        number++;
    }
    return number;
}

static void Main(string[] args)
{
    Console.WriteLine(FibHugesUntil(BigInteger.Zero, BigInteger.One, 1000));
}

Answer: 4782

Upvotes: 6

Related Questions