GCD Algorithm

[Berb]

Does anybody need this? It's a simple algorithm that will return the greatest common factor between two integers. If you need to find the GCD of real values then you can multiply them by a power of 10 and then divide the answer by the same power of 10.

GCD (Euclidean) Algorithm

function gcd takes integer value1, integer value2 returns integer
    local integer r
    if (value1 < value2) then
        set r = value1
        set value1 = value2
        set value2 = r
    endif
    loop
        set r = value1 - value2 * (value1/value2)
        exitwhen (r == 0)
        set value1 = value2
        set value2 = r
    endloop
    return value2
endfunction

Where should something like this be posted? The JASS section? It's but a single function.

By the way, one application of this (with conversion from reals) is timer systems. You could effectively accommodate several periodic intervals by simply finding the GCD of all of them. For example, let's say you've got 3 timers with different intervals:

0.075
0.03
0.15

This GCD algorithm will yield (after conversions to/from real values): 0.015
It's kind of nifty. I use it a lot in University.

** Maybe I should make it a text-macro instead for all those speed freaks.

 

[Magtheridon96]

If you can write an LCM function and maybe some other useful math functions (Factorial, cube root, etc..), you can submit it in the Jass section and call it MathUtils

 

[Troll-Brain]

I'm not sure if it's really visible but this thread is supposed to exist for such functions.

 

[Berb]

Not positive but the LCM is easy to find if you've got the GCD. It's just:

number1 * (number2 / gcd(number1, number2)) is the LCM.

function lcm takes integer value1, integer value2 returns integer
    return (value1 * (value2 / gcd(value1, value2)))
endfunction

So I guess this is what we got so far:

Immense Library of Mathematical Functions

library Math

function gcd takes integer value1, integer value2 returns integer
    local integer r
    if ((value1 == 0) or (value2 == 0)) then
        set value2 = 0
    else
        loop
            set r = value1 - value2 * (value1/value2)
            exitwhen (r == 0)
            set value1 = value2
            set value2 = r
        endloop
    endif
    return value2
endfunction

function lcm takes integer value1, integer value2 returns integer
    return (value1 * (value2 / gcd(value1, value2)))
endfunction

endlibrary

 

[Bribe]

I did include this in my "Fractions" library (graveyarded). Though I am not sure of a purpose of this snippet as a standalone, I would say mine is considerably shorter for some reason.

    public function GCD takes integer a, integer b returns integer
        local integer a2
        loop
            exitwhen b == 0
            set a2= a
            set a = b
            set b = ModuloInteger(a2, b)
        endloop
        return a
    endfunction

From: http://www.hiveworkshop.com/forums/graveyard-418/fractions-180062/

 

[Berb]

You used a function to calculate the remainder?

That reminds me I don't do any division-by-zero checks in my script.

By the way:

function ModuloInteger takes integer dividend, integer divisor returns integer
    local integer modulus = dividend - (dividend / divisor) * divisor

    // If the dividend was negative, the above modulus calculation will
    // be negative, but within (-divisor..0).  We can add (divisor) to
    // shift this result into the desired range of (0..divisor).
    if (modulus < 0) then
        set modulus = modulus + divisor
    endif

    return modulus
endfunction

Notice how there are no checks to see that divisor are not 0? Their modulo function fails if you give it a value of 0.

You're right though, I could take out the first bit in my gcd function that checks to see one is bigger than the other because that is done in the loop after one iteration anyways.

So I updated the code above. It no longer performs the check to see if the input is in descending order. The check to see that neither of them is 0 is necessary though. What was your logic in returning a if b is specified as 0?

We really should put together a Math "library" with a compilation of mathematical functions. I was just wondering if anybody found this useful though because it's not something I've seen in the resources sections.

 

[Bribe]

That's actually how the Fractions.py library did it, but if someone inputs "0" as a value they handled it at a different phase in the conversion process.

The version I have will simply return the wrong result, if the value 0 is passed. But it will not crash at least.

Here is output from IDLE if you pass the value 0:

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    Fraction(10,0)
  File "/Library/Frameworks/Python.framework/Versions/3.2/lib/python3.2/fractions.py", line 167, in __new__
    raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
ZeroDivisionError: Fraction(10, 0)

From memory, their function looks something like:

def gcd(a, b):
    while (b != 0):
        a, b = b, a % b
    return a

 

[Berb]

Yea by re-ordering the loop (from my example) you can actually accommodate for the 0 parameter with the loop condition. That makes things quite elegant. At the core, it's still using the Euclidean algorithm to calculate the GCD. There are some tricks you can do to speed the algorithm up though.

In the cases where your remainder is greater than 1/2 of the lower value you can actually multiply it by one more and then deal with a negative remainder which will be much smaller than the positive remainder. This will speed things up a bit in some scenarios.

 

[Magtheridon96]

function CubeRoot takes real x returns real
    return Pow(x, 0.333333333) // 9 3's are required so the Jass VM would increase the priority of this real being accurate.
endfunction

That should be a useful wrapper
Here are some more:

http://www.hiveworkshop.com/forums/1838224-post336.html

function QuadRoot takes real x returns real
    return Pow(x, 0.25)
endfunction

// Thanks Bribe:
function IsEvenNumber takes integer i returns boolean
    return i == i / 2 * 2
endfunction

function IsOddNumber takes integer i returns boolean
    return not IsEvenNumber(i)
endfunction

function IsNumberDivisibleByNumber takes integer i, integer by returns boolean
    return i == i / by * by
endfunction

http://www.hiveworkshop.com/forums/1937972-post445.html

http://www.hiveworkshop.com/forums/1968637-post497.html

http://www.hiveworkshop.com/forums/2000852-post554.html

These are most of the math snippets I can find.

 

[Berb]

Here's one that calculates the constant e to a certain exponent. The constant should also be included in this library here.

function exp takes integer n returns real
    local real top
    local real bot
    local real S     = 1
    local integer it = 1
    
    set top = n
    set bot = 1
    loop
        set S = S + (top / bot) 
        
        set it  = it + 1
        exitwhen (it > 10)
        set top = top * n
        set bot = bot * it
    endloop
    
    return S
endfunction

 

[Magtheridon96]

globals
    private Table tb
endglobals

function Exp takes integer n returns real
    local integer t = n
    local real b = 1
    local real s = 1
    local integer i = 1
    if tb.has(n) then
        set s = tb[n]
    else
        loop
            set s = s + t / b
            set i = i + 1
            exitwhen i > 10
            set t = t * t
            set b = b * i
        endloop
        set tb[n] = s
    endif
    return s
endfunction

private module Init
    private static method onInit takes nothing returns nothing
        set tb = Table.create()
    endmethod
endmodule
private struct Inits extends array
    implement Init
endstruct

I think it would be much more efficient to cache already calculated values into a Table
You can use a simple array if you want

 

[Berb]

Honestly I think that just having the constant is enough. The function I wrote isn't very useful when you've already got a function Pow, which can also return roots of the constant (which this function does not do) and calculate powers that are not integers.

How I wish we could declare static variables in functions.

Actually, I just noticed something. Why not remove the necessity of "table" and just use an array? Actually I guess it doesn't hurt, plus you can cache retarded sums like e^9001 (OVER NINE THOUSAND?!?!).