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.

Everybody Uses Abstract Algebra Every Day

Although it is a new branch of Mathematics, Abstract Algebra has far reaching applications in other scientific fields like Computing Science and Physics.

Actually, everyone uses pure Abstract Algebra on a daily basis. In a few paragraphs I will show how but first here's how this new branch relates to the old branch of Elementary Algebra, which is the algebra most people learn first.

One of the fundamental algorithms of Abstract Algebra is an algorithm from Elementary Algebra called the Division algorithm, which states that when one non zero integer divides another integer, the dividend is equal to the divisor times a unique quotient plus a unique remainder.

In other words, any 2 integers a, b where b > 0 can be expressed as a = bq + r where q and r are unique integers such that 0 <= r < b where r is the remainder when a is divided by b.

For example, let a = 12 and b = 12 then r = 0 since 12 = 12*1 + 0

This is the same as saying  that 12 is congruent to 0 modulo 12 because 12 - 0 is divisible by 12.

Or in other words, 12 = 0 in the set of all integers from 0 to 11. 

It can be verified that the sum s of any two integers from the set of all integers from 0 to 11 is still in that set if it is calculated as s = 12q + r 

For example, let s = 9 + 5 = 14. While 14 is not in the set from 0 to 11, 14 can be uniquely represented as 14 = 12*1 + 2 so 14 = 2 modulo 12 

The fact that the sum of any two elements can be represented by another element in that set means that the set is closed with respect to the operation of addition, and that coupled with a few other properties is what makes this set a group under the operation of addition, it is also a ring under this and the operation of multiplication, and a blank canvas under the operation of exponentiation.

This set is called Z12 since it is the first positive 12 integers of Z and Z is the set of all integers.

Now let’s get back to how everyone uses this on a daily basis. Enter the clock. Everyone uses the clock except for a few lucky people who don’t care about concrete measurements of time. 

At some point of each day most people need to calculate how many hours are left of something, how many hours until something happens and so on. In doing so they are dealing with Abstract Algebra, or more specifically, with the abstract structure of Z12 under addition.


The table on the left of the graphic above illustrates the addition table of Z12
Note that each row in that table is shifted by 1, which makes it easy to visualize.

Since it is 9 o'clock in City A and City A is 5 hours ahead of City B then it is currently 14 o'clock in City B and since 14 = 12*1 + 2 so 14 = 2 modulo 12 then the clock in City B shows 2.


Further reading:
Algebra by Thomas W. Hungerford
The Theory of Algebraic Number Fields by David Hilbert
Applied Abstract Algebra by Lidl & Pilz
Integers, Polynomials, and Rings by Ronald S. Irving