قمت بحساب عدد فيبوناتشي رقيم بليون وهو عدد كبير للغاية
النتيجة كانت :
795231787455429732005474545710
x 10^208987610
Execution time: 3386486 milliseconds ~ 1 hour
اخذ البرنامج حوالي ساعة كاملة لحسابه
طبعا هناك عدة تحديات هنا:
1- مشكلة overflow
لا يمكن للمتغير في c++ ان يخزن اكبر من الرقم 1-63^2
لذلك قمت بتخزين الارقام على شكل linked-list
2-مشكلة التخزين:
هذا الرقم الضخم قد يصل حجمه ل200 ميغا بايت لكن المشكلة انه وخلال حساب اعداد فيبوناتشي فانك تحتاج تخزن القيم المؤقتة للاعداد السابقة مما يتطلب مساحة تخزين عالية
قمت بحل المشكلة بحل ليس مثالي وهو التخلص من الdigits واستبدالها باصفار كلما تجاوز 30 digit
بعض الحلول الثانية المقترحة هي عمل الحساب على حاسوب سحابي
3-مشكلة السرعة:
نفس المشكلة مع عدد بهذا الكم الكبير من digits تصبح عملية الجمع على العدد بطيئة جدا والحل كان ايضا عن طريق التخلص من الdigits
وجدت بعض المبرمجين قامو بحساب نفس العدد خلال 9 ثواني دون التخلص من الdigits عن طريق مكتبة اسمها gnm.h
#include <iostream>
#include <string>
#include <algorithm>
#include <chrono>
using namespace std;
class Node
{
public:
int val;
Node *next;
~Node()
{
delete next;
}
};
class BigInt
{
public:
Node *head;
BigInt(string num)
{
head = new Node();
Node *temp = head;
for (int i = num.length() - 1; i >= 0; i--)
{
char ch = num.at(i);
int val = ch - '0';
head->val = val;
if (i > 0)
{
head->next = new Node();
head = head->next;
}
}
head = temp;
}
void printNum()
{
Node *temp = head;
string result = "";
while (head != NULL)
{
result += to_string(head->val);
head = head->next;
}
reverse(result.begin(), result.end());
cout << result << endl;
head = temp;
}
void AddNum(BigInt *other)
{
Node *p1 = other->head;
Node *p2 = head;
Node *resultHead = new Node();
Node *result = resultHead;
int carry = 0;
while (p1 != NULL && p2 != NULL)
{
int val = p1->val + p2->val + carry;
if (val > 9)
{
int reminder = val % 10;
carry = (val - reminder) / 10;
val = reminder;
}
else
{
carry = 0;
}
result->val = val;
if (p1->next != NULL || p2->next != NULL)
{
result->next = new Node();
result = result->next;
}
p1 = p1->next;
p2 = p2->next;
}
while (p1 != NULL)
{
int val = p1->val + carry;
if (val > 9)
{
int reminder = val % 10;
carry = (val - reminder) / 10;
val = reminder;
}
else
{
carry = 0;
}
result->val = val;
if (p1->next != NULL)
{
result->next = new Node();
result = result->next;
}
p1 = p1->next;
}
while (p2 != NULL)
{
int val = p2->val + carry;
if (val > 9)
{
int reminder = val % 10;
carry = (val - reminder) / 10;
val = reminder;
}
else
{
carry = 0;
}
result->val = val;
if (p2->next != NULL)
{
result->next = new Node();
result = result->next;
}
p2 = p2->next;
}
if (carry > 0)
{
result->next = new Node();
result->next->val = carry;
}
delete head;
head = resultHead;
}
int length()
{
Node *current = head;
int result = 0;
while (current != NULL)
{
result++;
current = current->next;
}
return result;
}
void drop30()
{
Node *current = head;
for (int i = 0; i < 10; i++)
{
Node *temp = current->next;
current->next = nullptr; // Update the next pointer to nullptr
delete current;
current = temp;
}
head = current;
}
~BigInt()
{
if (head)
{
delete head;
}
}
};
int main()
{
auto start = std::chrono::high_resolution_clock::now();
BigInt *bn = new BigInt("1");
BigInt *bn2 = new BigInt("1");
int index = 2;
int zeros = 0;
for (int i = 0; i < 500000000 - 1; i++)
{
index += 1;
bn->AddNum(bn2);
index += 1;
bn2->AddNum(bn);
if (bn->length() > 30)
{
bn->drop30();
bn2->drop30();
zeros += 10;
}
}
cout << "***************" << endl;
cout << index << endl;
bn2->printNum();
cout << " x 10^" << zeros << endl;
delete bn;
delete bn2;
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
// Output the execution time
std::cout << "Execution time: " << duration.count() << " milliseconds" << std::endl;
return 0;
}
