الگوریتمستان - کلاس اعداد بزرگ در ++C

یکی از دغدعه‌های مهم برخی از افرادی که در حوزه‌هایی مانند رمزنگاری برنامه‌نویسی می‌کنند کار با اعداد بسیار بزرگ صحیح است. در چنین حوزه‌هایی نیاز زیادی به عملیات ریاضی روی اعداد بزرگ وجود دارد. تا کنون کلاس‌ها و توابع زیادی روی اینترنت برای حل این مشکل از طرف برنامه‌نویسان معرفی شده است. آنچه که در اینجا معرفی می‌کنم، کلاسی است برای امکان تعریف اعداد بسیار بزرگ که توسط خودم نوشته شده است.

  

class BigInteger

{

  friend BigInteger BigAbs(const BigInteger &);

  

  friend BigInteger operator + (long long , const BigInteger &);

  friend BigInteger operator + (string , const BigInteger &);

  friend BigInteger operator - (long long , const BigInteger &);

  friend BigInteger operator - (string , const BigInteger &);

  friend BigInteger operator * (long long , const BigInteger &);

  friend BigInteger operator * (string , const BigInteger &);

  friend BigInteger operator / (long long , const BigInteger &);

  friend BigInteger operator / (string , const BigInteger &);

  friend BigInteger operator % (long long , const BigInteger &);

  friend BigInteger operator % (string , const BigInteger &);

  friend BigInteger operator ^ (long long , const BigInteger &);

  friend BigInteger operator ^ (string , const BigInteger &);

  friend bool operator == (long long , const BigInteger &);

  friend bool operator == (string , const BigInteger &);

  friend bool operator != (long long , const BigInteger &);

  friend bool operator != (string , const BigInteger &);

  friend bool operator < (long long , const BigInteger &);

  friend bool operator < (string , const BigInteger &);

  friend bool operator > (long long , const BigInteger &);

  friend bool operator > (string , const BigInteger &);

  friend bool operator <= (long long , const BigInteger &);

  friend bool operator <= (string , const BigInteger &);

  friend bool operator >= (long long , const BigInteger &);

  friend bool operator >= (string , const BigInteger &);

  friend ostream & operator << (ostream &out, const BigInteger &);

  friend istream & operator >> (istream &in, BigInteger &r);

private:

  char *data;

  unsigned size;

  bool sign;

  void reverse(string &str);

public:

  BigInteger();

  BigInteger(long long);

  BigInteger(string);

  BigInteger(const BigInteger &);

  ~BigInteger();

  bool isValid();

  unsigned length();

  string toString();

  int operator [ ] (unsigned index) const;

  BigInteger operator = (long long);

  BigInteger operator = (string);

  BigInteger operator = (const BigInteger &);

  BigInteger operator + (long long) const;

  BigInteger operator + (string) const;

  BigInteger operator + (const BigInteger &) const;

  BigInteger operator + () const;

  BigInteger operator += (long long);

  BigInteger operator += (string);

  BigInteger operator += (const BigInteger &);

  BigInteger operator - (long long) const;

  BigInteger operator - (string) const;

  BigInteger operator - (const BigInteger &) const;

  BigInteger operator - () const;

  BigInteger operator -= (long long);

  BigInteger operator -= (string);

  BigInteger operator -= (const BigInteger &);

  BigInteger operator * (long long) const;

  BigInteger operator * (string) const;

  BigInteger operator * (const BigInteger &) const;

  BigInteger operator *= (long long);

  BigInteger operator *= (string);

  BigInteger operator *= (const BigInteger &);

  BigInteger operator / (long long) const;

  BigInteger operator / (string) const;

  BigInteger operator / (const BigInteger &) const;

  BigInteger operator /= (long long);

  BigInteger operator /= (string);

  BigInteger operator /= (const BigInteger &);

  BigInteger operator % (long long) const;

  BigInteger operator % (string) const;

  BigInteger operator % (const BigInteger &) const;

  BigInteger operator %= (long long);

  BigInteger operator %= (string);

  BigInteger operator %= (const BigInteger &);

  BigInteger operator ^ (long long) const;

  BigInteger operator ^ (string) const;

  BigInteger operator ^ (const BigInteger &) const;

  BigInteger operator ^= (long long);

  BigInteger operator ^= (string);

  BigInteger operator ^= (const BigInteger &);

  BigInteger operator ++ ();

  BigInteger operator ++ (int);

  BigInteger operator -- ();

  BigInteger operator -- (int);

  bool operator == (long long) const;

  bool operator == (string) const;

  bool operator == (const BigInteger &) const;

  bool operator != (long long) const;

  bool operator != (string) const;

  bool operator != (const BigInteger &) const;

  bool operator < (long long) const;

  bool operator < (string) const;

  bool operator < (const BigInteger &) const;

  bool operator > (long long) const;

  bool operator > (string) const;

  bool operator > (const BigInteger &) const;

  bool operator <= (long long) const;

  bool operator <= (string) const;

  bool operator <= (const BigInteger &) const;

  bool operator >= (long long) const;

  bool operator >= (string) const;

  bool operator >= (const BigInteger &) const;

};

کلاس BigInteger به زبان ++C از عملیات مقدماتی ضرب، جمع، تفریق، تقسیم، باقیمانده و توان رسانی پشتیبانی می‌کند. اگر کد کلاس را بررسی کنید متوجه می‌شوید که اکثر توابع کلاس برای نوع داده long long و کلاس string سربارگذاری شده‌اند تا کاربر بتواند از طریق این دو مجموعه هم با کلاس در ارتباط باشد. همچنین عملگرهای >> و << برای ورودی و خروجی جریان سربارگذاری شده است.

به عنوان نمونه:

#include <iostream>

#include "BigInteger.h"

using namespace std;

int main()

{

  BigInteger a = 1, b(2), c, d, e, f;

  cin >> c >> d;

  e = c * d + "1364";

  f = ++b * e ^ 3;

  cout << a << "\t" << b << "\t" << e << "\t" << f;

  return 0;

}

این کلاس چند تابع ویژه دارد:

• تابع BigAbs قدرمطلق عدد را محاسبه می‌کند.
• تابع isValid معتبر بودن عدد را بررسی می‌کند.
• تابع length طول عدد را بر می‌گرداند.
• تابع toString رشته‌ای را که شامل عدد مورد نظر است تولید می‌کند.

در ضمن عملگر [] هم برای دسترسی سریع به ارقام عدد سربارگذاری شده است. به عنوان نمونه [a[0 و [a[2 به ترتیب یکان و صدگان عدد a را نشان می‌دهند. در صورتی که اندیس وارد شده خارج از اندازه عدد باشد مقدار 1- برگشت داده می‌شود.

نکته قابل توجه در این کلاس سربارگذاری سه عملگر تقسیم (خارج قسمت)، باقیمانده و توان است. برای پیاده‌سازی تقسیم و باقیمانده اعداد بزرگ سعی کردم بهینه‌ترین الگوریتم ممکن را پیاده سازی کنم، تا زمان محاسبه بیهینه شود.

این نکته را هم به خاطر داشته باشید که اگر مقسوم یا مقسوم علیه یا هر دو منفی باشند، نتیجه محاسبات کمی‌فرق خواهد کرد. به این مثال ساده توجه کنید:

9 = 1 * 5 + 4    =>    9 / 5 = 1 , 9 % 5 = 4

-9 = -2 * 5 + 1    =>    -9 / 5 = -2 , -9 % 5 = 1

9 = -1 * -5 + 4    =>    9 / -5 = -1 , 9 % -5 = 4

-9 = 2 * -5 + 1    =>    -9 / -5 = 2 , -9 % -5 = 1

عملگر توان هم که با عملگر ^ پیاده‌سازی شده، به این خاطر است که از الگوریتم بهینه‌تری نسبت به توان رسانی معمولی استفاده کرده‌ام. در حالت عادی محاسبه توان nام عدد از مرتبه‌ی $O(n)$ است. اما الگوریتمی‌که دراین کلاس به کار رفته از مرتبه‌ی   $O(log\;n)$    است که باعث کاراتر شدن محاسبات می‌شود.

از جمله کاربردهای چنین کلاسی ضرب اعداد بزرگ در هم است. به عنوان مثال، برنامه‌ی زیر فاکتوریل عدد 1000 را - تقریبا 2600 رقم!!! - به راحتی حساب می‌کند:

#include <iostream>

#include "BigInteger.h"

using namespace std;

int main()

{

  unsigned i;

  BigInteger f = 1;

  for(i = 2 ; i <= 1000 ; i++)

    f *= i;

  cout << " 1000! = " << f << endl;

  return 0;

}

از دوستان عزیزی که قصد استفاده از این کلاس را دارند خواهشمندم نظرات خود را در مورد آن بیان کنند و اگر مشکلی در محاسبات مشاهده شد، حتما اطلاع دهید تا اصلاح شود. همینطور در صورتی هم که برای محاسبات مختلف الگوریتم بهینه‌تری سراغ دارید یا توابع دیگری را برای اضافه کردن به کلاس مد نظر دارید، مطرح کنید.

کد کلاس در این ریپازیتوری منتشر شده است.