Sonning ixtiyoriy butun darajasini hisoblash

Sonning ixtiyoriy butun darajasini topish informatikaning boshlang'ich kurslarida o'rganilgan sodda muommolardan biri.

Yechimi ham oddiy:

int pow = 1;
for(int i =0; i < m; i++)
{
    pow*=n;
}

Anglaganingizdek, yuqoridagi kod n^m ni hisoblaydi. Kod n ni m marta ko'paytirib chiqishga asoslangan. Bundan tezroq usul bormi? Ha bor ekan. Daraja bu sonni bir necha marta ko'paytirishdan iborat amal bo'lsa qanday qilib bundan tez bo'lishi mumkin. Keling, 7^13 ni hisoblab ko'raylik. Demak,

7^13 = 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 = ((7^2 * 7)^2)^2*7

ko'rinishida ifodalab olishimiz mumkin. Bu usul kvadratlarga keltirib darajani hisoblash usuli hisoblanadi. Bu usulning rekursiv ifodasi:

Formulani kodga aylantiramiz va quyidagi natijani olamiz.

/// <summary> 
/// Sonning ixtiyoriy darajasini hisoblash
/// </summary> 
/// <param name="x"> son</param> 
/// <param name="n"> daraja</param> 
/// <returns> x ning n darajasini qaytaradi</returns> 
public static double Pow(double x, int n)
{
    // agar n < 0 bo'lsa
    if (n < 0)
        return Pow(1 / x, -1 * n);
    //agar n = 0 bo'lsa
    if (n == 0)
        return 1;
    // n ga birga teng bo'lgan holat
    if (n == 1)
        return x;
    //dataga juft bo'lsa
    if ((n & 1) == 0)
        return Pow(x * x, n / 2);
    //toq bo'lsa
    return x * Pow(x * x, (n - 1) / 2);
}
private static void Main(string[] args)
{
     Console.WriteLine(Pow(3, -6));
}
//Natija: 0.00137174211248285

Bu usulning qulayligi shundaki n'ning taxminan 4 dan katta bo'lgan qiymatlarida, oddiy ko'paytirib borish usulidan tezroq ishlaydi. Ushbu usuldan keyinchalik qiyinroq muommolarning yechimi uchun foydalanamiz. Boshqacha qilib aytganda, sonning har qanday butun darajasini hisoblashni 7 marta ko'paytirish amali bilan bajarish mumkin.