17.2.15

Faster Multiplication Tables

I offered quite a long algorithm for generating multiplication tables of  Zp when p is prime and I argued(not very convincingly) that the multiplication tables of Zn when n is composed of 2 distinct primes are much different and would require a different algorithm.

In fact, the same algorithm can be used to generate multiplication tables of Zn when n is composed of 2 distinct primes.

When called with the following parameters: (0, 1, 15, []) the function described in Multiplication Tables returns the first (n-1)/2 rows of Z15 correctly, and then it proceeds onto pondering the meaning of life, the universe, and everything.

Input: HammerTime(0, 1, 15, [])

Output:
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,
0,2,4,6,8,10,12,14,1,3,5,7,9,11,13,
0,3,6,9,12,
0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,
0,5,10,
0,6,12,3,9,
0,7,14,6,13,5,12,4,11,3,10,2,9,1,8,

Adolescent ramblings:
0,8,1,5,9,13,2,6,10,14,3,7,11,0,5,10,0,6,12,3,9,0,7,14,6,13,5,12


To ensure the function stops short of adolescent ramblings when faced with a composite n, a small change needs to be made like so:

//Author: Marina Ibrishimova
//Purpose: Generate the first half of the multiplication table of Zn 
//without actually computing the GCD(each_row_index*each_column_index, n)
function StopHammerTime(ki, k, n, table_so_far) {  
  var len = table_so_far.length;  
  var half_table_slots = n*((n-1)/2);  
  if(len == half_table_slots) {return;}  
  else {   
   while ( ki <= (n - 1)) {  
   table_so_far.push(ki);  
   ki = ki + k;  
   }  
   len = table_so_far.length;  
   var last_inset = table_so_far[len-1];  
   var k_dist = n - last_inset;   
   var new_ki = k - k_dist;   
   var n_k = k + 1;  
   if(last_inset == n-(k-1) && k < n/2) { StopHammerTime(1, k, n, table_so_far); }  
   else if(last_inset == n-k && k < n/2) { StopHammerTime(0, n_k , n, table_so_far); }  
   else if(last_inset < n && k < n/2){ StopHammerTime(new_ki, k, n, table_so_far); }  
   }  
   return table_so_far;    
 }

StopHammerTime((0, 1, n, [])) generates the first half of any multiplication table skipping repetitions.

Input: StopHammerTime(0, 1, 15, [])

Output:
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,
0,2,4,6,8,10,12,14,1,3,5,7,9,11,13,
0,3,6,9,12,
0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,
0,5,10,
0,6,12,3,9,
0,7,14,6,13,5,12,4,11,3,10,2,9,1,8,


Note: when k = 3 the row is 0,3,6,9,12,0,3,6,9,12,0,3,6,9,12 but StopHammerTime stops short of repetitions in addition to stopping short of adolescent ramblings.

Also note: the actual output of StopHammerTime is a 1D array, the above output is just for eyeball convenience. 

Just like with addition tables, multiplication tables are also simply a shift, or a skip, or a cyclic permutation of a row, namely the row, which lists the elements of Zn.

In addition tables it was always a shift, or a skip of 1 from the row, which lists the elements of Zn.  but in multiplication tables each row k is a shift or a skip by k - 1.

Example: in the multiplication table of Z6  the row at k = 1 simply lists the elements of Z6 = [0,1,2,3,4,5] because 1 times any other integer is the integer itself:

What would the row at k = 2 of the multiplication table of Z6 look like without calculating 2*x mod 6 for every x from 0 to n-1?

Well, looking at the row at k = 1, namely [0,1,2,3,4,5], reveals that the element 2 is at index 2, which is a skip by 1 not counting 0 the first time because it is the first element of any row; the second element will be a skip by 1 after the element 0 in the row at k = 1, which is 2; the element after 2 in the row at k = 2 will be a skip by 1 after the element 2 in the row at k = 1, which is 4; the element after 4 in the row at k = 2 will be a skip by 1 after the element 4 in the row at k = 1, which is 0. Now the row at 2 has 4 elements - we keep skipping and populating it in the same manner until there are exactly 6 not necessarily unique elements because every row of  Z6 must have 6 elements by definition.

In essence, the row at k = 2 is every second element of the row at k = 1:

k=1 is [0,1,2,3,4,5]
k=2 is [0,2,4,0,2,4]

Similarly for the other rows:

Looking back at the row at k = 1, namely [0,1,2,3,4,5] reveals that k = 3  is a skip by 2 not counting 0 the first time so the row at 3 is

[0,3,0,3,0,3]

Looking back at the row at k = 1, namely [0,1,2,3,4,5] reveals that 4 is a skip by 3 not counting 0 the first time so the row at 4 is:

[0,4,2,0,4,2]

Looking back at  the row at k = 1, namely [0,1,2,3,4,5] reveals that 5 is a skip by 4 not counting 0 the first time so the row at 5 is:

[0,5,4,3,2,1]

So the table then becomes:

*  0 1 2 3 4 5
0 [0 0 0 0 0 0]
1 [0 1 2 3 4 5]
2 [0 2 4 0 2 4]
3 [0 3 0 3 0 3]
4 [0 4 2 0 4 2]
5 [0 5 4 3 2 1]

Note: It can be verified with a scientific calculator that this is indeed the multiplication table of Z sub 6  by multiplying each row by each column and then modulo 6 in case the result of multiplying each row by each column is greater than 6. Note that no such calculations were needed in the described algorithm.



The algorithm for factoring n then becomes:

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Factor n without any multiplication or addition 
 ---------------------------------------------------- */ 
  1. Populate A= [0, 1, 2, ...  n-1] 
  2. Shift A consecutively for each element in A by its index-1 with an initial starting point of 1. 
  3. If 0 is encountered AND the index at that entry where 0 is encountered is greater than 0, then stop the looping and call that index p. 
  4. Divide n by p, the result will be q, 
  5. Return p and q
Obviously, if #3, 4, 5 are omitted and replaced by a simple if statement, the entire multiplication table will be generated but who cares about that anyway.