GCD of 2 numbers to calculate screen aspect ratio.

[Belini]

Existe no Autoit alguma função no Autoit capaz de retornar o maior divisor de um número com um resultado inteiro?

Edited May 17, 2022 by Belini

[TheDcoder]

Are you asking about the Greatest common divisor? There's no function for it in AutoIt but you can translate the functions in Wikipedia to AutoIt

Maybe someone already did that in an UDF but I don't know of any.

[Belini]

It wouldn't actually be the greatest common divisor because it's just one number I need and the greatest common divisor would be applied to more than one number.

Edited May 17, 2022 by Belini

[TheDcoder]

Well, the greatest divisor of any number is the number itself, the dividend will always be 1. Here's the function

Func GreatestDivisor($n)
    Return $n
EndFunc

 

Edited May 17, 2022 by TheDcoder

[Belini]

True then would be the maximum divide discarding divide by itself

EDITED: I'm trying to find a simpler way to calculate the screen's aspect ratio so I need the greatest divisor of a number except dividing the number by itself.

 

Edited May 17, 2022 by Belini

[TheDcoder]

7 minutes ago, Belini said:

True then would be the maximum divide discarding divide by itself

Then it would just be half of the number, and you'll get a dividend of 2.

[TheXman]

Here's one way that it could be done.  Loop backwards from the number, finding the first evenly divisible number using Mod():

Const $SOME_INT = 1247

ConsoleWrite(StringFormat("The greatest divisor of %i (that isn't %i) is %i", _
                          $SOME_INT, _
                          $SOME_INT, _
                          greatest_divisor($SOME_INT)) & @CRLF)

Func greatest_divisor($iInt)
    If $iInt = 0        Then Return SetError(-1, 0, 0)
    If Not IsInt($iInt) Then Return SetError(-2, 0, 0)

    For $i = ($iInt - 1) To 1 Step -1
        If Mod($iInt, $i) = 0 Then Return $i
    Next
EndFunc

Example output:

The greatest divisor of 1247 (that isn't 1247) is 43

 

Edited May 17, 2022 by TheXman
Added check for 0

[Belini]

1 hora atrás, TheDcoder disse:

Então seria apenas metade do número, e você obteria um dividendo de 2.

Você está certo novamente, então o que eu realmente preciso é o máximo divisor comum para dois números

Citar

Aqui está uma maneira que poderia ser feito. Faça um loop para trás a partir do número, encontrando o primeiro número divisível usando Mod():

obrigado @TheXman, mas agora vejo o que realmente preciso é GCD

Exemplo:
proporção de 1024x768
1024|768 GCD = 256
1024/256=4
768/256=3
Resultado = 4:3

 

 

Edited May 17, 2022 by Belini

[TheDcoder]

2 minutes ago, Belini said:

You're right again, so what I really need is the greatest common divisor for two numbers

Then we're back to the start, just take a look at the wiki article for GCD

There's no simple formula but Wikipedia mentions all of the popular ones.

[Belini]

I think I managed to solve

Global $GCD, $ASP_RAT

Aspect_Ratio(@DesktopWidth, @DesktopHeight)

ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $GCD & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $ASP_RAT & @CRLF)

Func Aspect_Ratio($Width = 0, $Height = 0)
    Local $GUARD, $INT[3]
    $INT[1] = $Width
    $INT[2] = $Height
    For $i = $INT[2] To 1 Step -1
        If Mod($INT[2], $i) = 0 Then $GUARD &= "|" & $i & "|"
    Next
    For $i = $INT[1] To 1 Step -1
        If Mod($INT[1], $i) = 0 Then
            If StringInStr($GUARD, "|" & $i & "|") Then
                $GCD = $i
                ExitLoop
            EndIf
        EndIf
    Next
    $ASP_RAT = ($INT[1] / $GCD) & ":" & ($INT[2] / $GCD)
EndFunc   ;==>Aspect_Ratio

 

Edited May 18, 2022 by Belini

[jchd]

This is a very sub-optimal algorithm.

expandcollapse popup

Local $t
$t = TimerInit()
For $i = 1 To 1000
Local $aGCD = _Aspect_Ratio(@DesktopWidth, @DesktopHeight)
Next
ConsoleWrite(TimerDiff($t) & @LF)
ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $aGCD[0] & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $aGCD[1] & ':' & $aGCD[2] & @CRLF)


Func _Aspect_Ratio($n, $p)
    Local $a = [0, $n, $p]
    While $a[2] <> 0
        $a[0] = $a[2]
        $a[2] = Mod($a[1], $a[2])
        $a[1] = $a[0]
    WEnd
    $a[1] = $n / $a[0]
    $a[2] = $p / $a[0]
    Return $a
EndFunc

;-------------------

Global $GCD, $ASP_RAT, $INT[3]

$t = TimerInit()
For $i = 1 To 1000
Aspect_Ratio(@DesktopWidth, @DesktopHeight)
Next
ConsoleWrite(TimerDiff($t) & @LF)

ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $GCD & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $ASP_RAT & @CRLF)

Func Aspect_Ratio($Width = 0, $Height = 0)
    Local $GUARD, $INT[3], $RESULT[3]
    $INT[1] = $Width
    $INT[2] = $Height
    For $i = $INT[2] To 1 Step -1
        If Mod($INT[2], $i) = 0 Then $GUARD &= "|" & $i & "|"
    Next
    For $i = $INT[1] To 1 Step -1
        If Mod($INT[1], $i) = 0 Then
            If StringInStr($GUARD, "|" & $i & "|") Then
                $GCD = $i
                ExitLoop
            EndIf
        EndIf
    Next
    $ASP_RAT = ($INT[1] / $GCD) & ":" & ($INT[2] / $GCD)
EndFunc   ;==>Aspect_Ratio

 

[Belini]

thanks @jchd for one more option but what I did despite being a little rough is faster because it got the aspect ratio in 11 milliseconds against 31 milliseconds of your algorithm.

expandcollapse popup

Local $t
$t = TimerInit()
For $i = 1 To 1000
Local $aGCD = _Aspect_Ratio(@DesktopWidth, @DesktopHeight)
Next
ConsoleWrite("jchd = " & TimerDiff($t) & @LF)
ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $aGCD[0] & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $aGCD[1] & ':' & $aGCD[2] & @CRLF)


Func _Aspect_Ratio($n, $p)
    Local $a = [0, $n, $p]
    While $a[2] <> 0
        $a[0] = $a[2]
        $a[2] = Mod($a[1], $a[2])
        $a[1] = $a[0]
    WEnd
    $a[1] = $n / $a[0]
    $a[2] = $p / $a[0]
    Return $a
EndFunc

;-------------------

Global $GCD, $ASP_RAT

$t = TimerInit()

;For $i = 1 To 1000 ; <== Unnecessary because I already have the FOR and NEXT inside the function.
Aspect_Ratio(@DesktopWidth, @DesktopHeight)
;Next

ConsoleWrite("Belini = " & TimerDiff($t) & @LF)
ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $GCD & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $ASP_RAT & @CRLF)

Func Aspect_Ratio($Width = 0, $Height = 0)
    Local $GUARD, $INT[3]
    $INT[1] = $Width
    $INT[2] = $Height
    For $i = $INT[2] To 1 Step -1
        If Mod($INT[2], $i) = 0 Then $GUARD &= "|" & $i & "|"
    Next
    For $i = $INT[1] To 1 Step -1
        If Mod($INT[1], $i) = 0 Then
            If StringInStr($GUARD, "|" & $i & "|") Then
                $GCD = $i
                ExitLoop
            EndIf
        EndIf
    Next
    $ASP_RAT = ($INT[1] / $GCD) & ":" & ($INT[2] / $GCD)
EndFunc   ;==>Aspect_Ratio

Please test again by removing the For and Next when calling the Aspect_Ratio function

Edited May 18, 2022 by Belini

[jchd]

Can you double-check please? Yours took 11ms for one run, mine took 31ms for 1000 runs.

expandcollapse popup

Local $t
$t = TimerInit()
For $i = 1 To 1;1000
Local $aGCD = _Aspect_Ratio(@DesktopWidth, @DesktopHeight)
Next
ConsoleWrite(TimerDiff($t) & @LF)
ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $aGCD[0] & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $aGCD[1] & ':' & $aGCD[2] & @CRLF)


Func _Aspect_Ratio($n, $p)
    Local $a = [0, $n, $p]
    While $a[2] <> 0
        $a[0] = $a[2]
        $a[2] = Mod($a[1], $a[2])
        $a[1] = $a[0]
    WEnd
    $a[1] = $n / $a[0]
    $a[2] = $p / $a[0]
    Return $a
EndFunc

;-------------------

Global $GCD, $ASP_RAT, $INT[3]

$t = TimerInit()
For $i = 1 To 1;1000
Aspect_Ratio(@DesktopWidth, @DesktopHeight)
Next
ConsoleWrite(TimerDiff($t) & @LF)

ConsoleWrite("The greatest divisor of " & @DesktopWidth & " and " & @DesktopHeight & " is " & $GCD & @CRLF)
ConsoleWrite("Aspect Ratio of " & @DesktopWidth & "x" & @DesktopHeight & " is " & $ASP_RAT & @CRLF)

Func Aspect_Ratio($Width = 0, $Height = 0)
    Local $GUARD, $INT[3], $RESULT[3]
    $INT[1] = $Width
    $INT[2] = $Height
    For $i = $INT[2] To 1 Step -1
        If Mod($INT[2], $i) = 0 Then $GUARD &= "|" & $i & "|"
    Next
    For $i = $INT[1] To 1 Step -1
        If Mod($INT[1], $i) = 0 Then
            If StringInStr($GUARD, "|" & $i & "|") Then
                $GCD = $i
                ExitLoop
            EndIf
        EndIf
    Next
    $ASP_RAT = ($INT[1] / $GCD) & ":" & ($INT[2] / $GCD)
EndFunc   ;==>Aspect_Ratio

My result with above code:

0.5075
The greatest divisor of 1680 and 1050 is 210
Aspect Ratio of 1680x1050 is 8:5
5.4133
The greatest divisor of 1680 and 1050 is 210
Aspect Ratio of 1680x1050 is 8:5

 

[Belini]

I hadn't noticed that the For and Next in the two examples were just for time comparison and now I see that your code is actually many times faster.