Latest recipes tagged "divisor"http://code.activestate.com/recipes/tags/divisor/new/2016-03-03T07:12:28-08:00ActiveState Code RecipesExtended Euclidean Algorithm (Python)
2016-03-03T07:12:28-08:00Samuel James Ericksonhttp://code.activestate.com/recipes/users/4187478/http://code.activestate.com/recipes/578631-extended-euclidean-algorithm/
<p style="color: grey">
Python
recipe 578631
by <a href="/recipes/users/4187478/">Samuel James Erickson</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/discrete/">discrete</a>, <a href="/recipes/tags/divisor/">divisor</a>, <a href="/recipes/tags/euclid/">euclid</a>, <a href="/recipes/tags/extended/">extended</a>, <a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/greatest/">greatest</a>, <a href="/recipes/tags/logarithm/">logarithm</a>).
Revision 2.
</p>
<p>given input of integers a and b, this program returns GCD(a,b) along with integers x and y such that ax+by=GCD(a,b).</p>
GCD of an arbitrary list (Python)
2010-12-22T00:05:45-08:00Jason Schornhttp://code.activestate.com/recipes/users/4176312/http://code.activestate.com/recipes/577512-gcd-of-an-arbitrary-list/
<p style="color: grey">
Python
recipe 577512
by <a href="/recipes/users/4176312/">Jason Schorn</a>
(<a href="/recipes/tags/arbitrary/">arbitrary</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/divisor/">divisor</a>, <a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/greatest/">greatest</a>, <a href="/recipes/tags/list/">list</a>, <a href="/recipes/tags/schorn/">schorn</a>).
</p>
<p>Given an arbitrary list (of length >= 1) of positive integers, return the greatest common divisor (<code>gcd</code>) of the list.</p>
Infinite Stream Divisor (Python)
2010-07-21T12:50:17-07:00Narayana Chikkamhttp://code.activestate.com/recipes/users/4174427/http://code.activestate.com/recipes/577326-infinite-stream-divisor/
<p style="color: grey">
Python
recipe 577326
by <a href="/recipes/users/4174427/">Narayana Chikkam</a>
(<a href="/recipes/tags/divisor/">divisor</a>, <a href="/recipes/tags/infinite/">infinite</a>, <a href="/recipes/tags/stream/">stream</a>).
</p>
<p>Maintain an F.S.A to keep track of the consequent remainders as states, input symbols as driving actions on each state. O(N) is the time complexity to find the given large string [in some radix(R), for some specific divisor(D)], where N is the length of the Input String which confirms to the Language Rules under the alphabet. O(R*D) is the space complexity to keep the F.S.A in memory for lookup!</p>