14.7.16

Generating Powers of 2 Faster

In a previous post I described an algorithm for generating powers of 2 mod n when n is an odd integer.

It required the generation of an array of multiples of 2 mod n that relied on consecutively adding 2 to an initial integer while checking to see if the new integer exceeds n and resetting the process thus making n iterations on an input of n and then some. This function generated the row at 2 of the multiplication table of Zn, which I then used to generate the row at 2 of the exponentiation table of Zn.

Today I propose a new function that makes only (n-1)/2 iterations on an input of n based on the observation that the row at (n+1)/2 of the exponentiation table of Zn is equivalent to the row at 2 of the exponentiation table of Zin reverse order.


In this case it is sufficient to generate the row at (n+1)/2  of the multiplication table  of Zn, which can be generated faster based on the following claim:

Claim: Every odd element of the row at (n+1)/2  of the multiplication table of Zn,is equal to the sum of the previous element and 1 starting from (n+1)/2 and every even element is also equal to the sum of the previous element and 1 starting from 1 up to (n-1)/2.

This means that at each iteration two elements of the multiplication table of Zcan be added to the array of multiples as opposed to just one and neither will exceed n by construction, therefore there's no need to add an extra check.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find all powers of 2 and (n+1)/2 mod n 
 ---------------------------------------------------- */  
//generate powers of 2 from highest to lowest exponent
function powers_of_two_backwards(n)
{
 var index = 0;
 var perm_slot =1;
 
 var perm = new Array(); var powers = new Array();
 perm = generate_faster_permutation(n);
 do{
    index = perm_slot;
    perm_slot = perm[index];
    powers.push(perm_slot); 
   }while(perm_slot != 1)
 return powers;
}
//generate row at (n+1)/2  of the multiplication table 
function generate_faster_permutation(n)
{ 
 var start = (n+1)/2;
 var end = (n-1)/2;
 var perm = new Array();
 perm.push(0);perm.push(start);
 for(i=1; i<=end; i++)
 {
     perm.push(i);
     start = start+1;
     perm.push(start);
 }
 perm.pop();  
 return perm; 
}


Here's a point and click implementation of the algorithm above.




Note: this algorithm can also be used to find the order of 2 mod n if instead of adding elements to a data structure powers_of_two_backwards(n) counts the number of iterations it makes since the number of iterations in this cycle is precisely the order of 2 and (n+1)/2 mod n.