Solved

Lattice Multiplication Algorithm in C#

Posted on 2013-02-06
11
1,084 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: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
Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

 

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

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

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.
This article shows how to deploy dynamic backgrounds to computers depending on the aspect ratio of display
A short tutorial showing how to set up an email signature in Outlook on the Web (previously known as OWA). For free email signatures designs, visit https://www.mail-signatures.com/articles/signature-templates/?sts=6651 If you want to manage em…

820 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