Infinite Sequence Part III - Fibonacci

Last post, I had described about how to create based class for infinite sequence, and create a simple generic sequence. This post, we will move on to Fibonacci sequence.

Each Fibonacci number is the sum of 2 preceding number. First and second Fibonacci numbers are 0 and 1. Third Fibonacci number is the sum of First and Second (0+1) equal to 1. And forth Fibonacci number is the sum of Second and Third number (1+1) equal to 2. First 20 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

Now let's start coding Fibonacci.

public class Fibonacci : BaseSequence<BigInteger> {
    protected override IEnumerable<BigInteger> Enumerate() {
        BigInteger value = BigInteger.Zero;
        BigInteger value2 = BigInteger.One;

        yield return value;
        yield return value2;
        while (true) {
            value += value2;
            yield return value;
            value2 += value;
            yield return value2;
        }
    }
}

Just few lines of code, Fibonacci sequence is finished! Value and value2 return value alternately. Value variable return value in odd position. And value2 return value in even position.

Test Fibonacci sequence with projecteuler.net questions.
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x < 1000000).Where(x => x % 2 == 0).Sum()
);
//1089154

What is the first term in the Fibonacci sequence to contain 1000 digits?

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x.ToString(10).Length < 1000).Count()
);
//4782

Next post, we will go to much harder sequence, which is Prime sequence.

Infinite Sequence Part II - GenericSequence

Last post, I had introduce about infinite sequence. Infinite sequence is list that has infinity items. This part I will show how to create class for infinite sequence. Now let's start coding.

Begin with creating the based class. Its based class name is BaseSequence and it is generic typed. This class represents based class of all sequences.

//Fix: 2008-03-08 - Cut off unused ..OrDefault methods
public abstract class BaseSequence<T> {
    protected abstract IEnumerable<T> Enumerate();

    public T ElementAt(int index) {
        return Enumerate().ElementAt(index);
    }
    public T First() {
        return Enumerate().First();
    }
    public T First(Func<T, bool> predicate) {
        return Enumerate().First(predicate);
    }
    public IEnumerable<T> Take(int count) {
        return Enumerate().Take(count);
    }
    public IEnumerable<T> TakeWhile(Func<T, bool> predicate) {
        return Enumerate().TakeWhile(predicate);
    }
    public IEnumerable<T> TakeWhile(Func<T, int, bool> predicate) {
        return Enumerate().TakeWhile(predicate);
    }
}

Enumerate method will enumerate items indefinitely. Therefore, we have to declare it as protected. And we also have to provide methods that is able to enumerate and break from loop for a certain criteria. ElementAt method get item for a specific index. First method get the first item. Take method get list of items for a specific criteria.

And now create an easy derived class called GenericSequence. This class lets user passes a function to generate next items. User can also pass seed value, in order to set the initial value.

public class GenericSequence<T> : BaseSequence<T> {
    Func<T, T> _func;
    T _seed;

    public GenericSequence(Func<T, T> func) {
        _seed = default(T);
        _func = func;
    }
    public GenericSequence(T seed, Func<T, T> func) {
        _seed = seed;
        _func = func;
    }

    protected override IEnumerable<T> Enumerate() {
        T value = _seed;

        yield return value;
        while (true) {
            value = _func(value);
            yield return value;
        }
    }
}

Now test the class with question from projecteuler.net again :)

Find the longest sequence using a starting number under one million.
Defined n = n/2 (n is even)
and n = 3n + 1 (n is odd)
Finish when n is 1

//y is even (y = y/2), y is odd (y = 3y + 1)
Func<long, long> sequenceFunc = y =>
    (y % 2 == 0) ? y / 2 : y * 3 + 1;

//Count sequence length
Func<int, int> countSequence = x =>
    new GenericSequence<long>(x, sequenceFunc)
    .TakeWhile(y => y > 1)  //Take until y = 1
    .Count();               //Count the length

//Print out
Console.WriteLine(1.To(999999)  //Test all values < 1 million
    .OrderByDescending(countSequence)   //sort by count length
    .First()                    //Get only highest count
);

Or in short

Console.WriteLine(1.To(999999).OrderByDescending(x =>
    new GenericSequence<long>(x, y =>
        (y % 2 == 0) ? y / 2 : y * 3 + 1
    ).TakeWhile(y => y > 1).Count()
).First());
//837799

We can completed the question in one statement, even it may looked complicated. Anyway, if you create many nested loops it is also complicated and even harder to read.

Next post, we will create Fibonacci sequence ;)

Infinite Sequence Part I - Introduction

Sequence includes finite sequence and infinite sequence. Finite sequence is a set. There are many classes in .NET that represent set such as Array, List, & Collection. With classes, you can reuse its functionality. Such as you want to find whether an object is in a list you can write:

bool exists = list.Contains(obj);

Or if you want to enumerate for first 10 objects:

var newList = list.Take(10);

Infinite sequence is infinity-members of list. Basic sample of infinite sequence is Natural numbers (1,2,3,...), Odd numbers (1,3,5,...), & Even numbers (2,4,6,...). But how can you represent infinite sequence into class? Such as if I want to find whether is 4 in Odd numbers, can I write?:

bool exists = oddNumbers.Contains(4);
//false

Or take first 10 numbers in Odd sequence:

var tenOdd = oddNumbers.Take(10);
//{1,3,5,7,9,11,13,15,17,19}

Most of the time, if you deal with above questions, you may rather write:

bool isOdd = 4 % 2 == 1

and

for (int i = 1; i <= 19; i += 2)

That means you have to know functionality of the sequence in order to use it. And you have to rewrite the function everytime. Odd and Even numbers are simple. How about Fibonacci and Prime sequence? Their incremental is not linear. And to check members in the list is more complex.

Is it easier if we can check a number prime list the same as we check in simple List?

var isPrime = prime.Contains(34567);

And get the first 1000 Fibonacci value without having to write codes to generate Fibonacci value everytime.

var milFib = fib.Take(1000);

How can you represent infinite sequence into class?
Continue next post :)

BigInteger, an integer with unbounded length

Usaully, when you think of number, Int32 almost covers all requirements. Its maximum value is 2,147,483,647. It almost never overflow. Int32 is not enough? That's very rare case. But you can using Int64 which its maximum value is 9,223,372,036,854,775,807 which considers an extreamly large number. Is it possible that an operation will make Int64 be overflown? It is possible. In mathematics and cryptography, large precision calculation is needed, and data length of an integer can be extended indefinitely.

Which type shall we use next to Int64? If your answer is Int128, the answer is wrong. Next class we gonna use has no length limitation. It is an integer with unbounded length. This type is called BigInteger.

BigInteger is not included in current C# package. But now you can find BigInteger in Silverlight package. Once you install Silverlight, BigInteger can be found in [drive]:\Program Files\Microsoft Silverlight\Microsoft.Scripting.dll under the namespace Microsoft.Scripting.Math.

Let's play around BigInteger (question from projecteuler.net) :)
Find the sum of digits in 100!

BigInteger bigInt = 1;
100.DownTo(2).ForEach(x => bigInt *= x);    //Factorial 100!
Console.WriteLine(bigInt.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//648

More question :)
What is the sum of the digits of the number 2¹⁰⁰⁰?

BigInteger bi = 1;
1000.Times(x => bi *= 2);    //2¹⁰⁰⁰
Console.WriteLine(bi.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//1366

Factorial of 100 and 2 power by 1000, Int64 is generally unable to handle above questions. But BigInteger can handle it easily and fast.

As a bonus, I had written some Extensions for BigInteger. First method is for getting sum of a list of BigInteger.

public static BigInteger Sum(this IEnumerable<BigInteger> source) {
    BigInteger num = BigInteger.Zero;
    foreach (BigInteger num2 in source)
        num += num2;
    return num;
}
public static BigInteger Sum<T>(this IEnumerable<T> source, Func<T,BigInteger> selector) {
    return source.Select(selector).Sum();
}

Usage:

var list = new BigInteger[] { 1, 2, 3 };
Console.WriteLine(list.Sum());
//6

Next method is for parsing string into BigInteger:

public static BigInteger Parse(string s) {
    using (System.IO.StringReader reader = new System.IO.StringReader(s)) {
        char[] buffer = new char[10];
        int startIndex = 0;
        uint[] multiplier = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

        int count = reader.ReadBlock(buffer, 0, 9);
        BigInteger ret = int.Parse(new string(buffer, 0, count));
        if (ret.IsNegative())
            startIndex = 1;

        while (count == 9) {
            count = reader.ReadBlock(buffer, startIndex, 9);
            ret *= multiplier[count];
            ret += int.Parse(new string(buffer, 0, count + startIndex));
        }
        return ret;
    }
}
public static bool TryParse(string s, out BigInteger result) {
    try {
        result = Parse(s);
        return true;
    } catch {
        result = null;
        return false;
    }
}

Usage

BigInteger i = BigIntegerExtension.Parse("1234567890");
Console.WriteLine(i);
//1234567890

Next post, I will show you somethings bigger than BigInteger :)

How to use Extension Methods to extend C# language

Start my first blog with coding!

Usually, when we want to extend a type, we need to create a new derived type. But creating a new derived type, sometimes it is not suitable. Sometimes the extensions are so small, sometimes types are sealed and unable to be extended. Another solution is you can create new static methods. But those methods are not become parts of the type. New Visual Studio 2008 has a new feature enables you to add new methods without having to derive a type and able to create new methods that will become a part of the type. This new feature called "Extension Methods".

Interesting point is, we can use "Extension Methods" to enhance built-in types like int or IEnumerable. And that could change style of coding which totally different from C# 2.0. Do you know Ruby? Ruby is a programming language that is short and easy. Let's make C# to be as easy as Ruby.

Start with foreach. When you enumerate items in a list you use:

foreach (Object item in list)

But not in Ruby, in Ruby we just write:

list.each{|item| ...}

How easy! To make code like Ruby, put this source on your extension class.

public static void ForEach<T>(this IEnumerable<T> source, Action<T> action) {
    foreach (T item in source)
        action(item);
}
public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action) {
    int i = 0;

    foreach (T item in source)
        action(item, i++);
}

After extension, you can write:

list.ForEach(item => ...);
list.ForEach((item,index)=> ...);

Here is the example:

string[] persons = new string[] {"Jack", "Lisa", "Ryan"};
persons.ForEach(person => Console.WriteLine("Hello {0}!", person));
//Hello Jack!
//Hello Lisa!
//Hello Ryan!

persons.ForEach((person, index) => Console.WriteLine("{0}. {1}", index + 1, person));
//1. Jack
//2. Lisa
//3. Ryan

Is that ok with you? If you like Ruby style go to next method. When we run number 0 to 2 (run 3 loop) we usaully write:

for (int i = 0; i <= 2; i++)

Ruby is much easily:

0..2

or

3.times{|x| ..}

Jealous? Put this source on your extension class:

public static IEnumerable<int> To(this int from, int to) {
    for (int x = from; x <= to; x++)
        yield return x;
}
public static IEnumerable<int> DownTo(this int from, int to) {
    for (int x = from; x >= to; x--)
        yield return x;
}
public static IEnumerable<int> StepTo(this int from, int to, int step) {
    if (step > 0) {
        for (int x = from; x <= to; x += step)
            yield return x;
    } else if (step < 0) {
        for (int x = from; x >= to; x += step)
            yield return x;
    } else {
        throw new ArgumentException("Step cannot be zero.", "step");
    }
}
public static void Times(this int num, Action<int> action) {
    for (int x = 0; x < num; x++)
        action(x);
}

Now you can write:

string[] persons = new string[] { "Jack", "Lisa", "Ryan" };
0.To(2).ForEach(i => Console.WriteLine(persons[i]));
//Jack
//Lisa
//Ryan

2.DownTo(0).ForEach(i => Console.WriteLine(persons[i]));
//Ryan
//Lisa
//Jack

0.StepTo(2, 2).ForEach(i => Console.WriteLine(persons[i]));
//Ryan
//Jack
//(run 0 to 2 with step 2)

3.Times(i => Console.WriteLine(persons[i]));
//Jack
//Lisa
//Ryan

Try practical use, with question from projecteuler.net.
Add all the natural numbers below 1000 that are multiples of 3 or 5.

Console.WriteLine(1.To(999).Where(x => (x % 3 == 0) || (x % 5 == 0)).Sum());
//233168

Now we can completed question above with only one line of code. If you use C# 2.0, you will never write code like this. There are more several methods that you can extend C# from Ruby (or any other languages). Make your code shorter, your life will be easier.