Jump to content

GCD of 2 numbers to calculate screen aspect ratio.


Recommended Posts

Posted (edited)

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

Edited by Belini
Link to post
Share on other sites

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.

EasyCodeIt - A cross-platform AutoIt implementation - Fund the development! (GitHub will double your donations for a limited time)

DcodingTheWeb Forum - Follow for updates and Join for discussion

Link to post
Share on other sites
Posted (edited)

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 by Belini
Link to post
Share on other sites
Posted (edited)

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

Func GreatestDivisor($n)
    Return $n
EndFunc

 

Edited by TheDcoder

EasyCodeIt - A cross-platform AutoIt implementation - Fund the development! (GitHub will double your donations for a limited time)

DcodingTheWeb Forum - Follow for updates and Join for discussion

Link to post
Share on other sites
Posted (edited)

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 by Belini
Link to post
Share on other sites
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.

EasyCodeIt - A cross-platform AutoIt implementation - Fund the development! (GitHub will double your donations for a limited time)

DcodingTheWeb Forum - Follow for updates and Join for discussion

Link to post
Share on other sites
Posted (edited)

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 by TheXman
Added check for 0
Link to post
Share on other sites
Posted (edited)
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 by Belini
Link to post
Share on other sites
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 :D

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

EasyCodeIt - A cross-platform AutoIt implementation - Fund the development! (GitHub will double your donations for a limited time)

DcodingTheWeb Forum - Follow for updates and Join for discussion

Link to post
Share on other sites
  • Belini changed the title to Encontrando o maior divisor de dois números (GCD)
  • Belini changed the title to GCD of 2 numbers to calculate screen aspect ratio.
Posted (edited)

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 by Belini
Link to post
Share on other sites

This is a very sub-optimal algorithm.

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

 

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to post
Share on other sites
Posted (edited)

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.

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 by Belini
Link to post
Share on other sites

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

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

 

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Link to post
Share on other sites

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.

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
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...