دو نیم کردن (الگوریتم کامپیوتری)

در ریاضیات ، تقسیم بر دو یا دو نیم کردن، میانجی گری یا کاهش نیز نامیده می‌شود. ^[۱] سابقه برخورد با آن به عنوان یک عملیات مجزا از ضرب و تقسیم معمولی بر سایر اعداد به مصر باستان برمی‌گردد که الگوریتم ضرب آنها از تقسیم بر دو به عنوان یکی از مراحل اصلی استفاده می کرد.^[۲] برخی ریاضیدانان تا اواخر قرن شانزدهم همچنان نیم‌کردن را به عنوان یک عملیات ریاضی جداگانه به حساب می‌آوردند، ^[۳]^[۴] همچنین در برنامه‌نویسی کامپیوتری مدرن نیز اغلب به صورت جدا مورد تحلیل و بررسی قرار می گیرد.^[۵] انجام این عملیات در محاسبات ده‌دهی، سیستم اعداد دودویی که در برنامه‌نویسی کامپیوتری کاربرد دارد و نیز در سایر سیستم‌های اعداد با مبنای زوج آسان است.

دودویی

در محاسبات دودویی، تقسیم بر دو را می توان با یک عملیات شیفت بیتی انجام داد که مکان شماره را یک واحد به سمت راست منتقل می کند. این عمل شکلی از بهینه سازی کاهش قدرت است. به عنوان مثال، 1101001 به صورت دودویی (عدد مبنای ده: 105)، پس از یک واحد انتقال به سمت راست، برابر با 110100 می‌شود (عدد مبنای ده: 52)؛ توجه شود که کم‌ارزش‌ترین بیت، یعنی 1، حذف می‌شود. به‌طور مشابه، تقسیم بر هر توان دو 2^k را می توان با جابجایی (شیفت) به تعداد k واحد به سمت راست انجام داد. از آنجا که تغییر بیت اغلب عملیاتی بسیار سریعتر از عملیات تقسیم است، جایگزینی یک تقسیم با یک شیفت به این روش می تواند گام مفیدی در بهینه سازی برنامه باشد.^[۵] با این حال، به خاطر قابل حمل بودن نرم‌افزار و خوانایی آن، در بیشتر موارد بهتر است برنامه ها با استفاده از عملیات تقسیم نوشته شود و اعتماد به کامپایلر برای انجام این جایگزینی صورت گیرد.^[۶] مثالی از لیسپ:

 (setq number #b1101001)   ; #b1101001  —  105
 (ash number -1)           ; #b0110100  —  105 >> 1 ⇒ 52
 (ash number -4)           ; #b0000110  —  105 >> 4 ≡ 105 / 2⁴ ⇒ 6

با این حال، دستورها بالا لزوما در مورد تقسیم اعداد دودویی علامت‌دار درست نیستند. در شیفت دادن یک واحدی به سمت راست که باعث تقسیم بر دو می شود، عدد همواره به سمت پایین گرد می‌شود. با این حال، در برخی از زبان‌های برنامه‌نویسی، تقسیم اعداد دودویی علامت‌دار به سمت 0 گرد می شود (که اگر حاصل عملیات منفی باشد، به این معنی است که به سمت بالا گرد شده است). به عنوان مثال، جاوا یکی از این زبان‌ها است: در جاوا، $-3/2$ معادل با $-1$ ارزیابی می‌شود، در حالی که $-3>>1$ معادل $-2$ می‌شود. بنابراین زمانی که مقسوم منفی باشد، احتمالاً کامپایلر نمی‌تواند با جایگزین کردن تقسیم بر دو با شیفت بیتی آن را بهینه کند.^[۷]

ممیز شناور دودویی

در محاسبات ممیز شناور دودویی، تقسیم بر دو را می توان با یک واحد کاهش توان انجام داد (تا زمانی که نتیجه یک عدد غیرعادی نباشد). بسیاری از زبان های برنامه نویسی دارای توابعی هستند که می توان از آنها برای تقسیم یک عدد ممیز شناور بر توانی از دو استفاده کرد. برای مثال زبان برنامه‌نویسی جاوا مِتُد java.lang.Math.scalb را برای مقیاس‌بندی با توان دو ارائه می‌کند،^[۸] و در زبان برنامه نویسی C تابع ldexp به همین منظور وجود دارد.^[۹]

ده‌دهی

الگوریتم زیر برای اعداد ده‌دهی می‌باشد. اما می توان آن را به عنوان یک مدل برای ساخت الگوریتمی برای به دست آوردن نیمی از هر عدد N در هر مبنای زوجی به کار برد.^[۷]

N را نوشته و یک صفر در سمت چپ آن قرار دهید.
ارقام N را به صورت زوج‌های متداخل در نظر بگیرید، سپس ارقام حاصل را از جدول زیر یادداشت کنید.

اگر رقم اول ... باشد	زوج	زوج	زوج	زوج	زوج	فرد	فرد	فرد	فرد	فرد
و رقم دوم ...	0 یا 1	2 یا 3	4 یا 5	6 یا 7	8 یا 9	0 یا 1	2 یا 3	4 یا 5	6 یا 7	8 یا 9
آنگاه بنویس	0	1	2	3	4	5	6	7	8	9

مثال: $1738/2=?$

01738 را می‌نویسیم و برای پیدا کردن پاسخ به صورت زیر عمل می‌کنیم.

01: رقم اول زوج و رقم دوم 1، 0 می‌نویسیم.
17: رقم اول فرد و رقم دوم 7، 8 می‌نویسیم.
73: رقم اول فرد و رقم دوم 3، 6 می‌نویسیم.
38: رقم اول فرد و رقم دوم 8، 9 می‌نویسیم.

حاصل: 0869.

از مثال می‌توان فهمید که 0 زوج است.

اگر رقم آخر عدد N فرد باشد باید 0.5 به حاصل اضافه کنیم.

همچنین ببینید

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

منابع

↑ Steele, Robert (1922), The Earliest arithmetics in English, Early English Text Society, 118, Oxford University Press, p. 82.
↑ Chabert, Jean-Luc; Barbin, Évelyne (1999), A history of algorithms: from the pebble to the microchip, Springer-Verlag, p. 16, ISBN 978-3-540-63369-3.
↑ Jackson, Lambert Lincoln (1906), The educational significance of sixteenth century arithmetic from the point of view of the present time, Contributions to education, 8, Columbia University, p. 76.
↑ Waters, E. G. R. (1929), "A Fifteenth Century French Algorism from Liége", Isis, 12 (2): 194–236, doi:10.1086/346408, JSTOR 224785.
↑ ^۵٫۰ ^۵٫۱ Wadleigh, Kevin R.; Crawford, Isom L. (2000), Software optimization for high-performance computing, Prentice Hall, p. 92, ISBN 978-0-13-017008-8.
↑ Hook, Brian (2005), Write portable code: an introduction to developing software for multiple platforms, No Starch Press, p. 133, ISBN 978-1-59327-056-8.
↑ ^۷٫۰ ^۷٫۱ "Division by two". Wikipedia (به انگلیسی). 2021-10-16.
↑ "Math.scalb". Java Platform Standard Ed. 6. Retrieved 2009-10-11.
↑ Programming languages — C, International Standard ISO/IEC 9899:1999, Section 7.12.6.6.

[1] Steele, Robert (1922), The Earliest arithmetics in English, Early English Text Society, 118, Oxford University Press, p. 82.

[2] Chabert, Jean-Luc; Barbin, Évelyne (1999), A history of algorithms: from the pebble to the microchip, Springer-Verlag, p. 16, ISBN 978-3-540-63369-3.

[3] Jackson, Lambert Lincoln (1906), The educational significance of sixteenth century arithmetic from the point of view of the present time, Contributions to education, 8, Columbia University, p. 76.

[4] Waters, E. G. R. (1929), "A Fifteenth Century French Algorism from Liége", Isis, 12 (2): 194–236, doi:10.1086/346408, JSTOR 224785.

[WC00-5] ۵٫۰ ^۵٫۱ Wadleigh, Kevin R.; Crawford, Isom L. (2000), Software optimization for high-performance computing, Prentice Hall, p. 92, ISBN 978-0-13-017008-8.

[6] Hook, Brian (2005), Write portable code: an introduction to developing software for multiple platforms, No Starch Press, p. 133, ISBN 978-1-59327-056-8.

[:0-7] ۷٫۰ ^۷٫۱ "Division by two". Wikipedia (به انگلیسی). 2021-10-16.

[8] "Math.scalb". Java Platform Standard Ed. 6. Retrieved 2009-10-11.

[9] Programming languages — C, International Standard ISO/IEC 9899:1999, Section 7.12.6.6.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]