متغیر استقرایی

متغیر استقرایی (در شاخه علوم رایانه) به متغیری گفته می‌شود که در هر گام از اجرای یک حلقه به میزان ثابتی افزایش یا کاهش می‌یابد و یا مقدار آن تابعی خطی از یک متغیر استقرایی دیگر در حلقه است.

به عنوان مثال، در کد زیر متغیرهای i و j متغیرهای استقرایی هستند؛ زیرا در هر گام از حلقه مقدار i یک واحد افزایش می‌یابد و j نیز با i رابطه خطی دارد:

for (i = 0; i <10; ++i) {
    j = 17 * i;
}

کاربرد در روش کاهش قدرت

یکی از روش‌های رایج در بهینه‌سازی‌های کامپایلر -کامپایلر بهینه‌ساز- کشف وجود متغیرهای استقرایی و جایگزینی دستورات مربوط به آن‌ها با دستورات حاوی محاسبات ساده‌تر است؛ برای مثال، با فرض این که عملیات مربوط به جمع یک متغیر با یک مقدار ثابت از عملیات ضرب آن در یک مقدار ثابت، ساده‌تر و سبک‌تر است، کد قسمت قبل را می‌توان به صورت زیر تغییر داد:

j = -17;
for (i = 0; i <10; ++i) {
    j = j + 17; //جایگزینی ضرب‌های مکرر روی متغیر استقرایی با عمل ساده‌تر جمع
}

که در اینجا بجای ضرب j در متغیر گام حلقه (که همان متغیر استقرایی است)، هربار j با مقدار ثابت 17 جمع می‌شود.

این راهکار بهینه‎سازی مثالی خاص از روش کاهش قدرت است.

کاربرد در روش کاهش فشار ثبات

گاهی اوقات، می‌توان این بهینه‌سازی را به صورت معکوس اعمال کرد و با این کار یک متغیر استقرایی را کاملاً از کدهای برنامه حذف کرد. برای مثال کد زیر را در نظر بگیرید:

extern int sum;
int foo(int n) {
    int i, j;
    j = 5;
    for (i = 0; i <n; ++i) {
        j += 2; //این متغیر استقرایی قابل حذف شدن از کد است
        
        sum += j;
    }
    return sum;
}

در حلقه این تابع، دو متغیر استقرایی وجود دارند: i و j. هر یک از این دو را می‌توان بر حسب تابعی خطی از دیگری بازنویسی کرد؛ بنابراین کامپایلر می‌تواند این کد را به صورت زیر بهینه‌تر کند:

extern int sum;
int foo(int n) {
    int i;
    for (i = 0; i <n; ++i) {
        sum += 5 + 2 * (i + 1);
    }
    return sum;
}

در بهینه سازی بالا در واقع، تعریف متغیر j و محاسبات اعمال شده روی آن حذف شده‌اند و کاربرد j در حلقه به صورت تابعی خطی از متغیر استقرایی دیگر حلقه، i، بازنویسی شده است.

در واقع، از این ایده استفاده می‌شود که با جایگزین کردن یک متغیر استقرایی با تابعی خطی از متغیر استقرایی موجود دیگری، که عملیات آن تابع خطی سبک باشد، می‎توان از در نظر گرفته شدن ثبات مجزایی از cpu برای این متغیر جلوگیری کرد. این روش، مثالی از بهینه‌سازی در زمینه تخصیص ثبات است.

جایگزینی متغیر استقرایی

متغیری که درون یک حلقه به‌روزرسانی می‌شود، در واقع در هر گام از حلقه مقداری را به خود می‌گیرد که وابسته به مقدار متغیر حلقه در آن گام است. به عنوان مثال، متغیری را در نظر بگیرید که در ابتدا ۲- بوده و در هر گام از حلقه ۲ واحد زیاد می‌شود. این متغیر در واقع در هر گام از حلقه، دو برابر مقدار متغیر حلقه است.

می‌توان به جای به‌روزرسانی چنین متغیری در هر گام از حلقه، در هر گام آن را مستقیماً بر حسب متغیر حلقه نوشت. به این کار جایگزینی متغیر استقرایی می‌گویند.

این جایگزینی رابطه‌ی بین متغیر درون حلقه و متغیر حلقه را تصریح می‌کند. این کار به برخی از آنالیزهایی که کامپایلرها انجام می‌دهند کمک می‌کند. به عنوان مثال تحلیل واسبتگی یکی از این آنالیزهاست که با استفاده از جایگزینی متغیر استقرایی ساده‌تر می‌شود.

مثال

قطعه کد زیر را در نظر بگیرید.

int c, i;
c = 10;
for (i = 0; i <10; i++) {
    c = c + 5; // متغیر استقرایی در هر حلقه، ۵ واحد افزایش می‌یابد
}

در این قطعه کد، متغیر c یک متغیر استقرایی است و در حلقه به‌روزرسانی می‌شود. ولی می‌توانیم به جای این که در هر حلقه ۵ واحد به آن اضافه کنیم، ارتباطی مستقیم بین c و متغیر حلقه یعنی i پیدا کنیم.

برای یافتن این ارتباط، دقت می‌کنیم که رابطه‌ی این دو در واقع رابطه‌ای خطی با شیب ۵ است. با توجه به مقدار اولیه‌ی c یعنی ۱۰، می‌توانیم به سادگی مقدار عرض از مبدأ این رابطه‌ی خطی را نیز بیابیم که در واقع ۱۵ است.

لذا می‌توانیم قطعه کد را به صورت زیر تغییر دهیم.

int c, i;
c = 10;
for (i = 0; i <10; i++) {
    c = 5 * i + 15;  // مقدار متغیر استقرایی، مستقیماً از روی مقدار متغیر حلقه محاسبه می‌شود
}

کاری که کردیم در واقع نمونه‌ای از جایگزینی متغیر استقرایی بود.

متغیرهای استقرایی غیرخطی

در تمام مثال‌هایی که در بخش‌های قبل دیدیم، رابطه‌ای خطی بین متغیر استقرایی و متغیر حلقه وجود داشت. اما چنین رابطه‌ی خطی‌ای همیشه وجود ندارد.

گاهی ممکن است رابطه‌ی بین این دو چندجمله‌ای، نمایی یا ... باشد. در بسیاری از این موارد نیز می‌توان بهینه‌سازی‌هایی را انجام داد.

مثال ۱

قطعه کد زیر را در نظر بگیرید.

int c, i;
c = 0;
for (i = 0; i <10; i++) {
    c = c + i;  // مقدار متغیر استقرایی، هر بار به اندازه‌ی متغیر حلقه اضافه می‌شود 
}

در این مثال، مقدار متغیر استقرایی هر در گام از حلقه، به اندازه‌ی مقدار متغیر حلقه افزایش می‌یابد.

هیچ‌گونه رابطه‌ی خطی‌ای بین c و i وجود ندارد اما با کمی دقت درمی‌یابیم که در هر گام از حلقه، مقدار c در واقع جمع اعداد ۰ تا i است. پس به نظر می‌رسد که می‌توان جایگزینی متغیر استقرایی را با استفاده از یک رابطه‌ی چندجمله‌ای انجام داد.

قطعه کد تغییر یافته به صورت زیر خواهد بود:

int c, i;
c = 0;
for (i = 0; i <10; i++) {
    c = i * (i + 1) / 2;  // مقدار متغیر استقرایی، مستقیماً از روی مقدار متغیر حلقه محاسبه می‌شود 
}

مثال ۲

قطعه کد زیر را در نظر بگیرید.

int j, i;
j = 1;
for (i = 0; i <10; i++) {
    j = j <<1;  // متغیر استقرایی در هر گام از حلقه یک بار شیفت چپ می‌خورد
}

در این مثال، مقدار متغیر استقرایی در هر گام از حلقه، یک شیفت به چپ می‌خورد.

باز هم رابطه‌ی خطی‌ای بین j و i مشاهده نمی‌شود اما به سادگی می‌توان دریافت که در هر گام از حلقه، مقدار j در واقع برابر با i + 1 بار شیفت به چپ خورده‌ی عدد ۱ است.

بنابراین این بار هم می‌توان مقدار جایگزینی متغیر استقرایی j را به صورت زیر انجام داد.

int j, i;
j = 1;
for (i = 0; i <10; i++) {
    j = 1 <<(i + 1);  // مقدار متغیر استقرایی، مستقیماً از روی متغیر حلقه محاسبه می‌شود
}