Tính toán với các số lớn vô hạn bằng thư viện GMP
TRANG CHỦ | TIN TỨC | DIỄN ĐÀN | BÀI VIẾT | DOWNLOADS | HỎI ĐÁP | TRỢ GIÚP flagflag
Tra từ điển
Menu chính
Tư liệu - Tiện ích
Đăng nhập
Bí danh:

Mật khẩu:



Lost Password?

Register now!
Thanks to
TOP  >  Programming/Database  >  Tính toán với các số lớn vô hạn bằng thư viện GMP
Khi tính toán với các số lớn (ví dụ 2 lũy thừa 2048 v.v) thường phải sử dụng các thư viện chuyên dụng. Nổi tiếng trong các loại này có thể kể ra:

- GMP - GNU Multiple Precision
- CLN - Class Library for Numbers
- Apfloat - A C++ High Performance Arbitrary Precision Arithmetic Package

Bài viết này giới thiệu cách cài đặt và sử dụng GMP, nhân dịp người viết cần phải dùng nó để debug hệ thống hardware của dự án điện thoại di động thế hệ mới.

GMP có đặc điểm là cực nhanh, ban đầu được thiết kế cho ngôn ngữ C nhưng sau này có hỗ trợ cả C++. Bên cạnh C/C++, còn có các interfaces cho các ngôn ngữ khác như Perl, PHP, Java. Ví dụ PHP có extension php_gmp giúp việc sử dụng GMP trở nên rất dễ dàng. Tham khảo tại php.net - GMP Functions.

Thư viện GMP có thể dùng trong tính toán cơ bản (cộng, trừ, nhân, chia) các số nguyên, số thực. Nhược điểm của GMP là khá khó sử dụng vì phải viết code theo dạng ngôn ngữ bậc thấp, thiếu tính trừu tượng. Các hàm cơ bản nhất của GMP có dạng như sau:

- Khai báo: mpf_t xf, yf, zf;
- Khởi tạo (1): mpf_init(xf);
- Khởi tạo (2): mpf_init2(xf，bits);
- Giải phóng: mpf_clear(xf);
- Thay thế: mpf_set_str(xf, str, base);
- Cộng: mpf_add(zf, xf, yf);
- Trừ: mpf_mul(zf, xf, yf);
- Nhân: mpf_mul(zf, xf, yf);

Tuy nhiên khi đã làm quen với các hàm trên thì có thể viết các chương trình lớn thực hiện các tính toán phức tạp mà không phải lo nghĩ gì tới giới hạn của các con số (GMP dễ dàng tính toán các số có 600 triệu chữ số). Xem demo online của GMP tại Try GMP!.

Cách cài đặt và sử dụng GMP

1) Download tại http://gmplib.org/, bài viết này sử dụng bản gmp-4.2.2 làm ví dụ.

2) Cài đặt với GCC trên Unix/Linux/Cygwin
$ cd
$ tar xjf gmp-4.2.2.tar.bz2
$ cd gmp-4.2.2
$ ./configure
$ make
$ make check
$ make install

3) Test
Đi cùng với gói gmp có một chương trình expr rất hay cho phép biên dịch và thực hiện các phép tính từ dòng lệnh, ví dụ tại dòng lệnh nhập công thức '1+gcd(87324,78263148,7896)*(10**1989879887)', sau khoảng 0.2 giây, expr sẽ trả về kết quả là một số có gần 2 triệu chữ số (** ở đây biểu thị phép toán lũy thừa).

- Compile và cài đặt expr như là một thư viện chuẩn để có thể dùng về sau
$ cd
$ cd gmp-4.2.2/demos/expr/
$ make libexpr.a
$ cp libexpr.a /usr/local/lib/
$ cp expr.h /usr/local/include/

- Tạo một file foo.c như sau để thử nghiệm, chú ý phần header với khai báo gmp.h và expr.h
/* Demo program to run expression evaluation.

Copyright 2000, 2001, 2002, 2004 Free Software Foundation, Inc.

/* Usage: ./foo [-b base] expression

   Evaluate each argument as a simple expression. In all cases the input
   base can be set with -b, or the default is "0" meaning decimal with 
   "0x" allowed.

   This is a pretty trivial program, it's just an easy way to experiment
   with the evaluation functions.  */

#include <stdio.h>
#include <stdlib.h>

#include "gmp.h"
#include "expr.h"

void run_expr (int base, char *str)
{
  int  ret;
  int  outbase = (base == 0 ? 10 : base);

  mpz_t  res, var_a, var_b;

  mpz_init (res);
  mpz_init_set_ui (var_a, 55L);
  mpz_init_set_ui (var_b, 99L);

  ret = mpz_expr (res, base, str, var_a, var_b, NULL);
      
  if (ret == MPEXPR_RESULT_OK)
    {
      mpz_out_str (stdout, outbase, res);
      printf ("\n");
    }
  else
      printf ("Invalid (return code %d)\n", ret);

   mpz_clear (res);
   mpz_clear (var_a);
   mpz_clear (var_b);
}

int main (int argc, char *argv[])
{
  int  base = 0;
  int  seen_expr = 0;
  int  opt;
  char *arg;

  for (;;)
    {
      argv++;
      arg = argv[0];
      if (arg == NULL)
        break;

      if (arg[0] == '-')
        {
          for (;;)
            {
              arg++;
              opt = arg[0];

              switch (opt) {
              case '\0':
                goto end_opt;

              case 'b':
                arg++;
                if (arg[0] == '\0')
                  {
                    argv++;
                    arg = argv[0];
                    if (arg == NULL)
                      {
                      need_arg:
                        fprintf (stderr, "Need argument for -%c\n", opt);
                        exit (1);
                      }
                  }
                base = atoi (arg);
                goto end_opt;

              case '-':
                arg++;
                if (arg[0] != '\0')
                  {
                    /* no "--foo" options */
                    fprintf (stderr, "Unrecognized option --%s\n", arg);
                    exit (1);
                  }
                /* stop option interpretation at "--" */
                for (;;)
                  {
                    argv++;
                    arg = argv[0];
                    if (arg == NULL)
                      goto done;
                    run_expr (base, arg);
                    seen_expr = 1;
                  }

              default:
                fprintf (stderr, "Unrecognized option -%c\n", opt);
                exit (1);
              }
            }
        end_opt:
          ;
        }
      else
        {
          run_expr (base, arg);
          seen_expr = 1;
        }
    }

 done:
  if (! seen_expr)
    {
      printf ("Usage: foo [-b base] expression\n");
      exit (1);
    }

  return 0;
}

- Biên dịch foo.c như sau, chú ý phần link tới thư viện gmp và expr
$ gcc foo.c -lexpr -lgmp -o foo

- Chạy thử 1: thực hiện phép tính: (5+6-7)*8/2
./foo '(5+6-7)*8/2'
16

- Chạy thử 2: tính 2 lũy thừa 2048, dùng cơ số 10
$ ./foo -b10 '2**2048'
32317006071311007300714876688669951960444102669715
48403213034542752465513886789089319720141152291346
36887179609218980194941195591504909210950881523864
48283120630877367300996091750197750389652106796057
63838406756827679221864261975616183809433847617047
05816458520363050428875758915410658086075523991239
30385521914333389668342420684974786564569494856176
03532632205807780565933102619270846031415025859286
41771167259436037184618573575983511523016459044036
97613233287231227125684710820209725157101726931323
46967854258065669793504599726835299863821552516638
94373355436021354332296046453184786049521481935558
53611059596230656

- Chạy thử 3: Shift 15 sang trái 1023 bit, dùng cơ số 16
./foo -b16 'F<<3FF'
78000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
0000000

Có thể thực hiện được hầu như tất cả các tính toán thông thường với expr thông qua giao diện là foo như trên. Các phép toán bao gồm (xếp theo thứ tự ưu tiên giảm dần từ trên xuống dưới):
        Operators      Precedence
         **              220
         ~ ! - (unary)   210
         * / %           200
         + -             190
         << >>           180
         <= < >= >       170
         == !=           160
         &               150
         ^               140
         |               130
         &&              120
         ||              110
         ? :             100/101

Các hàm sau cũng có thể được sử dụng:
Trích dẫn:
abs bin clrbit cmp cmpabs congruent_p divisible_p even_p fib fac
gcd hamdist invert jacobi kronecker lcm lucnum max min nextprime
odd_p perfect_power_p perfect_square_p popcount powm
probab_prime_p root scan0 scan1 setbit sgn sqrt

Tham khảo thêm gmp-4.2.2/demos/expr/README để biết thêm chi tiết về expr

Hết.
Tell a friend
Votes:1 Average:10.00
Jump to the top
Prev
Giải quyết triệt để vấn đề tiếng Việt trong MySQL 		top of the category
Programming/Database

Danh sách lời bình

Xem thêm các lời bình khác...
Thảo luận mới
Giải trí - Cười
Copyright © 2005-2008 Nhatban.net. All Rights Reserved.