C/C++ da ikkita 99 xonali katta sonlarni ko’paytirish.

Salom. Oxirgi kunlarda nimagadir matematikaga bo’lgan qiziqishlar yana ortmoqda. Bir paytlar o’zimga juda qiyin bo’lib ko’ringan misollarni shu kunlarda juda oson yechimlarini topmoqdaman. Bugungi ko’radigan misolimiz ikkita katta sonlarni ko’paytirish.

Bilamiz CPU orqali razryadidan kelib chiqib 2^32 yoki 2^64 li sonlarni ko’paytirib bera oladi. To’g’ri hayotda hisob kitobda 2^64 dan katta sonlar ishlatilmaydi. Lekin shunday joylari borki 100, 1000 xonali sonlarni bir biriga ko’paytirishga to’g’ri kelib qoladi.

Agar 2^22222 ni hisoblaydigan maqolamni o’qigan bo’lsangiz, ushbu maqolam ham oldingiga yozilganiga o’xshab ketadi. Faqat bu yerda 2 sonining o’rnida hohlagan son ishlatiladi.

Keling oldin ikkita sonni ko’paytirishni qadamma-qadam hisoblab bersam. Shunda bu safar ham dasturni tushinishingiz oson bo’ladi. Keling 2 ta 1234 va 5678 sonlarini ko’paytirib ko’raylik. Oddiy matematikada quyidagicha qilinadi
tabular{00100010}{00000000}{~ ~ ~ 1 2 3 4 ~ ~ ~ 5 6 7 8 ~ ~ ~ 8 16 24 32 ~ ~ 7 14 21 28 ~ ~ 6 12 18 24 ~ ~ 5 10 15 20 ~ ~ ~ 5 16 34 60 61 52 32}
bundan chiqqan

5 16 34 60 61 52 32

sonlarini o’ngdan chapga qarab 10 likdagi birliklarini surib qo’shib chiqsak natijaga erishamiz. Ya’ni

2 + 10 * 3 = 32 bunda 3 
5 + 10 * 5 = 52 + 3 bunda 5
6 + 10 * 6 = 62 + 5 bundan 6
6 + 10 * 6 = 60 + 6 bundan 6
0 + 10 * 4 = 34 + 6 bundan 4
0 + 10 * 2 = 16 + 4 bundan 2
7 + 10 * 0 = 5 + 2

demak natija 7006652 bo’larkan. Man ham shu usuldan foydalandim faqat man birinchi qadamda 32 hisoblanganida result[0] da 2 ni qoldirib, result[1] += 3 qilib qo’shib qo’ydim.

Endi shuni mani dasturim yordamida qanday qilinganini ko’ramiz. Misolda o’zgaruvchilar qiymatlari

len1 = 4
len2 = 4;
num1={1, 2, 3, 4};
num2={5, 6, 7, 8};

shunaqa bo’ladi. Bizga sonlarning oxirgi raqamidan boshlashimiz uchun indekslarni oxirgisidan 0 gacha o’qish kerka bo’ladi ya’ni

for(int j = len2 - 1; j >= 0; j--)

shunda num2 dagi o’ng tarafdan boshlab qiymat olishni boshlaymiz. Shunda bizda n2 da 8 dan 5 gacha bo’lgan sonlar, n1 da esa 4 dan 1 gacha bo’lgan sonlar bo’ladi.

Yana bir qismi

int index = len2 - j - 1

Agar metematik usulini ko’rgan bo’lsangiz, har boshqa sonni ko’paytirguncha bitta-bitta surish kerak, shu surishni hosil qilish uchun shunday yozilgan. Ya’ni j = 3 bo’lsa, index = 0, j = 2 bo’lsa index = 1.

Manimcha qolganini o’zingiz tushinib olasiz. Aslida bu juda oson.

#include 
#include 
#include 
#include 

unsigned char len1 = 0, len2 = 0, lenr = 0;
unsigned char num1[99], num2[99], result[9999];

void read_number(unsigned char * num, unsigned char *len)
{
	char c;
	while( 1 )
	{
		scanf("%c", &c);
		if (c == 'r' || c == 'n') 
			break;
		
		num[(*len)++] = c - '0';
	}
}

void kup()
{
	for(int j = len2 - 1; j >= 0; j--)
	{
		unsigned char n2 = num2[j];
		int index = len2 - j - 1;

		for(int i = len1 - 1; i >= 0; i--)
		{
			unsigned char n1 = num1[i];

			result[index] += n1 * n2;
			if (result[index] >= 10)
			{
				result[index + 1] += (int)floor(result[index] / 10.0);
				result[index] = result[index] % 10;
			}

			index++;

			if (index > lenr)
				lenr = index;
		}
	}
}

int main()
{
	memset(result, 0, 9999);

	read_number(num1, &len1);
	read_number(num2, &len2);

	kup();

	for(int i = lenr - 1; i >= 0; i--)
	{
		printf("%d", result[i]);
	}

	return 0;
}

Savollar bo’lsa marhamt.