Sign in to follow this  
Followers 0
greggklein

GCF

4 posts in this topic

Is there an easier way to find Greatest Common Factor:

Do

$x = Random(1,500,1)

$y = Random(1,500,1)

Until $x < $y

While $y/$x > Floor($y/$x)

$newx = $x

$x = $y-$x*Floor($y/$x)

$y = $newx

WEnd

$gcf = $x

MsgBox("","GCF","The GCF of "&$x& " and "& $y& " is "&$x)

Share this post


Link to post
Share on other sites



I knew that I should have stayed awake in math class.

I do not know the answer to you question - but here is a free bump in the forum... maybe others have a clue.


[size="1"][font="Arial"].[u].[/u][/font][/size]

Share this post


Link to post
Share on other sites

Is there an easier way to find Greatest Common Factor:

Do

$x = Random(1,500,1)

$y = Random(1,500,1)

Until $x < $y

While $y/$x > Floor($y/$x)

$newx = $x

$x = $y-$x*Floor($y/$x)

$y = $newx

WEnd

$gcf = $x

MsgBox("","GCF","The GCF of "&$x& " and "& $y& " is "&$x)

i remmeber giving a reply for this question, it's not helpful but i was there ?? ... ? maybe he post an other ones

[quote]Don't expect for a perfect life ... Expect a least troubles ones[/quote]Contact me : ass@kiss.toWhat I Have Done :Favorites Manager Mangage your favorite's folder, that's coolPC Waker For those who want to save stickersWebScipts Supporter For those who've just started with Web and WebScriptsTemporary Looker Simple but powerful to manage your Temporary folder, you know what you downloaded[UDF] _NumberFormat() Better performance on number display[UDF] _DirGet() What a folder contain [how many (hidden,normal,...) files], with one line of code[UDF] _IsPressEs() Just like _IsPress() but for a group of keys

Share this post


Link to post
Share on other sites

#cs ----------------------------------------------------------------------------

 AutoIt Version: 3.2.10.0
 Author:         Greatest Common Denominator (converted from C, http://en.wikipedia.org/wiki/Greatest_common_divisor)

 Script Function:
    Find GCD of two positive numbers

#ce ----------------------------------------------------------------------------

$result = gcd(12,18)
ConsoleWrite($result & @CRLF)

$result = gcd(5,0)
ConsoleWrite($result & @CRLF)

$result = gcd(42,56)
ConsoleWrite($result & @CRLF)

$result = gcd(18,84)
ConsoleWrite($result & @CRLF)

Func gcd($u, $v)

    Local $shift = 0
    Local $diff
 
    ; GCD(0,x) := x
    If $u = 0 OR $v = 0 Then Return BitOr($u,$v)
 
    ; Let shift := lg K, where K is the greatest power of 2 dividing both u and v.
    While $shift <= BitAnd(BitOr($u,$v),1) = 0 ;This line looks wrong but it works -WeaponX

        $u = BitShift ($u, 1)
        $v = BitShift ($v, 1)
        
        $shift += 1
    WEnd

    While NOT BitAnd($u,1)
      $u = BitShift ($u, 1)
    WEnd
 
    ; From here on, u is always odd.
    Do
        While NOT BitAnd($v,1) ;Loop X
          $v = BitShift ($v, 1)
        WEnd
 
        ;/* Now u and v are both odd, so diff(u, v) is even. Let u = min(u, v), v = diff(u, v)/2.
        If $u <= $v Then
            $v -= $u
        Else
            $diff = $u - $v
            $u = $v
            $v = $diff
        EndIf
        $v = BitShift ($v, 1)
    Until $v = 0
 
    Return BitShift ($u, $shift)
EndFunc

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0