• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1404
  • Last Modified:

Lattice Multiplication Algorithm in C#

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
mikerowaves
Asked:
mikerowaves
  • 7
  • 4
2 Solutions
 
Meir RivkinFull stack Software EngineerCommented:
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
 
mikerowavesAuthor Commented:
Thank you.
0
 
Meir RivkinFull stack Software EngineerCommented:
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
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
mikerowavesAuthor Commented:
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
 
mikerowavesAuthor Commented:
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
 
mikerowavesAuthor Commented:
Any update on this?
0
 
Meir RivkinFull stack Software EngineerCommented:
This is basically what i do. Ill post a screenshot with explanation
0
 
mikerowavesAuthor Commented:
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
 
mikerowavesAuthor Commented:
Thank you for your help though. I will accept your solution as correct as well because it is, in fact.
0
 
Meir RivkinFull stack Software EngineerCommented:
10x for the points.
0
 
mikerowavesAuthor Commented:
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: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 7
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now