الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

عملية الضرب

بدأه C++er في 15 سبتمبر 2011 · 2 رد · 1,068 مشاهدة · في الرياضيات والخوارزميات
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

توجد عدة وسائل لتنفيذ عملية الضرب مثل الجمع المتكرر (جمع الرقم الأول عدد مرات الرقم الثانى او العكس) او shift-add (و تسمي binary multiplication) او محور هذا السؤال Karatsuba algorithm، مثال Wikipedia يشرح مثل اغلب الأمثله كيف يمكن التطبيق على رقم و يتم تقسيمه لخانتين و لكن ماذا عن رقم تم تقسيم لأربع خانات او 16 خانه داخل base مختلف؟

سؤالي هو بإستخدام هذه الـ algorithm ما هى الخطوات المطلويه للحصول على حاصل ضرب الرقمين التاليين:

uint8 x[] = { 0x01, 0x23, 0x45, 0x67 };uint8 y[] = { 0x89, 0xab, 0xcd, 0xef };xy = ??
حاولت التطبيق كما هو موجود داخل موقع ويكيبديا و لكن التطبيقات باءت بالفشل، ارجو المساعده؟

و الله ولي التوفيق

تم تعديل هذه المشاركة بواسطة Xacker في 8 يناير 2013 في 03:50 — السبب: uint16 -> uint8

مدونتي: C++ Tips and Tricks

#3

مع انى لازلت متحير من قيمة الأساس و الأس ألا أنى توصلت للحل النظرى، يمكن ضرب الرقمين AB و 12 بهذا الشكل:

x= 0xAB, y=0x12

xy= 2*B + (1*A)<<8 + ((A+B)*(1+2)-2*B-1*A) << 4
xy= 16 + A00 + (3F-16-A) << 4
xy= A16 + 1F<<4
xy= A16 + 1F0
xy= C06

بالنسبه للمصفوفات بالاعلي سيتم الحصول على ناتج عملية الضرب عن طريق تقسيم محتواياتهم و من بعدها تنفيذ نفس الطريقه السابقه عليهم كالتالي:

uint8 x[] = { 0x01, 0x23, 0x45, 0x67 }; // 0x67452301
uint8 y[] = { 0x89, 0xab, 0xcd, 0xef }; // 0xefcdab89

// xy = 0x60BC833D692E6689

xL = { 0x01, 0x23 };
xH = { 0x45, 0x67 };

yL = { 0x89, 0xab };
yH = { 0xcd, 0xef };

xy = xL*yL + (xH*yH) << 32 + ( (xL+xH)(yL+yH) - xL*yL - xH*yH ) << 16

xL*yL = 0x17746689
xH*yH = 0x60BC1D41

xy = 17746689 + (60BC1D41)<<32 + (8A46*19B56-17746689-60BC1D41)<<16
xy = 17746689 + 60BC1D4100000000 + (DE2CD584-17746689-60BC1D41)<<16
xy = 60BC1D4117746689 + 65FC51BA<<16
xy = 60BC1D4117746689 + 65FC51BA0000
xy = 60BC1D4117746689 + 65FC51BA0000
xy = 60BC833D692E6689

كل مصفوفه تمثل 32بت و بالتالي عند ضربهم سيكون الناتج 64بت و بالمثل عند ضرب مصفوفتين 64بت سيكون الناتج 128بت و هكذا.

و الله ولي التوفيق

مدونتي: C++ Tips and Tricks

مواضيع مشابهة