GNU C tamsayi turleri

Project Euler, Topcoder gibi programlama ve algoritma problemleri üzerine kurulu sitelerdeki soruları çözerken bildiğiniz dilin size kazandırdığı hız ve işlev gerçekten çok önemli. Ben uzun süreler Python ile kolayca syntax'ı üzerine düşünmeden sadece kodun algoritmik kısmıyla uğraşıp hızlı hızlı soruları çözerek ilerliyordum. Ancak bu dönem C ile ilgilendiğimden dolayı bu problemlerde kaldığım yerden C ile devam ediyorum. Bu şekilde hem C konusunda teknik bilgim gelişirken hem de C'ye alışıp daha hızlı öğreniyorum. Bu hem bana okulda hem de ilerde yapacağım işler için büyük fayda sağlıyor diyebilirim.

C'de tamsayı(int), küçük tamsayı(short), büyük tamsayı(long), karakter(char) gibi tamsayı türleri vardır.Ve bunların işaretli(signed), işaretsiz(unsigned) durumları olabilir. Normal amaçlar için bu türler yeterli gelebilir. Ancak programlama konusunda yarışma düzeyinde sorular ile uğraşıyorsanız bu türlerin tutabileceği hane sayısından daha büyük sayılar ile uğraşabilirsiniz. İşte bunun için GNU C kütüphanesinde özel amaçlar için birçok farklı tür tanımlanmıştır. Bu türlere kaynak kodunuza stdint.h dosyasını include ederek ulaşıp kullanabilirsiniz.

Yaptığınız işte yeterli olacak bit sayısını biliyorsanız int8_t, int16_t, int32_t, int64_t ve bunların işaretsiz türlerini uint8_t, uint16_t, uint32_t, uint64_t kullabilirsiniz. Ancak burada dikkat edilmesi gereken nokta bilgisayarınızın özellikleri gereği bazı veri türleri olmayabilir(64-bit veya 32 bit makinelerde). Kütüphane dosyasına bakıp hangi türlerin tanımlı olduğuna bakabilirsiniz.

Aynı yukardaki veri türlerine benzer şekilde ama en azından ne kadar bitlik olacağını belirlemek isteyebilirsiniz. Bunun için int_least8_t, int_least16_t, int_least32_t, int_least64_t ve işaretsiz türleri uint_least8_t, uint_least16_t, uint_least32_t , uint_least64_t kullanabilirsiniz. Bu veri türlerini kullanırken tanımlama yaptıktan sonrasizeof ile boyutlarını kontrol ettirip yeniden tanımlama yapabilirsiniz.

C'nin diğer dillerden bana göre en büyük avantajlarından birisi de alt seviyeye yakın olmasının kazandırdığı hızdır. Eğer kodunuzun belirli kısmında hızlı erişime sahip tamsayı türleri kullanmak istiyorsanız int_fast8_t, int_fast16_t, int_fast32_t, int_fast64_t ve işaretsiz türleri uint_fast8_t, uint_fast16_t, uint_fast32_t, uint_fast64_t deneyebilirsiniz.

Bu türlerin yanında bilgisayarınızın destekleyeceği en büyük tam sayı genişliği için de intmax_t ve uintmax_t veri türlerini kullanabilirsiniz. Bu türleri kullanırken bilgisayarınızda tanımlı olan asgari ve azami değerleri öğrenmek için INT32_MAX, UINT8_MAX, INT_FAST32_MIN, INT_LEAST64_MIN, UINTMAX_MAX, INTMAX_MIN gibi makroları kullanabilirsiniz.

Bu veri türlerini kullanım şeklide diğerleri gibi. Sadece printf veya scanf kullanılcağı zaman bu değerler long integer olduğundan %ld kullanılması gerekiyor. Aşağıda verilen bir sayının tersini döndüren fonksiyon bu veri türlerinden uint64_t kullanılarak tanımlanmıştır.

uint64_t reverse(uint64_t n){
    uint64_t rev = 0;
    while (n > 0) {
        rev = (10*rev) + (n%10);
        n /= 10;
    }
    return rev;
}

Benzer şekilde verilen sayının en büyük asal böleni döndüren fonksiyon şu şekilde tanımlanabilir.

uint32_t largest_prime_fact(uint64_t num){
    if (num < 4)
        return num;

    uint32_t lfact, fact;
    if (num%2 == 0) {
        lfact = 2;
        num /= 2;
        while (num%2 == 0)
            num /= 2;
    }

    uint32_t maxfact = sqrt(num);
    for (fact = 3; num > 1 && fact < maxfact; fact += 2) {
        if (num%fact == 0) {
            num /= fact;
            lfact = fact;
            while (num%fact == 0)
                num /= fact;
            maxfact = sqrt(num);
        }
    }

    return num != 1 ? num : lfact;
}

Asal sayıları elekten geçirerek bulan fonksiyon da şu şekilde tanımlanabilirdi.

uint32_t e_sieve(uint32_t **primes, uint32_t limit){
    int32_t *pbits = calloc(limit/sizeof(int32_t) + 1,
            sizeof(int32_t));
    uint32_t prime = 2;
    uint32_t mult, idx, bidx;

    int psize = 1024;
    uint32_t *pfound = malloc(sizeof(uint32_t)*psize);
    uint32_t pcount = 1;
    pfound[0] = prime;
    while (prime*prime < limit) {
        mult = 0;
        for (int i = 2; mult < limit; ++i) {
            mult = i*prime;
            idx = mult/32;
            bidx = mult%32;
            pbits[idx] |= (1 << bidx);
        }
        for (int i = prime + 1; i < limit; ++i) {
            idx = i/32;
            bidx = i%32;
            if (!((pbits[idx] >> bidx) & 1)) {
                if (pcount == psize) {
                    psize *= 2;
                    pfound = realloc(pfound, sizeof(uint32_t)*psize);
                }
                prime = i;
                pfound[pcount++] = prime;
                break;
            }
        }
    }
    for (int i = prime + 1; i < limit; ++i) {
        idx = i/32;
        bidx = i%32;
        if (!((pbits[idx] >> bidx) & 1)) {
            if (pcount == psize) {
                psize *= 2;
                pfound = realloc(pfound, sizeof(uint32_t)*psize);
            }
            pfound[pcount++] = i;
        }
    }
    free(pbits);
    *primes = realloc(pfound, sizeof(uint32_t)*pcount);
    return pcount;
}

Bu veri türlerini kullanarak düşük işlem yaparken hız farkını hissedemeyebilirsiniz. Ancak ProjectEuler'in ilerleyen kısımlarındaki devasa boyutta işlemlerde gerçektende farkını koyuyor diyebilirim. Tabi sadece hız değil büyük haneli tamsayılar üzerinde de rahatça çalışma imkanı sağlıyor. Alışkanlık kazanmak insana çok şey katabilir.

comments powered by Disqus