Improve company productivity with a Business Account.Sign Up

x
?
Solved

Lattice Multiplication Algorithm in C#

Posted on 2013-02-06
11
Medium Priority
?
1,442 Views
Last Modified: 2013-02-11
I have a problem I need answered ASAP. I was tasked with writing a simple C# form that does a fundamentally simple but from a coding standpoint, complex mathematical task. The method is called Lattice Multiplication, and it is a simple, matrix-based way to multiply large numbers. Here is a video that will easily explain it if you are not familiar: http://www.youtube.com/watch?v=VoXJA-9WzNI

I have attached what I came up with thus far. The code is commented and fleshed out up to the point where I multiply the digits to get a linear array of two characters (the products of each multiple) per index. I am completely stumped what to do next. I came here as a last resort because I simply cannot figure this out.

This is a time sensitive matter so I would appreciate any and all help in advance.

Thank you.
default.aspx
default.aspx.cs
0
Comment
Question by:mikerowaves
  • 7
  • 4
11 Comments
 
LVL 42

Expert Comment

by:Meir Rivkin
ID: 38858506
i'm half there, let me dig the code and see if it's working properly for all numbers.
be back to you with code
0
 

Author Comment

by:mikerowaves
ID: 38858521
Thank you.
0
 
LVL 42

Assisted Solution

by:Meir Rivkin
Meir Rivkin earned 2000 total points
ID: 38858642
see the screenshot, i've tested 10k random calculations so i'm sure its working smooooooooothly :)

screenshot
void TestFigures()
        {
            var rnd = new Random();
            int iterations = 1000;
            for (int i = 0; i < iterations; i++)
            {
                var d1 = (int)Math.Floor(rnd.NextDouble() * rnd.NextDouble() * Math.Pow(10, rnd.Next(0, 5)));
                var d2 = (int)Math.Floor(rnd.NextDouble() * rnd.NextDouble() * Math.Pow(10, rnd.Next(0, 5)));
                double simple_multiply = d1 * d2;
                double lattice_multiply = LatticeMultiplication(int.Parse(d1.ToString()), int.Parse(d2.ToString()));
                Debug.Equals(simple_multiply, lattice_multiply);
            }
        }

        private double LatticeMultiplication(int num1, int num2)
        {
            if (num1 == 0 && num2 == 0) return 0;
            int[] num1Array = ConvertToIntArray(num1);
            int[] num2Array = ConvertToIntArray(num2);
            int num1arrSize = num1Array.Count();
            int num2arrSize = num2Array.Count();

            int[] accumulators = new int[num1arrSize + num2arrSize];

            int i, j, accIndex = accumulators.Count() - 1;
            for (i = 0; i < num2arrSize; i++)
            {
                for (j = 0; j < num1arrSize; j++)
                {
                    int result = num1Array[j] * num2Array[i];
                    if (result > 9)
                    {
                        accumulators[accIndex] += result % 10;
                        int tenth = accumulators[accIndex];
                        if (tenth > 9)
                        {
                            accumulators[accIndex] = tenth % 10;
                            accumulators[accIndex - 1] += tenth / 10;
                        }
                        accumulators[accIndex - 1] += result / 10;
                        tenth = accumulators[accIndex - 1];
                        if (tenth > 9)
                        {
                            accumulators[accIndex - 1] = tenth % 10;
                            accumulators[accIndex - 2] += tenth / 10;
                        }
                    }
                    else
                    {
                        accumulators[accIndex] += result;
                        int tenth = accumulators[accIndex];
                        if (tenth > 9)
                        {
                            accumulators[accIndex] = tenth % 10;
                            accumulators[accIndex - 1] += tenth / 10;
                        }
                    }
                    accIndex--;
                }
                accIndex = accumulators.Count() - 2 - i;
            }

            return double.Parse(string.Join("", accumulators.Select(n => n.ToString()).ToArray()));
        }


        private int[] ConvertToIntArray(int num)
        {
            List<int> listOfInts = new List<int>();
            while (num > 0)
            {
                listOfInts.Add(num % 10);
                num = num / 10;
            }

            return listOfInts.ToArray();
        }

Open in new window

0
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

 

Author Comment

by:mikerowaves
ID: 38860151
This works, but there are a few instances where it doesn't. For example, if you take 1000x1000, it gives you a result of 1. 1000x12 gives you a result of 21.
0
 

Author Comment

by:mikerowaves
ID: 38860163
I think the main goal of the Lattice process is to transverse a diagonal matrix as opposed to doing it this way, although this still works. Do you know what I mean?
0
 

Author Comment

by:mikerowaves
ID: 38862274
Any update on this?
0
 
LVL 42

Expert Comment

by:Meir Rivkin
ID: 38862850
This is basically what i do. Ill post a screenshot with explanation
0
 

Accepted Solution

by:
mikerowaves earned 0 total points
ID: 38862875
I actually figured out the pattern and did it myself. Here is the final code:

    // Main Multiplication Function
    private int LatticeMultiplication(int num1, int num2)
    {
        // Create integer list for total number.
        List<int> total = new List<int>(); 

        if (num1 != 0 && num2 != 0) // Proceed if no zeroes.
        {
            // Convert numbers to linear arrays and then to a matrix.
            int[] num1Array = ConvertToIntArray(num1);
            int[] num2Array = ConvertToIntArray(num2);
            string[,] mLattice = ConvertToMatrix(num1Array, num2Array); // String preserves zeroes.

            // Set x/y coordinates.
            int wall = num1Array.Count() - 1; // Right side of matrix.
            int floor = num2Array.Count() - 1; // Bottom of matrix.
            int ceiling = 0; // Top of matrix.
            int door = 0; // Left side of matrix.
            int xPos = floor;
            int yPos = wall;
            int tempX = floor;
            int tempY = wall;

            int sum = 0;
            int carry = 0;
            bool isFirst = false;

            // Transverse bottom diagonals.
            while (yPos > door - 1)
            {
                // Reset temporary values.
                tempX = xPos;
                tempY = yPos;
                isFirst = false;
                sum = carry;

                while (tempX >= ceiling && tempY <= wall)
                {
                    if (isFirst == false)
                    {
                        sum += GetValue(mLattice[tempX, tempY], 1); // Get first or second number.
                        isFirst = true; // Set alternate.
                        tempY++; // Set next diagonal position.
                    }
                    else
                    {
                        sum += GetValue(mLattice[tempX, tempY], 0);
                        isFirst = false;
                        tempX--;
                    }
                }

                // Check for tenths spot and add ones to total.
                if (sum > 9)
                {
                    carry = GetValue(sum.ToString(), 0);
                    total.Add(GetValue(sum.ToString(), 1));
                }
                else
                {
                    total.Add(GetValue(sum.ToString(), 0));
                }

                // Move left to next diagonal.
                yPos--;
            }

            // Reset values for left side diagonals.
            xPos = floor;
            yPos = door;
            sum = 0;

            // Transverse left diagonals.
            while (xPos > ceiling - 1)
            {
                // Reset temporary values.
                tempX = xPos;
                tempY = yPos;
                isFirst = true;
                sum = carry;

                while (tempX >= ceiling && tempY <= wall)
                {
                    if (isFirst == false)
                    {
                        sum += GetValue(mLattice[tempX, tempY], 1);
                        isFirst = true;
                        tempY++;
                    }
                    else
                    {
                        sum += GetValue(mLattice[tempX, tempY], 0);
                        isFirst = false;
                        tempX--;
                    }
                }

                if (sum > 9)
                {
                    carry = GetValue(sum.ToString(), 0);
                    total.Add(GetValue(sum.ToString(), 1));
                }
                else
                {
                    carry = 0;
                    total.Add(GetValue(sum.ToString(), 0));
                }

                // Move up to next diagonal.
                xPos--;
            }

            // Return a joined final value using LINQ.
            return Convert.ToInt32(string.Join("", total.Select(n => n.ToString()).ToArray().Reverse()));
        }

        // Return if zer
        return 0;
    }

    // Main Multiplication Subfunctions
    // Convert integer numbers to a split array.
    private int[] ConvertToIntArray(int num)
    {
        List<int> numArray = new List<int>();

        // Add digits one by one by looking at mod result.
        while(num > 0)
        {
            numArray.Add(num % 10);
            num = num / 10;
        }

        // Reverse array.
        numArray.Reverse();
        return numArray.ToArray();
    }

    // Convert arrays to matrix.
    private string[,] ConvertToMatrix(int[] num1Array, int[] num2Array)
    {
        // Establish given array sizes.
        int arr1Size = num1Array.Count();
        int arr2Size = num2Array.Count();

        // Establish array length.
        string[] multiplied = new string[arr1Size * arr2Size]; 
        int index = 0;

        // Create single array of multiplied numbers.
        for (int i = 0; i < arr2Size; i++)
        {
            for (int j = 0; j < arr1Size; j++)
            {
                // Multiply numbers and format with a zero if a single digit.
                multiplied[index] = (num2Array[i] * num1Array[j]).ToString("00");
                index++;
            }
        }

        // Create matrix.
        string[,] matrix = new string[arr2Size, arr1Size];

        // Add values to matrix.
        for (int i = 0; i < multiplied.Count(); i++)
        {
            matrix[i / arr1Size, i % arr1Size] = multiplied[i];
        }

        return matrix;
    }

    private int GetValue(string m, int index)
    {
        return Convert.ToInt32(m.Substring(index, 1)); // Return number according to index.
    }

Open in new window

0
 

Author Comment

by:mikerowaves
ID: 38862876
Thank you for your help though. I will accept your solution as correct as well because it is, in fact.
0
 
LVL 42

Expert Comment

by:Meir Rivkin
ID: 38862921
10x for the points.
0
 

Author Closing Comment

by:mikerowaves
ID: 38875516
I figured it out using a matrix, which was required by the project. However, sedgwick provided a solution that also works.
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
This article describes and provides a custom-made tool I wrote to give businesses a means of identifying commercial music content, without having to expend too much effort. Business recordings are easily identified from possibly illegal music files …
In response to a need for security and privacy, and to continue fostering an environment members can turn to for support, solutions, and education, Experts Exchange has created anonymous question capabilities. This new feature is available to our Pr…
When you have multiple client accounts to manage, it often feels like there aren’t enough hours in the day. With too many applications to juggle, you can’t focus on your clients, much less your growing to-do list. But that doesn’t have to be the cas…

601 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question