متغير الاستقراء

في علم الحاسوب ، المتغير الاستقرائي هو متغير يتم زيادته أو إنقاصه بمقدار ثابت في كل تكرار لحلقة تكرارية، أو هو دالة خطية لمتغير استقرائي آخر. ^{[ 1 ]}

على سبيل المثال، في الحلقة التالية، iو jهي متغيرات استقراء:

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

تتمثل إحدى عمليات تحسين المترجم الشائعة في التعرف على وجود متغيرات الاستقراء واستبدالها بحسابات أبسط؛ على سبيل المثال، يمكن إعادة كتابة الكود أعلاه بواسطة المترجم على النحو التالي، على افتراض أن إضافة ثابت ستكون أرخص من عملية الضرب.

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

يُعد هذا التحسين حالة خاصة من تقليل القوة .

في بعض الحالات، من الممكن عكس هذا التحسين لإزالة متغير الاستقراء من الكود بالكامل. على سبيل المثال:

extern int sum ;int foo ( int n ) { int j = 5 ;for ( int i = 0 ; i < n ; ++ i ) { j += 2 ; sum += j ; }أعد المجموع ؛ }

تحتوي حلقة هذه الدالة على متغيرين استقرائيين: iو j. يمكن إعادة كتابة أي منهما كدالة خطية للآخر؛ لذلك، قد يُحسّن المُصرّف هذا الكود كما لو كان قد كُتب

extern int sum ;دالة foo ( عدد صحيح n ) { من أجل ( عدد صحيح i = 0 ؛ i < n ؛ ++ i ) { المجموع += 5 + 2 * ( i + 1 )؛ }أعد المجموع ؛ }

استبدال المتغيرات بالاستقراء هو تحويل للمترجم للتعرف على المتغيرات التي يمكن التعبير عنها كدوال لمؤشرات الحلقات المحيطة واستبدالها بتعبيرات تتضمن مؤشرات الحلقات.

هذا التحويل يجعل العلاقة بين المتغيرات ومؤشرات الحلقة واضحة، مما يساعد في تحليل المترجمات الأخرى، مثل تحليل التبعية .

مثال:

رمز الإدخال:

int c = 10 ;for ( int i = 0 ; i < 10 ; i ++ ) { c = c + 5 ; // يتم زيادة قيمة c بمقدار 5 في كل تكرار للحلقة }

رمز الإخراج

int c = 10 ;for ( int i = 0 ; i < 10 ; i ++ ) { c = 10 + 5 * ( i + 1 ); // يتم التعبير عن c بشكل صريح كدالة لمؤشر الحلقة }

يمكن تطبيق نفس التحسينات على متغيرات الاستقراء التي لا تكون بالضرورة دوالًا خطية لعداد الحلقة؛ على سبيل المثال، الحلقة

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

يمكن تحويلها إلى

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

• الاستقراء الرياضي

• أهو، ألفريد ف.؛ سيثي، رافي؛ أولمان، جيفري د. (1986)، المترجمات: المبادئ والتقنيات والأدوات (الطبعة الثانية  )، ISBN 978-0-201-10088-4
• ألين، فرانسيس إي.؛ كوك، جون ؛ كينيدي، كين (1981)، "تقليل قوة المشغل"، في مونشنيك، ستيفن إس.؛ جونز، نيل دي. (محرران)، تحليل تدفق البرنامج: النظرية والتطبيقات ، برنتيس هول، ISBN 978-0-13-729681-1
• كوك، جون ؛ كينيدي، كين (نوفمبر 1977)، "خوارزمية لتقليل قوة المشغل"، اتصالات رابطة آلات الحوسبة ، 20 (11): 850-856 ، doi : 10.1145/359863.359888 ، S2CID 1092505 
• كوبر، كيث؛ سيمبسون، تايلور؛ فيك، كريستوفر (1995)، تقليل قوة المشغل (ملف PDF) ، جامعة رايس ، تم الاطلاع عليه في 22 أبريل 2010