بخشی از مقاله
سيستم اعداد ماندهاي (باقيمانده)
سيستم اعداد ماندهاي يك سيستم اعداد صحيح است، كه مهمترين ويژگياش بطور ذاتي انتقال رقم نقلي مجازي در جمع و ضرب و تفريقهاست، همچنين نتجه جمع و تفريق و ضرب اعداد ما در مرحله اول بدون در نظر گرفتن طول اعداد مشخص ميشود، متأسفانه در سيستم اعداد ماندهاي عمليات رياضي ديگري مانند تقسيم و مقايسه و شناسايي علامت خيلي پيچيده و كند هستند از مشكلات ديگر سيستم اعداد ماندهاي اين است كه چون با سيستم اعداد صحيح كار ميكند در نتيجه نمايش اعداد اعشاري در سيستم اعداد ماندهاي خيلي ناجور است با توجه به خواص
سيستم اعداد ماندهاي نتيجه ميگيريم كه در اهداف عمومي كامپيوترها (ماشين حسابها) به صورت كاملاً جدي نميتواند مطرح بشود. بهرحال ، براي بعضي از كاربرها كه اهداف خاصي دارند مثل بسياري از انواع فيلترهاي ديجيتال، تعداد جمع و ضربهايي كه اساساً بزرگتر تعداد و درخواست بزرگي دامنه و شناسايي سرريز، تقسيم و شبيه اينها، سيستم اعداد باقيمانده خيلي جذاب و جالب ميتواند باشد.
1-1) مقدمه
سيستم اعدادماندهاي اساساً بوسيله يك مبناي چندتائي (N - تائي) و نه يك مبناي واحد مثل از اعداد صحيح مشخص ميشود. هر كدام از ها باقيمانده پس از تقسيم يك عدد بر آنها است.عدد صيح X در سيستم اعداد ماندهاي بوسيلة يك N -تائي مثل نمايش داده ميشود كه هر يك عدد غيرمنفي صحيح است كه در رابطة زير صادق است:
X
0
1
0
1
0
1
0
1
0
1
0
1
0 2
0
1
2
0
1
2
0
1
2
0
1
2 -4
-3
-2
-1
0
1
2
3
4
5
6
7
8
جدول 1-1 نمايش اعداد در سيستم اعداد ماندهاي به پيمانة
بزرگترين عدد صحيحي است بطوريكه معروف است به باقيمانده X به پيمانة Mi ، و در روش نوشتن اعداد هر دو و با يك مفهوم استفاده ميشوند.
مثال 1-1 سيستم اعدادماندهاي 2- باقيماندهاي با پيمانههاي را ملاحظه كنيد در اين سيستم نمايش عدد صحيح x=5 به صورت نمايش داده ميشود كه و از رابطههاي زير بدست ميآيند.
چونكه
چونكه
بنابراين در اين سيستم اعداد ماندهاي با پيمانههاي و عدد صحيح 5 به صورت (2,1) نشان داده ميشود.
عدد X لزوماً نبايد يك عدد صحيح مثبت باشد بلكه ميتواند عدد صيح منفي هم باشد براي مثال اگر X=-2 باشد آنگاه
چونكه
چونكه
نكتهاي كه در اينجا وجود دارد اين است كه ها مثبت تعريف مي شوند .
بنابراين عدد صيح -2 در سيستم اعداد ماندهاي با پيمانههاي و بصورت نمايش داده ميشود.
جدول 1-1 اعداد صحيح در محدودة [-4,8] را در سيستم اعداد ماندهاي به پيمانة نمايش داده است.
همانطور كه از جدول 1-1 مشخص است نمايش ماندهاي يك عدد صحيح منحصر بفرد است در حالي كه بر عكس اين مطلب درست نيست و نمايش صحيح دو يا چند عددماندهاي ممكن است
يكسان باشد براي مثال نمايش صحيح (1،1) هم عد يك ميشود و هم عدد هفت، پس در نتيجه ما بايد دامنة اعدادي را كه نمايش داده مي شوند محدود كنيم، همنطور كه از جدول 1-1 مشخص ميشود نمايش ماندهاي دورهاي است و تكرار ميشود و در اينجا محدودة تكرارش شش است، ما در سيستم اعداد ماندهاي به پيمانة فقط شش نمايش مختلف داديم چونكه دو مقدار مختلف سه مدقار مختلف ميتوانند به خود بگيرند، بنابراين ما بايد ناحية نمايش را به شش عدد محدود بكنيم، دو ناحيةممكن در جدول مشخص شدهاند، اولي و دومي است.
در حالت كلي در سيستم اعدادماندهاي ميتوان گفت كه تعداد نمايشهاي غيرتكراري برابر است با كوچكترين مضرب مشترك پيمانهها، كه به صورت زير نمايش داده ميشود.
و از همين عنصر براي محدود كردن ناحية نمايش استفاده ميكنيم.
كوچترين مضرب مشترك پيمانهها كوچكترين عدد است كه همة پيمانهها بر آن تقسيم مي شوند . براي مثال كوچكترين مضرف مشترك اعداد 2 و 3 عدد 6 ميشود. ولي كوچكترين مضرب مشترك اعداد 2 و 4 عدد 4 ميشود . بزرگترين ناحية ممكن عبارت است از حاصلظرب همة پيمانهها در همديگر
و براي بدست آوردن بزرگترين ناحية ممكن ما بايد پيمانهها را دو به دو نسبت به هم اول انتخاب كنيم، دو پيمانة و را نسبت به هم اول گوييم اگر كه بزرگترين مقسوم عليه مشترك آنها يك باشد. و معمولاً به اين شكل مينويسيم
براي مثال اعداد 4 و 9 نسبت به هم اول و هستند اگر چه خودشان هيچكدام عدد اول نيستند و اعداد 4 و 24 نسبت به هم اول نيستند چونگه بزرگترين مقسوم عليه مشترك آنها عدد 4 ميباشد اگر دو عدد خودشان اول باشند قطعاً نسبت به هم نيز اول هستند مثلاً اعداد 2 و 3 و يا 5 و 7 و …….
حال ما عدد M را بدست آوردهايم، حال ما مي توانيم يك ناحية M تائي از اعداد صحيح را به عنوان محدودة نمايش سيستم اعداد ماندهاي مربوطه در نظر گرفت، اگر كه اعداد صحيح مثبت احتياج داشته باشيم ميتوان ناحيه [O,M-1] را در نظر گرفت و اگر درجائي ديگر اعداد منفي هم مطلوب بودند ميتوانيم ناحيه را به اين صورت تعريف كنيم كه اگر M زوج باشد و اگر M فرد باشد. .
اگر به جدول 1-1 نگاه كنيم و ناحيه [0,5] را بررسي كنيم متوجه ميشويم كه هيچ دو عددي از آن شبيه هم نيستند.