Big-Integer Tutorial with C


বড় বড় নাম্বার যোগ, গুন করার সময় আমরা প্রায়ই চিন্তায় পড়ে যাই। যেমন আমরা যদি C Data type range দেখি,

int (signed) –2,147,483,648 to 2,147,483,647
unsigned int 0 to 4,294,967,295
long long (signed) –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
unsigned long long 0 to 18,446,744,073,709,551,615

অর্থ্যাৎ সবচেয়ে বেশি গেলেও ২০ ডিজিটের চেয়ে বড় নাম্বার রাখা না। কিন্তু আমাদের আরও বড় সংখ্যা নিয়ে কাজ করার প্রয়োজন হতে পারে। যেমন ধরা যাক, 100! বা 2^1000 যদি বের করতে চাই।

এই কাজগুলা করতে চাইলে আমাদের ছোটবেলার বাংলা পদ্ধতির সাহায্য নিতে হবে। প্রথমে আমি আলোচনা করব বড় বড় যোগ কিভাবে বের করতে হয়, তারপর আসব গুন কিভাবে করতে হয়।

মনে করি, আমাদের দুইটা সংখ্যা দেয়া আছে, 87654 and 74692
এই দুইটা সংখ্যা যোগ করতে হবে।


8
7
6
5
4

7
4
6
9
2

প্রথমে আমরা দুইটা সংখ্যা নিচে নিচে লিখে ফেললাম, এবার আমরা যোগ শুরু করব।


8
7
6
5
4

7
4
6
9
2





6

৪ যোগ ২ সমান ৬


8
7
6
5
4

7
4
6
9
2




4
6

৫ যোগ ৯ সমান ১৪
১৪-এর ৪ বসালাম, হাতে থাকল ১


8
7
6
5
4

7
4
6
9
2



3
4
6

৬ যোগ ৬ সমান ১২
হাতের ১ যোগ করে পেলাম ১৩
৩ বসালাম, হাতে থাকল ১

….
বুঝাই যাচ্ছে আমি কি করতে যাচ্ছি। সবশেষে পুরো বিষয়টা দাড়াবে এরকম

8

7

6

5

4

7

4

6

9

2

1

6

2

3

4

6

এই কাজটাই এখন আমরা প্রোগ্রাম দিয়ে করব। মানে কম্পিউটারকে দিয়ে করাব।

প্রথমে সংখ্যাগুলাকে ডিজিটে ভাগ করে Array-তে নিব।


#include <cstdio>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    return 0;
}

একটা ছোট সমস্যা। আমরা তো যোগ করা শুরু করি ডানদিক থেকে। কিন্তু আমাদের অ্যারে শুরু হয় বামদিক থেকে।
মানে হল, আমাদের প্রথমে যোগ করতে হবে ৪ এবং ২; কিন্তু এগুলা অ্যারেতে শেষ এলিমেন্ট। কি করা যেতে পারে?

আমরা Array উল্টাদিক থেকে পড়া শুরু করতে পারি অথবা অ্যারেটাকেই উল্টে নিতে পারি।
আমরা বরং অ্যারেটাকে উল্টে নিই। তাতে করে আমাদের অ্যারে দেখাবে এরকম।

4
5
6
7
8

2
9
6
4
7

এবং যোগ করার পর আমাদের যোগফল অ্যারেটা হবে এরকম

4
5
6
7
8

2
9
6
4
7

6
4
3
2
6
1

সমস্যা নাই যদিও। সবকাজ শেষ হবার পর আমরা রেজাল্ট অ্যারেটা উল্টে নিব। তাতেই সবকিছু সোজা হয়ে যাবে।

#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    return 0;
}

এবার যোগ করা শুরু করি।

প্রথমে যখন আমরা যোগ করা করি তখন কিন্তু আমাদের হাতে কিছু থাকে না।
আমরা একটা variable নিবো carry;
আমাদের হাতে যা থাকে সেটা এই carry তে থাকবে। প্রথমে হাতে কিছুই থাকে না, তাই carry = 0

এরপর আমরা যোগ করব, firstNumber [i] + secondNumber [i] + carry এইভাবে

যোগফলটা carry-তেই রাখলাম।

#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
    }
    
    return 0;
}

কিভাবে কাজটা হবে সেটা একটু বুঝার চেষ্টা করি।
আমারা প্রথম দুইটা ডিজিটের যোগফল বের করালাম। এবং সেই যোগফল carry-তে আছে।
এখন দেখতে হবে, carry >= 10 কিনা।

যদি carry >= 10 হয় তাহলে আমরা রেজাল্টে বসাব, carry % 10
এবং আমাদের হাতে থাকবে carry / 10

যদি carry < 10 হয় তাহলে আমরা রেজাল্টে বসাব, carry
এবং আমাদের হাতে থাকবে 0

এই দুইটা if-else কন্ডিশন আসলে একই কাজ করে। মানে একটা লাইন দিয়েই দুইটা কাজ করা যায়; if-else লাগবে না।
যেমন ধরি, আমাদের একটা নাম্বার আছে, number
এবং আমরা রেজাল্টে বসাব, number % 10
এবং carry তে বসাব number / 10

result = number % 10
carry = number / 10

একটু খেয়াল করলে দেখা যায়, number value 10 থেকে বড় বা ছোট যাই হোক না কেন, result and carry value সবসময় একই আসবে। একটু চিন্তা করে দেখেন


    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }

এইভাবে লুপটা ঘুরতে থাকবে। এবং লুপ ঘুরা শেষ হলে আমরা আমাদের উত্তরটা পেয়ে যাব result অ্যারেতে।

একটা সমস্যা কিন্তু থেকে গেল। এখন যদি আমরা result array print দিই তাহলে কি পাব?

64326

result অ্যারেটা reverse করতে হবে, সেটা আমরা জানি। কিন্তু 1 টা কোথায় গেল?

খেয়াল করে দেখেন, লুপ শেষ হয়ে গেলেও আমাদের carry-তে একটা 1 ছিল, যেটা আমরা result array তে ঢুকাতে পারি নাই। সেটা ঢুকাতে হবে।

এইক্ষেত্রে আমরা জানি, carry তে এখন 1 আছে। কিন্তু ধরেন, আমরা অনেক অনেক বড় নাম্বার যোগ করছি। তখন হয়তো carry-তে 54362; এতবড় একটা নাম্বারও থাকতে পারে। তাই না?

এইজন্য আমরা একটা লুপ চালাবো। এবং একটা একটা করে ডিজিট carry থেকে নিয়ে result array তে ঢুকাব।


    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }
    
    while ( carry ) {
        result [i] = carry % 10;
        carry /= 10;
        i++;
    }
    
    return 0;

আরেকটা সমস্যা। সেটা হল, for loop এর loop variable i-কে আমরা while loop-এর ভেতরে পাব না।

কিন্তু while loop-এর ভেতরে আমাকে তো জানতে হবে, result array-তে কত নাম্বার index থেকে আমি ঢুকানো শুরু করব?

for loop-এ যে পর্যন্ত ঢুকানো হয়েছিল, তারপরের থেকে, তাই না?

বেশি ঝামেলা না করে আমরা result array-টার জন্য আলাদা একটা variable রাখতে পারি।

সবশেষে আমরা result array টা reverse করে দিব।


#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    int carry = 0;
    int resultLength = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }
    
    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }
    
    reverse(result, result + resultLength);
    
    return 0;
}

এখন কথা হল, আমরা এইখানে firstNumber and secondNumber initialize করে দিয়েছিলাম। এটা তো আসলে করা যাবে না। আমাদেরকে ইনপুট নিতে হবে। কিন্তু অনেক বড় বড় সংখ্যা আমরা কিভাবে ইনপুট নিব?

ইনপুটটা আমরা string হিসেবে নিতে পারি।
যদি তাই করি, তাহলে যোগ করার সময় আমাদের একটা কাজ অতিরিক্ত করতে হবে।

সেটা হল, এইক্ষেত্রে ডিজিটগুলা তো আসলে একেকটা character; তাই যোগ করার সময় character গুলাকে ডিজিট করে নিতে হবে।

মানে হল, ‘0’-কে convert করে 0 করবো
‘1’-কে convert করে 1 করবো

আমরা কোডটা দেখে ব্যাপারটা বুঝার চেষ্টা করি।


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    char secondNumber [N];
    int result [N + 10];

    scanf ("%s %s", firstNumber, secondNumber);

    reverse(firstNumber, firstNumber + strlen(firstNumber));
    reverse(secondNumber, secondNumber + strlen(secondNumber));

    int carry = 0;
    int resultLength = 0;

    for ( unsigned int i = 0; i < strlen(firstNumber); i++ ) {
        carry = (firstNumber [i] - '0') + (secondNumber [i] - '0') + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

অতীব চমকপ্রদ একটা কোড করে ফেললাম। এবার একটা ইনপুট দিয়ে টেস্ট করা যাক।

input:
123
1

expected output:
124

actual output:
🙄

ঘটনা যেটা হইছে সেটা অনেকটা এমন

1
2
3
আলু
পটল
1
😕
😐
4

মানে হল, ২য় নাম্বারটা ছোট হবার কারনে তার আগের ঘরগুলাতে Garbage value থাকবে।

সমাধান যেটা করা যেতে পারে, যোগ শুরু করার আগেই অ্যারেগুলা 0 দিয়ে initialize করে দেয়া, যাতে করে আলু, পটল থাকতে না পারে।

0 দিয়ে initialize করে দেয়ার পর আমরা ইনপুট নিবো। ইনপুটের নাম্বারগুলো 0 কে replace করে বসে যাবে। আমাদের অ্যারে সাইজ তো বেশ বড়, ইনপুট নেয়ার পর যে ঘরগুলো খালি থাকবে সেগুলোতো তখন 0 পাওয়া যাবে, আলু পটল না।

আরেকটা ছোট সমস্যা আছে।
আমরা তো এখন string হিসেবে ইনপুট নিচ্ছি। আমরা জানি, string ইনপুট নিলে শেষে একটা

 End of string ('\0') character 

automatically বসে যায়। কাজেই কাজ শুরুর আগে এটাকেও 0 করে দিতে হবে।

এরপরের চিন্তার বিষয় হল, আমরা আমাদের লুপটা কতবার চালাব?

উত্তর হল, দুইটা নাম্বারের মধ্যে যে নাম্বারের length সবচেয়ে বেশি ততবার চালাব।

আমি কি ঠিক বলতেছি? আচ্ছা, এবার তাহলে কোডটা দেখা যাক।


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    char secondNumber [N];
    int result [N + 10];

    // initialize the array with '0'
    memset(firstNumber, '0', sizeof firstNumber);
    memset(secondNumber, '0', sizeof secondNumber);

    scanf ("%s %s", firstNumber, secondNumber);

    int firstNumberLength = strlen (firstNumber);
    int secondNumberLength = strlen (secondNumber);
    int maximumLength = max (firstNumberLength, secondNumberLength);

    reverse(firstNumber, firstNumber + strlen(firstNumber));
    reverse(secondNumber, secondNumber + strlen(secondNumber));

    // normalize the last end of string character
    firstNumber [firstNumberLength] = '0';
    secondNumber [secondNumberLength] = '0';

    int carry = 0;
    int resultLength = 0;

    for ( int i = 0; i < maximumLength; i++ ) {
        carry = (firstNumber [i] - '0') + (secondNumber [i] - '0') + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

যোগের কাহিনি শেষ। :mrgreen:

এবার আসি গুনের কাহিনিতে। ধরি, আমাদের গুন করতে দেয়া হল,
9452 X 675

সাধারনত আমরা ছোটবেলায় গুনটা যেভাবে করতাম,




9
4
5
2



X
6
7
5


4
7
2
6
0

6
6
1
6
4
X
5
6
7
1
2
X
X
6
3
8
0
1
0
0

এইবার আমরা বড়বেলার গুনফল বের করব। এবং সেটা দেখতে হবে অনেকটা এমন




9
4
5
2





X
675
6
3
8
0
1
0
0

মানে একবারেই আমরা গুনফলটা বের করে ফেলব। ঘটনাটা আমি বুঝানোর চেষ্টা করি।

এখানে 675 কে অ্যারেতে আলাদা আলাদা ডিজিট হিসেবে চিন্তা না করে একটা সংখ্যা হিসেবে চিন্তা করতে হবে। এবং একবারে 675 দিয়েই গুনের কাজ করতে হবে। যেমন:

675 X 2    =    1350 
675 X 50   =   33750
675 X 400  =  270000
675 x 9000 = 6075000
-----------------------
             6380100

অথবা আরেকটা কাজ করা যায়। মনে করি আমাদের কাছে একটা খালি অ্যারে আছে








675 x 2 = 1350
put the last 0 in the array
carry = 135







0

675 X 5 = 3375 + carry = 3375 + 135 = 3510
put the last 0 in the array
carry = 351






0
0

675 X 4 = 2700 + carry = 2700 + 351 = 3051
put the last 1 in the array
carry = 305





1
0
0

675 X 9 = 6075 + carry = 6075 + 305 = 6380
put the last 0 in the array
carry = 638




0
1
0
0

এখন হাতে যে carry আছে সেটাই অ্যারেটার আগে বসিয়ে দিতে হবে

6
3
8
0
1
0
0

এবার দেখব আমাদের সবশেষ কোড


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    int secondNumber;
    int result [N + 10];

    scanf ("%s %d", firstNumber, &secondNumber);

    int firstNumberLength = strlen (firstNumber);

    reverse(firstNumber, firstNumber + strlen(firstNumber));

    int carry = 0;
    int resultLength = 0;

    for ( int i = 0; i < firstNumberLength; i++ ) {
        carry = ((firstNumber [i] - '0') * secondNumber) + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

একটাই প্রশ্ন থেকে যায়, ২য় নাম্বারটা আমরা কেন অ্যারেতে নিলাম না? যদি ২য় নাম্বারটা অনেক অনেক বড় হয় তখন কি হবে?

উত্তর: হবে আর কি কিছু একটা। এই শিশু বয়সে ওইসব নিয়ে টেনশন করার কি দরকার? চেপে যান 😐

One thought on “Big-Integer Tutorial with C

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s