Solved

Lattice Multiplication Algorithm in C#

Posted on 2013-02-06
11
1,165 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 500 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 does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

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

Free learning courses: Active Directory Deep Dive

Get a firm grasp on your IT environment when you learn Active Directory best practices with Veeam! Watch all, or choose any amount, of this three-part webinar series to improve your skills. From the basics to virtualization and backup, we got you covered.

Question has a verified solution.

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

Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
This article aims to explain the working of CircularLogArchiver. This tool was designed to solve the buildup of log file in cases where systems do not support circular logging or where circular logging is not enabled
In this video, viewers are given an introduction to using the Windows 10 Snipping Tool, how to quickly locate it when it's needed and also how make it always available with a single click of a mouse button, by pinning it to the Desktop Task Bar. Int…
In this video you will find out how to export Office 365 mailboxes using the built in eDiscovery tool. Bear in mind that although this method might be useful in some cases, using PST files as Office 365 backup is troublesome in a long run (more on t…

617 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