Optimisation of algorithms

Sean^DCT4

Hi all,

I have two algorithms that run fine except they take a little longer than I would like.

The first is a Collatz Conjecture:

public class CollatzConjexture
    {
        public static int Calculate(int StartIndex, int MaxSequence)
        {
            int ChainLength = 0;
            int key = 0;
            bool ContinuteCalulating = true;
            int LongestChain = 0;
            Int64 Remainder = 0;
            
            for (int i = StartIndex; i <= MaxSequence; i++)
            {
                ChainLength = 1;
                Remainder = i;
                ContinuteCalulating = true;

                while (ContinuteCalulating)
                {
                    Remainder = CalculateCollatzConjecture(Remainder);
                    if (Remainder == 1)
                        ContinuteCalulating = false;

                    ChainLength += 1;
                }

                if (ChainLength > LongestChain)
                {
                    LongestChain = ChainLength;
                    key = i;
                }
            }
            
            return key;
        }

        private static Int64 CalculateCollatzConjecture(Int64 Number)
        {
            if (Number % 2 == 0)
                return Number / 2;
            else
                return (3 * Number) + 1;
        }
    }

The algo above takes the longest chain length with the minimum key.
key 1117065 produces a chain length of 528 making it the longest between 1 and 1.5million.

This takes about 5-7 seconds to run between the values 1 - 1,500,000

Does anyone have any ideas as to how I can improve this one?


The second is a simple factorial algorithm:

 public class Factorial
    {
        public static Int64 Calculate(int number)
        {
            Int64 returnValue = 1;

            while (number > 1)
            {
                returnValue *= number;
                number -= 1;
            }
            return returnValue;
        }
    }

Where I need to calculate a factorial of a number <20.

I'm running this in command line program C# and .NET 4


Also, these are not homework questions. Well past my uni days now

Thanks in advance.

Rabble Rabble

Is the Factorial really slow? Hard to see why, although it may exhaust the size of the INT64 fairly quickly. That seems ok. The other one is at least O(n2) and we dont really know what CalculateCollatzConjecture does. DOes it loop?

Jonathan

For the first one, you could query the processor about how many cores it has and distribute your for loop over those N cores.

EDIT: Scroll down Rabble Rabble. It is shown in the code box. Just a simple if else.

Sean^DCT4

Collatz parameters: StartIndex = 1, MaxSequence = 1500000

Pseudo code: Iterates through each in the range above and calculates the chain length for each number. http://en.wikipedia.org/wiki/Collatz_conjecture

function collatz(n) 
  while n > 1

    show n
    if n is odd then
      set n = 3n + 1
    else
      set n = n / 2
    endif

  endwhile
  
  show n

e.g. (n=10) 10 - > 5 -> 16 -> 8 -> 4 -> 2 -> 1 (Chain length: 7)
e.g. (n=13) 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (Chain length: 10)

I'm only interested in the largest chain length between 1 and 1.5million.


Thanks

COYW

Rabble Rabble wrote: »

Is the Factorial really slow? Hard to see why, although it may exhaust the size of the INT64 fairly quickly.

Yep, trying using the BigInteger in 4.0 as opposed to Int64.

Sean^DCT4

Using BigInteger increased the time by 40 seconds!! :eek:

DaSilva

I don't have C# on this pc, so I just quickly ran it on the web and it said it was a bit faster, you will have to try yourself though.

public static int Calculate(int StartIndex, int MaxSequence)
{
  int ChainLength = 0;
  int key = 0;
  int LongestChain = 0;
  Int64 Remainder = 0;
  
  for (int i = StartIndex; i <= MaxSequence; i++)
  {
      ChainLength = 1;
      Remainder = i;

      if (Remainder == 1)
      {
          ChainLength = 4;
      }

      while (Remainder != 1)
      {
          if (Remainder % 2 == 1)
          {
              Remainder = (Remainder * 3) + 1;
              ChainLength++;
          }

          if ((Remainder & (Remainder - 1)) == 0)
          {
              ChainLength += (int)Math.Log(Remainder, 2);
              break;
          }

          ChainLength++;
          Remainder >>= 1;
      }

      if (ChainLength > LongestChain)
      {
          LongestChain = ChainLength;
          key = i;
      }
  }
  
  return key;
}

Giblet

You have a while loop, you don't need a for loop. You just have to be creatve with your break conditions.

Edit: Use the max number as the while loop variable, looping over n and modifying N, and maintaining a counter than only increases when n == 1, making n = the counter.

void Calc(int start, int max)
        {
            int count = start;
            int chain = 1;
            int maxFound = 0;
            int key = 0;
            Int64 n = start;
            


            while (count < max)
            {
                if (n % 2 == 0)
                    n = n / 2;
                else
                    n = (3 * n) + 1;
                ++chain;

                if (chain > maxFound)
                {
                    maxFound = chain;
                    key = count;
                }
                if (n <= 1)
                {
                    chain = 1;
                    ++count;
                    n = count;
                }          
               
            }
            

        }

I prob ****ed up the algorithm there

DaSilva

Actually, you only need to check for a power of two after an odd number has been found, so it might be a tiny bit quicker now.

public static int Calculate(int StartIndex, int MaxSequence)
{
  int ChainLength = 0;
  int key = 0;
  int LongestChain = 0;
  Int64 Remainder = 0;
  
  for (int i = StartIndex; i <= MaxSequence; i++)
  {
      ChainLength = 1;
      Remainder = i;

      if (Remainder == 1)
      {
          ChainLength = 4;
      }

      while (Remainder != 1)
      {
          if (Remainder % 2 == 1)
          {
              Remainder = (Remainder * 3) + 1;
              ChainLength++;
              
              if ((Remainder & (Remainder - 1)) == 0)
              {
                  ChainLength += (int)Math.Log(Remainder, 2);
                  break;
              }
          }

          ChainLength++;
          Remainder >>= 1;
      }

      if (ChainLength > LongestChain)
      {
          LongestChain = ChainLength;
          key = i;
      }
  }
  
  return key;
}

Sean^DCT4

Thanks DaSilva, that really improved the performance. From ~7 to ~3seconds.

I tried to use .NET 4's Parallel library and was able to further reduce the time to ~2 seconds.

 public static class CollatzConjexture2
    {
        public static int Calculate(int StartIndex, int MaxSequence)
        {
            var nums = Enumerable.Range(StartIndex, MaxSequence);
            return nums.AsParallel()
                // compute length of chain for each number
                       .Select(n => new { key = n, len = CollatzChainLength(n) })
                // find longest chain
                       .Aggregate((max, cur) => (max.len < cur.len) || (max.len == cur.len && max.key > cur.key) ? cur : max)
                // get number that produced longest chain
                       .key;
        }

        private static int CollatzChainLength(Int64 Number)
        {
            int chainLength;
            for (chainLength = 1; Number != 1; chainLength++)
                Number = CalculateCollatzConjecture(Number);
            return chainLength;
        }

        private static Int64 CalculateCollatzConjecture(Int64 Number)
        {
            if (Number % 2 == 0)
                return Number / 2;
            else
                return (3 * Number) + 1;
        }
    }

Thanks for the help people.

COYW

Sean^DCT4 wrote: »

Using BigInteger increased the time by 40 seconds!! :eek:

That is interesting, in a bad way. Havent used it yet, just knew of its introduction, so I will take that on board. Thanks.

Tillotson

Recursive solution using memorisation.

#include <stdio.h>
#define MAX 1500000

int store[MAX] = {0};

int collatz(long n) {
        if (n < MAX && store[n] != 0)
                return store[n];

        int len = 1 + collatz(n % 2 == 0 ? n / 2 : 3 * n + 1);
        if (n < MAX) store[n] = len;
        return len;
}

int main() {
        int maxLen = 0, len;
        long maxKey = 0, key;
        store[1] = 1;

        for (key = 1; key < MAX; key++)
                if ((len = collatz(key)) > maxLen) {
                        maxLen = len;
                        maxKey = key;
                }

        printf("Length: %d, Key: %ld\n", maxLen, maxKey);
        return 0;
}

Runs pretty fast (gcc -O3):

[tillotson@brain ~]$ time ./a.out
Length: 528, Key: 1117065

real    0m0.035s
user    0m0.030s
sys     0m0.000s

Civilian_Target

For the Factorial... why not just cache key values (or common values) on the way, and run it recursively. Otherwise... I'm sure there are libraries that are optimized for this kind of stuff....

eg.

long fac(int input){
if(input == 1){
return 1;
}
else if(input == 10){
return 3628800;
}
else if....
else{
return input * fac(input - 1);
}
}