Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Lattice Multiplication Algorithm in C#

Posted on 2013-02-06
11
Medium Priority
?
1,262 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 4
11 Comments
 
LVL 42

Expert Comment

by:sedgwick
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:sedgwick
sedgwick 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
What is SQL Server and how does it work?

The purpose of this paper is to provide you background on SQL Server. It’s your self-study guide for learning fundamentals. It includes both the history of SQL and its technical basics. Concepts and definitions will form the solid foundation of your future DBA expertise.

 

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:sedgwick
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:sedgwick
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

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

International Data Corporation (IDC) prognosticates that before the current the year gets over disbursing on IT framework products to be sent in cloud environs will be $37.1B.
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
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…

670 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