Stepwise Progression of the Expanded
Euclidean Algorithm in PHP

HINT: The modulo % operator yields the remainder of division and the quotient is ignored.
HENCE: 5 ÷ 2 = 2.5, but 5 % 2 = 1 {1 remaining after dividing 5 by 2}.                         Refresh this page.

11 random numbers 285 257 134 265 162 388 439 249 339 51 138
multiply by 2 570 514 268 530 324 776 878 498 678 102 276
sort from left to right 102 268 276 324 498 514 530 570 678 776 878
shift to the right 0 102 268 276 324 498 514 530 570 678 776
modulo remainder 102 64 8 48 174 16 16 40 108 98 102
sort from left to right 8 16 16 40 48 64 98 102 102 108 174
shift to the right 0 8 16 16 40 48 64 98 102 102 108
modulo remainder 8 0 0 8 8 16 34 4 0 6 66
sort from left to right 4 6 8 8 8 16 34 66      
shift to the right 0 4 6 8 8 8 16 34      
modulo remainder 4 2 2 0 0 0 2 32      
sort from left to right 2 2 2 4 32            
shift to the right 0 2 2 2 4            
modulo remainder 2 0 0 0 0            

The GCD of 570, 514, 268, 530, 324, 776, 878, 498, 678, 102 and 276 is 2.


The shortcut for this page is: http://tinyurl.com/tab-gcd

Share on Facebook Share on Google+ Share this to LinkedIn Share this to LiveJournal if you have a paid account? Share this on Blogger Share this on Odnoklassniki Share this on VKontakte Share on Tumblr Share on Reddit Share on Pinterest Digg this Email this to someone

The source code in PHP for this file is here...

Up until now, the only way to deal with finding the GCD among a set of integers of greater quantity than two or three was to prime factor each of them and compare for similarities, or else compute the GCD for each and every combinatorial pair and then choose the smallest result. This expanded algorithm of Euclid provides for a more integrated approach for sets of integers greater than two.

Any version of the Euclidean Algorithm, whether it is the traditional approach of restricting ourselves to finding the GCD of only a pair of numbers, or this integrated approach among sets of numbers of indefinite quantity, hinge upon the properties which went into the construction of the Fibonacci series of numbers – but not merely the Fibonacci numbers, themselves, because the Fibonacci numbers are merely a quadratic special case of all Golden Series of Numbers stretching up to infinity of breadth. This expanded approach to finding the GCD exemplifies this breadth of complexity beyond mere pairs of numbers, because what we have overlooked up until now is that the structure of Golden Numbers Series are two-dimensional – not one-dimensional. That's why this expanded algorithm exhibits, very obviously, a tablature arrangement unlike the Fibonacci series which appears to be a mere linear progression. But to know this requires a study of the full range of Golden Ratio's existence. For that discussion, please refer to Infinite PHI.

For a really good demonstration of the traditionally restricted approach, please see this javascript method.







Division by Zero is Not the Problem;
Division is the Problem!

It could be said that defining division by zero is analogous to defining a division that results in an irrational fraction, or a repeating non-irrational fraction, because we'll always be left with a remainder no matter how accurate we try to approximate our quotient.

But better than this is to simply ignore division altogether and claim that we are performing repetitive subtractions. Now, we have to ignore neither the quotient, nor the remainder. We have to take both into consideration and give them equal merit. Whew! Doesn't peaceful coexistence feel really, really good!?

Some my want to claim that we don't get anything useful out of performing zero modulo operation upon a non-zero integer since our remainder is equal to the dividend. But we will require this when we want to get the Greatest Common Divisor from among a set of integers greater than two without resorting to any shortcuts, such as: taking them in pairs at a time, or resorting to prime factorization.

So, I think we've underestimated the significance of defining division by zero in terms of repetitive subtractions probably due to no one studying the bitwise operations of machine language computer programming, or reading Euclid's "Elements" to discover how he defined his Algorithm for finding the Greatest Common Divisor.

In other words...

GCD(a1, a2, a3, etc)

If ax != 0

AND

ax != ay for x and y and z, etc...

In plain English, no integers are zero and none of them are equal to each other...

For example...

GCD(494, 52) = 26

Step #1. Pick a direction in which to always sort these non-zero integers from smallest to largest; I'll choose from left to right...

52      494

Step #2. Shift these integers over one place to the right...

 *       52

Step #3. Fill in the missing first position with a zero...

 0       52

Step #4. Place step #3 underneath step #1...

52       494
 0        52

Step #5. Perform modulo downwards on each column...

52       494
%0       %52
------------
52        26

Step #6. Repeat from step #1 until all but one column zeros out.

26       52
%0      %26
-----------
26        0

Step #7. The last remaining column (containing a non-zero integer) is practically the answer, because it will repeat itself, indefinitely, if we didn't call it quits at this point.

Let's take another example...

GCD(99, 9, 33) = 3

 9      33       99
%0      %9      %33
-------------------
 9       6        0

 6       9
%0      %6
----------
 6       3

 3       6
%0      %3
----------
 3       0

But let's do it the other way of not letting any columns disappear...

GCD(99, 9, 33) = 3

 9      33       99
%0      %9      %33
-------------------
 9       6        0

 0       6        9
%0      %0       %6
-------------------
 0       6        3

 0       3        6
%0      %0       %3
-------------------
 0       3        0

Either way works...

So, I've just demonstrated the philosophical practicality of performing repetitive subtractions, and thus avoid the quandry of dividing by zero, by showing a concrete example of performing a non-linear variety of the Euclidean Algorithm on any set of integers greater than two in such a way that requires that we perform what appears to be division by zero while ignoring the quotient. Ignoring quotients doesn't mean that the division never occurred or else I'd never get to propel this expanded variety of the Euclidean Algorithm to its ultimate fruition!

Here is the above exampled as a JavaScript file,

gcd.js





Check out the JavaScript version of this webpage...


sTaTs