Gcd with Static Functions of a Struct

GCD with static functions of a struct

You can use a private serial queue to ensure that only one thread can be in any of the critical sections at any instant.

class SingleSome {

    struct Static {
        private static let queue = dispatch_queue_create("SingleSome.Static.queue", nil)
        private static var instance: SingleSome?

        static func getInstance(block: () -> SingleSome) -> SingleSome {
            var myInstance: SingleSome?
            dispatch_sync(queue) {
                if self.instance == nil {
                    self.instance = block()
                }
                myInstance = self.instance
            }
            // This return has to be outside the dispatch_sync block,
            // so there's a race condition if I return instance directly.
            return myInstance!
        }

        static func remove() {
            dispatch_sync(queue) {
                self.instance = nil
            }
        }
    }

}

What is the best way to attach static methods to classes rather than to instances of a class?

I would prefer the one with RationalMath. You really don't need extension methods here, because their aim is to mimic instance methods of objects of you can't modify. But here one should use plain old static method.

A function inside a struct C++

This function inside a class is called a non-static member function.

It has an implied object parameter that is accessible through this.

When called, the object parameter is on the left of the . in class member access:

struct x {
    int data_member;
    int f(int i){
        return data_member+i;
    }
};

x y;
y.f(10);

equivalent to:

struct x {
    int data_member;
};

int f(x* _this, int i) {
   return _this->data_member + i;
}

x y;
f(&y,10);

Using template metaprogramming in C++, find the GCD of two integers

something like this?

#include <utility>
#include <iostream>

template<int a, int b> struct gcd
{
    static constexpr auto value = gcd<b, a % b>::value;
};

template<int a>
struct gcd<a, 0>
{
    static constexpr auto value = a;
};

int main()
{
    auto x = gcd<10,5>::value;

    std::cout << x << std::endl;
}

LCM of the Two Numbers

From Wikipedia (https://en.wikipedia.org/wiki/Greatest_common_divisor):

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of 8 and 12 is 4.

Using Euclid's algorithm

Formally the algorithm can be described as:

gcd(a,0)=a

gcd(a,b)=gcd(b,a mod b)

where

a mod b = a - b [ a / b ]

If the arguments are both greater than zero then the algorithm can be written in more elementary terms as follows:

gcd(a,a)=a

gcd(a,b)=gcd(a-b,b), if a > b

gcd(a,b)=gcd(a,b-a), if b > a

Sum of Greatest Common Divisor (GCD)

This is a late reply after leaving comments. I was looking back at my 'stackoverflow snippets' directory, and realised I had implemented a solution for this question (67689345), and forgot about it...

The key is to find an analytic expression for the gcd sum, which requires the factorization of (n). see: Pillai's function, or: The gcd-sum Function

Tabulating all prime factors for (n <= 1000000) at runtime is so fast that it's almost negligible to the total running time. However, I used a utility of mine to generate a table of all primes (p) <= (1000). It actually finds all primes up to (1024), but that's fine. sp_factor yields a prime factorization with multiplicity if a prime factor occurs more than once, so any repeated factors must be handled in the gcdsum function. These are required for the prime power exponents in any case.

Note: each (n) is factored to find the summation of gcd terms. We exploit the transform of the index of summation to yield:

Sample Image

Note, that the summation for (n <= 1000000) may exceed 32-bits. So a 64-bit accumulator is used. On an old laptop I'm using just now - a 2Ghz dual-core i7 - this takes less than (0.25) seconds, which should be well within the contest requirements.

The results for: n = {1, .., 5} match the contest values: {0, 1, 3, 7, 11}, while: n = 1000000 yields: 4071628673912

/******************************************************************************/

#include <inttypes.h>

/******************************************************************************/

static const uint16_t sp_lut[] =
{
    0x0002, 0x0003, 0x0005, 0x0007, 0x000b, 0x000d, 0x0011, 0x0013,
    0x0017, 0x001d, 0x001f, 0x0025, 0x0029, 0x002b, 0x002f, 0x0035,
    0x003b, 0x003d, 0x0043, 0x0047, 0x0049, 0x004f, 0x0053, 0x0059,
    0x0061, 0x0065, 0x0067, 0x006b, 0x006d, 0x0071, 0x007f, 0x0083,
    0x0089, 0x008b, 0x0095, 0x0097, 0x009d, 0x00a3, 0x00a7, 0x00ad,
    0x00b3, 0x00b5, 0x00bf, 0x00c1, 0x00c5, 0x00c7, 0x00d3, 0x00df,
    0x00e3, 0x00e5, 0x00e9, 0x00ef, 0x00f1, 0x00fb, 0x0101, 0x0107,
    0x010d, 0x010f, 0x0115, 0x0119, 0x011b, 0x0125, 0x0133, 0x0137,
    0x0139, 0x013d, 0x014b, 0x0151, 0x015b, 0x015d, 0x0161, 0x0167,
    0x016f, 0x0175, 0x017b, 0x017f, 0x0185, 0x018d, 0x0191, 0x0199,
    0x01a3, 0x01a5, 0x01af, 0x01b1, 0x01b7, 0x01bb, 0x01c1, 0x01c9,
    0x01cd, 0x01cf, 0x01d3, 0x01df, 0x01e7, 0x01eb, 0x01f3, 0x01f7,
    0x01fd, 0x0209, 0x020b, 0x021d, 0x0223, 0x022d, 0x0233, 0x0239,
    0x023b, 0x0241, 0x024b, 0x0251, 0x0257, 0x0259, 0x025f, 0x0265,
    0x0269, 0x026b, 0x0277, 0x0281, 0x0283, 0x0287, 0x028d, 0x0293,
    0x0295, 0x02a1, 0x02a5, 0x02ab, 0x02b3, 0x02bd, 0x02c5, 0x02cf,
    0x02d7, 0x02dd, 0x02e3, 0x02e7, 0x02ef, 0x02f5, 0x02f9, 0x0301,
    0x0305, 0x0313, 0x031d, 0x0329, 0x032b, 0x0335, 0x0337, 0x033b,
    0x033d, 0x0347, 0x0355, 0x0359, 0x035b, 0x035f, 0x036d, 0x0371,
    0x0373, 0x0377, 0x038b, 0x038f, 0x0397, 0x03a1, 0x03a9, 0x03ad,
    0x03b3, 0x03b9, 0x03c7, 0x03cb, 0x03d1, 0x03d7, 0x03df, 0x03e5,
    0x03f1, 0x03f5, 0x03fb, 0x03fd, 0x0000
};

/* 172 primes < 2^10 factor 83.87% of all odd integers. */

/******************************************************************************/

static inline unsigned int sp_factor (uint32_t p[], uint32_t n)
{
    uint32_t sp = sp_lut[0], q;
    unsigned int np = 1;

    /* assert(n > 1 && n < (UINT32_C(1) << (20))); */

    for (unsigned int i = 1; (q = n / sp) >= sp; )
    {
        if (q * sp == n)
            np++, n = q, *p++ = sp;

        else if ((sp = sp_lut[i++]) == 0) /* EOT entry: */
            break;
    }

    *p++ = n;

    return np; /* the number of prime factors (with multiplicity). */
}

/******************************************************************************/

static uint64_t gcdsum (uint32_t n_max)
{
    uint64_t sum = 0;

    /* assert(n < (UINT32_C(1) << (20))); */

    for (uint32_t n = 2; n <= n_max; n++)
    {
        uint32_t ptab[(20)], pn, gn = 2 * n - 1;

        if ((pn = sp_factor(ptab, n)) != 1) /* composite: */
        {
            uint32_t etab[(20)], un, p, i;

            etab[0] = 1, un = 1;

            for (p = ptab[0], i = 1; i < pn; i++)
            {
                uint32_t pi = ptab[i];

                if (pi == p)
                    etab[un - 1]++;
                else
                {
                    ptab[un] = (p = pi), etab[un] = 1;
                    un++;
                }
            }

            for (gn = 1, i = 0; i < un; i++)
            {
                uint32_t pi = ptab[i], ei = etab[i];

                gn *= ((ei + 1) * pi - ei);
                while (--ei) gn *= pi; /* pi ^ (ei - 1) */
            }
        }

        sum += gn - n; /* exclude (n, n) term from summation. */
    }

    return sum;
}

/******************************************************************************/

Calling private method from a Public method in the same class

ok here goes

why this->gcd doesnt work. YOu have

class Fraction {
    int gcd(int num1, int num2) {
        int absNum1 = abs(num1);
        int absNum2 = abs(num2);

        while (num2 != 0) {
            int remainder = absNum1 % absNum2;
            absNum1 = absNum2;
            absNum2 = remainder;
        }

        return absNum2;
    };

public:
     Fraction &operator*(const Fraction &fraction2) const {
        ....
    }

in operator* this is const - it says so on the end of the statement. So you cannot invoke a non-const method on it.

gcd is a non const method.

This can be fixed by

 int gcd(int num1, int num2) const {

It compiles now

But as other have pointed out this does not need to be a member function. What does it even mean to say frac.gcd(a,b), the method doesnt even look at frac.

You want

 static int gcd(int num1, int num2) {

now you can call it like this

int gcd = Fraction::gcd(multipliedFraction.numerator, multipliedFraction.denominator);

Note that I changed the calling signature of your operator* to be

 Fraction operator*(const Fraction &fraction2) const

this is what it should be as per

 https://gist.github.com/beached/38a4ae52fcadfab68cb6de05403fa393

Gcd with Static Functions of a Struct