11.9.15

Finding The Order Of An Element Even Faster

The following algorithm is an optimized version of the algorithm presented here. Like the earlier
version, this algorithm also finds the order of an element by successively jumping over several elements at a time but this one jumps over 4 instead of just 2, which means it needs to iterate through only half the elements of find_order_faster(n, a) described in Finding The Order Of An Element Faster.

The logic behind this and the previous algorithm was first described in the last few paragraphs of Exponentiation Tables in Z sub n. I don't have to stop at 4 skips so long as I account for the overcount and keep the initial element a small and divisible by only itself and 1: in other words a big n requires a big jump but the result can be found in the same number of iterations as a smaller n.

For example, finding the order of a mod n for a 10 digit n can be reduced from 40 minutes to a few seconds simply by adjusting the length of the jump.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find the order of any a mod n for n = p*q where p,q > 2  
 ---------------------------------------------------- */  

function find_order_even_faster(n, a)
 {
   int aa = (a*a);  
   int aaa = (a*a*a);
   int aaaa = (a*a*a*a);
   int cur = aaaa;
   //length of the jump
   int index = 4;
   while ( cur !== 1 && cur !== a && cur !== aa && cur !== aaa)
   {
      cur = (aaaa * cur)%n;
      index = 4 + index;    
   }     
   if(cur === a){index = index-1;}
   else if(cur === aa){index = index-2;} 
   else if(cur === aaa){index = index-3;}
   return index;
 } 

Someone might be tempted to use a ternary operator to replace the if-else statements at the end but a ternary operator will be too costly in this case. Especially for bigger jumps where the number of if-else statements might exceed 100 million.

And below is the older algorithm, with cleaner variable names for reference. Looking at the two algorithms one might think of recursion to speed things up even more but I will not talk about this here.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Find the order of any a mod n for n = p*q where p,q > 2  
 ---------------------------------------------------- */  

function find_order_faster(n, a)
 {
 int aa = a*a;
 int cur = aa;
 int index = 2;
 while( cur != a && cur != 1)
 {
      cur = (aa * cur)%n;
      index = 2 + index;     
 }
 if(cur == a){indexindex - 1;}
 return index;
 } 

Outside of the while loop of both algorithms there is a number of primitive operations, and this number is proportional to the length of the jump.

In the while loop of these algorithms there are 3 things happening, namely: finding the product of the current element times a predefined constant; finding the remainder of the two; counting the number of  jumps.

Standard multiplication of two n-bit integers takes O(n2) but there is an algorithm that uses only
O(n log2 n log2 log2 n) bit operations.

Finding the quotient of two integers can be done in the same number of bit operations as the number of bit operations needed to multiply two n-bit integers.

Counting the number of jumps is fairly trivial.

By the way, it is easy to see that standard multiplication of one n-bit integer and one m-bit integer takes O(mn)

The implementation below is in Javascript because I am a computational masochist.

The 4-skip implementation of the algorithm described earlier in this post with Javascript:



The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:



The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 ways can be used for finding the order of any element mod n:
  1.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips
  5.  Using quadruple skips

Note that in the last two algorithms if n is large and a is less than 1/4 of n with non-trivial order then aa and aaaa will be relatively small as well. Both algorithms will overcount trivial orders up to the jump length.

9.9.15

Photoshop Before Photoshop

Serious digital photographers often sneer at mobile photography with its tap-to-apply filters and unrealistic colours much like film camera photographers used to scoff at digital photography with its click-to-apply Photoshop adjustments and unrealistic colours.

The argument is always the same: the latest methodology of capturing reality does not capture reality accurately.

I admit that I am one of the hipster scoffers who claim that none of the reality capturing devices invented so far capture reality accurately but that is another subject matter that I've covered already.

What I did find surprising after reading a book titled Faking It: Manipulated Photography Before Photoshop is that people have been combatting the imperfections of reality capturing devices by tampering with photos after they were taken pretty much since such devices were first introduced.

As early as 1846, only 5 years after the first calotype process was introduced allowing an unlimited number of photographs to be generated from a single negative, a man named Calvert Richards Jones altered a photograph he shot by painting over a figure in the negative in order to remove it from the processed photo because it didn't fit the scene.

Even the most hipster purists of all photographers who preached about the dangers of creating reality distortion fields by editing photographs would occasionally retouch their masterpieces. Such was the case with P. H. Emerson who would occasionally add clouds to the overexposed skies on his photographs when nobody was looking yet condoned anyone else who openly did so as well.


P.H. Emerson's  A Stiff Pull retouched

The skies in P. H. Emerson's works were overexposed not because he was secretly a lousy photographer but because the reality capturing devices at the time had a hard time processing certain types of light.

A Stiff Pull original


In those early days of photography colour had to be added after taking the photograph using gum bichromate, which was first introduced in 1855 but was not used until 1890.

The following photograph of my great great great grandfather, or greatgrandfather was taken in 1888 in Bulgaria and gum bichromate was used to allow the photographer to introduce colour and brushwork to it after it was taken. On a personal note, it looks like I've inherited his arched eyebrows but hopefully not the bushy moustache.

 Ivan Danchovsky c. 1888