x
Solved

# Lattice Multiplication Algorithm in C#

Posted on 2013-02-06
Medium Priority
1,442 Views
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
Question by:mikerowaves
• 7
• 4

LVL 42

Expert Comment

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

ID: 38858521
Thank you.
0

LVL 42

Assisted Solution

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

``````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)
{
num = num / 10;
}

return listOfInts.ToArray();
}
``````
0

Author Comment

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

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

ID: 38862274
Any update on this?
0

LVL 42

Expert Comment

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

Accepted Solution

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);
}
else
{
}

// 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);
}
else
{
carry = 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)
{
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];

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.
}
``````
0

Author Comment

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

ID: 38862921
10x for the points.
0

Author Closing Comment

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

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.