8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Katta sonlar bilan ishlash sinflari. Kriptografiya yoki IPv6 manzillari bilan ishlashda ko‘pincha juda ko‘p sonli arifmetikaga ehtiyoj tug‘iladi. C/C++ kutubxonalari ikkita katta sonni ko‘paytirish yana bir funksiyada qanday bajarilishini ko‘rib chiqamiz.
OpenSSL katta sonlar bilan ishlash uchun ajralmas mexanizmi, funksiyalari bor. Agar kutubxona bo‘lsa, unday quyidagicha foydalanish mumkin:
#include "stdafx.h"
#include
#include
#include
int main() {
BN_CTX *ctx = BN_CTX_new(); // hisoblash uchun massiv
BIGNUM *mybignum = nullptr; // koʻpaytirilishi kerak boʻlgan son
BIGNUM *mul = BN_new(); // natija
BN_dec2bn(&mybignum, "18446744073709551615"); // 2^64-1 BN_mul(mul, mybignum, mybignum, ctx);
// natijani chop qilish char *dec = BN_bn2dec(mul); if (dec) {
printf("%s\n", dec); OPENSSL_free(dec);
}
// xotirani tozalash
BN_free(mybignum); BN_free(mul);
}
Bu C++dan ko‘proq C kodidir. Bu istisnolar bilan bir muhitda u bilan ishlash uchun xavfli va xotira oqib ketishi mumkin.
Gcrypt. Libgcrypt kutubxonasi GnuPG loyihasi asosida yaratilgan va shifrlash bilan ishlash uchun asosiy funksiyalarni, shu jumladan katta sonlar bilan taʻminlaydi. Bu kutubxonadan quyidagicha foydalanish mumkin:
#include
#include
int main() {
unsigned long long mybignum = 18446744073709551615ull; gcry_mpi_t max_ul = gcry_mpi_new(64);
gcry_mpi_t mul = gcry_mpi_new(128);
size_t scanned = 0;
gcry_mpi_scan(&max_ul, GCRYMPI_FMT_USG, &mybignum, sizeof(unsigned long long), &scanned);
assert(scanned==sizeof(unsigned long long) && "failed to scan the whole number"); gcry_mpi_mul(mul, max_ul, max_ul);
gcry_mpi_dump(mul);
gcry_mpi_release(mul); gcry_mpi_release(max_ul);
}
Muammolar hali ham bir xil - C kodi, unda resurslarni o‘zimiz yaratishimiz mumkin.
GMP. Avvalgi ikki kutubxona kriptografiyada foydalanish uchun ishlatiladi. GMP faqat raqamlar bilan ishlaydigan maxsus kutubxona. Uning yordamida quyidagicha dastur tuzish mumkin:
#include
#include
int main() { mpz_t mybignum; mpz_t mul;
mpz_init_set_str(mybignum, "18446744073709551615", 10); mpz_init(mul);
mpz_mul(mul, mybignum, mybignum); gmp_printf("%Zd\n", mul);
mpz_clear(mybignum); mpz_clear(mul);
}
Boost.Multiprecision. Bu kutubxona katta sonlarning o‘zi bilan arifmetikani amalga oshirmaydi, faqat ular bilan ishlash uchun qulay, C++ interfeysini taʻminlaydi, uchinchi tomon kutubxonalaridan hisob-kitoblar uchun backend sifatida foydalanadi. Interfeys qanchalik qulayligi quyidagi dastur fragmentida ko‘rsatilgan:
#include
#include
int main() {
using namespace boost::multiprecision; int128_t mybignum = 18446744073709551615ull; cout << mybignum * mybignum << endl;
}
Bunday tez-tez uchraydigan masalalar uchun kutubxonalardan foydalanishda xotira va bajarish juda mushkul. C++ standartlashtirish bo‘yicha Milliy ishchi guruhdan rus ishlab chiquvchilari bir xil ishonishadi, shuning uchun standart kutubxonaga mustaqil ravishda wide integer tiplarini kiritish taklifi bilan chiqqan. Ulardan dasturda quyidagicha foydalanish mumkin:
auto mybignum = 18446744073709551615_int128; std::cout << mybignum * mybignum << std::endl;
}
Megabayt xotira oladigan raqamlar bilan ishlashni istaysizmi? Hech qanday muammo yo‘q, 100! ni hisoblash dasturini keltiramiz:
#include #include

using int_mb = wide_int<1024*1024>;

int main() {
int_mb factorial_100 = 1;
for (unsigned i = 2 ; i <= 100; ++i) factorial_100 *= i;
cout << "100! = " << factorial_100 << endl;
}