GCF

[greggklein]

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)

[herewasplato]

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.

[d4rk]

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

[weaponx]

expandcollapse popup

#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