Ý tưởng thực hiện tính toán số lớn

Gia_Khang_Nguyen_Lam · March 23, 2019, 1:46am

Tính tổng 1 + (1+2) + (1+2+3)+…+(1+2+3+…+n) (n là một số rất lớn khoảng 10^11 chữ số)
mọi người giúp em cái ý tưởng để thực hiện bt này với thank all .

rogp10 · March 21, 2019, 4:07pm

Biến đổi đại số trước đã

Kết quả sẽ không quá 128 bit.

Gia_Khang_Nguyen_Lam · March 22, 2019, 2:06pm

Bạn có thể giải thích thêm về ý tưởng ko. Mình định dùng kiểu char để chứa nhưng lại chưa có ý tưởng làm gì tiếp theo.

quakhoihai · March 22, 2019, 3:06pm

temp = 0, S = 0
for i to n
  temp += i
  S += temp

DangHuynhAnh · March 22, 2019, 2:50pm

Vấn đề ở đây là thuật toán lưu số ở dạng large number bạn à. Chứ không phải thuật toán để tính

Gia_Khang_Nguyen_Lam · March 23, 2019, 1:05pm

Thuật toán này dùng tính toán số nhỏ thôi bạn ơi của mình tới 10^11 bạn chạy chương trình kiểu đó nó ko in đâu.

tntxtnt · March 23, 2019, 1:17pm

ngồi viết công thức tính tổng ra :V
1+2+3+…+k = k(k+1)/2
cho k chạy từ 1 tới n, vậy là tính tổng S = 0.5(k² + k) với k từ 1 tới n :V

2S = \sum_{k=1}^{n}{k^2 + k}
= \sum_{k=1}^{n}{k^2} + \sum_{k=1}^{n}{ k}

Google tổng bình phương từ 1 tới n ta có: https://brilliant.org/wiki/sum-of-n-n2-or-n3/
vậy
2S = n(n+1)(2n+1)/6 + n(n+1)/2
12S = n(n+1)(2n+1) + 3n(n+1)
= n(n+1)(2n+4)
S = n(n+1)(n+2) / 6

:V :V :V

Gia_Khang_Nguyen_Lam · March 23, 2019, 1:42pm

Cám ơn bạn công thức cũng là một cách hay nhưng mình lại muốn học kĩ thuật để xử lí dạng big number bạn có ý tưởng nào không thank bạn nhiều.

tntxtnt · March 23, 2019, 2:11pm

cộng trừ nhân chia như toán tiểu học chứ sao nữa :V

 1234
x  56
-----
 7404 
6170
-----
69104

Lưu số dạng chuỗi đảo ngược, để khi cộng ví dụ 99+1=100 thì thêm số 1 vào sau dễ hơn. Ví dụ 1234 lưu là “4321”, 5678 lưu là “8765”, khi cộng thì cộng từng ký tự, nhớ 1 gì đó nữa v.v…

cách khác là xài thư viện có sẵn, ví dụ gmp cho C, gmpxx cho C++, hoặc Boost multiprecision. Bạn có thể thử ở Wandbox

ví dụ xài int 128-bit: https://wandbox.org/permlink/i8BjReiyfdglEIdj

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using int128_t = boost::multiprecision::int128_t;

int main()
{
    int128_t n = 100'000'000'000LL; //10^11
    int128_t s = n * (n + 1) * (n + 2) / 6;
    std::cout << s << "\n";
}

ví dụ xài cpp_int: https://wandbox.org/permlink/F6cMFd8fZZT8jkGj

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using BigInt = boost::multiprecision::cpp_int;

int main()
{
    BigInt n = 100'000'000'000LL; //10^11
    BigInt s = n * (n + 1) * (n + 2) / 6;
    std::cout << s << "\n";
}

ví dụ xài gmp thông qua Boost.Multiprecision: https://wandbox.org/permlink/NECi8mozaDEr4YnR

#include <iostream>
#include <boost/multiprecision/gmp.hpp>
using BigInt = boost::multiprecision::mpz_int;

int main()
{
    BigInt n = 100'000'000'000LL; //10^11
    BigInt s = n * (n + 1) * (n + 2) / 6;
    std::cout << s << "\n";
}