Số học với số nguyên lớn tự do trong PHP

Question

Ok, vì vậy PHP không phải là ngôn ngữ tốt nhất để xử lý các số nguyên lớn tùy ý, xem xét nó chỉ hỗ trợ các số nguyên đã ký 32 bit. Những gì tôi đang cố gắng làm là tạo ra một lớp có thể đại diện cho một số nhị phân lớn tùy ý và có thể thực hiện các phép tính số học đơn giản trên hai trong số chúng (cộng/trừ/nhân/chia).

Mục tiêu của tôi là xử lý các số nguyên 128 bit.

Có một vài cách tiếp cận mà tôi đang xem và các vấn đề tôi thấy với chúng. Bất kỳ đầu vào hoặc bình luận về những gì bạn sẽ chọn và làm thế nào bạn có thể đi về nó sẽ được đánh giá rất nhiều.

Cách tiếp cận # 1: Tạo lớp nguyên 128 bit lưu trữ số nguyên nội bộ dưới dạng bốn số nguyên 32 bit. Vấn đề duy nhất với cách tiếp cận này là tôi không chắc chắn làm thế nào để đi về xử lý các vấn đề tràn/tràn khi thao tác từng phần của hai toán hạng.

Phương pháp tiếp cận # 2: Sử dụng phần mở rộng bcmath, vì nó trông giống như thứ gì đó được thiết kế để giải quyết. Nỗi lo duy nhất của tôi khi sử dụng phương pháp này là thiết lập tỷ lệ của phần mở rộng bcmath, vì không thể có bất kỳ lỗi làm tròn nào trong các số nguyên 128 bit của tôi; chúng phải chính xác. Tôi cũng lo lắng về việc có thể cuối cùng chuyển đổi kết quả của các chức năng bcmath thành một chuỗi nhị phân (mà sau này tôi sẽ cần phải xô vào một số chức năng mã hóa mcrypt).

Cách tiếp cận # 3: Lưu các số dưới dạng chuỗi nhị phân (có thể là LSB trước). Về mặt lý thuyết, tôi có thể lưu trữ các số nguyên của bất kỳ kích thước tùy ý theo cách này. Tất cả những gì tôi phải làm là viết bốn hàm số học cơ bản để thực hiện thêm/sub/mult/div trên hai chuỗi nhị phân và tạo ra một kết quả chuỗi nhị phân. Đây chính xác là định dạng mà tôi cần phải chuyển giao cho mcrypt, vì vậy đó là một cộng thêm. Đây là cách tiếp cận mà tôi nghĩ có lời hứa nhất vào lúc này, nhưng điểm gắn bó tôi nhận được là PHP không cung cấp cho tôi bất kỳ cách nào để thao tác các bit riêng lẻ (mà tôi biết). Tôi tin rằng tôi sẽ phải chia nó thành các khối có kích thước bằng byte (không có ý định chơi chữ), tại thời điểm đó các câu hỏi của tôi về xử lý tràn/tràn từ Phương pháp tiếp cận # 1 được áp dụng.

Answer 1

Các PHP GMP extension sẽ tốt hơn cho việc này. Là một tiền thưởng thêm, bạn có thể sử dụng nó để làm bạn chuyển đổi số thập phân sang nhị phân, như vậy:

gmp_strval(gmp_init($n, 10), 2); 

Answer 2

Đã có một số khác nhau classesavailable vì vậy bạn có thể muốn xem chúng trước khi viết giải pháp của riêng bạn (nếu thực sự viết giải pháp của riêng bạn vẫn là cần thiết).

Answer 3

Theo như tôi có thể biết, tiện ích mở rộng bcmath là tiện ích bạn sẽ muốn. Dữ liệu trong hướng dẫn sử dụng PHP hơi thưa thớt, nhưng bạn có thể thiết lập độ chính xác để chính xác những gì bạn cần bằng cách sử dụng hàm bcscale() hoặc tham số thứ ba tùy chọn trong hầu hết các hàm bcmath khác. Không quá chắc chắn về điều chuỗi nhị phân, nhưng một chút googling cho tôi biết bạn nên có thể làm bằng cách sử dụng hàm pack().

Answer 4

tôi thực hiện các PEMDAS complaint BC evaluator sau đó có thể hữu ích cho bạn.

function BC($string, $precision = 32) 
{ 
    if (extension_loaded('bcmath') === true) 
    { 
     if (is_array($string) === true) 
     { 
      if ((count($string = array_slice($string, 1)) == 3) && (bcscale($precision) === true)) 
      { 
       $callback = array('^' => 'pow', '*' => 'mul', '/' => 'div', '%' => 'mod', '+' => 'add', '-' => 'sub'); 

       if (array_key_exists($operator = current(array_splice($string, 1, 1)), $callback) === true) 
       { 
        $x = 1; 
        $result = @call_user_func_array('bc' . $callback[$operator], $string); 

        if ((strcmp('^', $operator) === 0) && (($i = fmod(array_pop($string), 1)) > 0)) 
        { 
         $y = BC(sprintf('((%1$s * %2$s^(1 - %3$s))/%3$s) - (%2$s/%3$s) + %2$s', $string = array_shift($string), $x, $i = pow($i, -1))); 

         do 
         { 
          $x = $y; 
          $y = BC(sprintf('((%1$s * %2$s^(1 - %3$s))/%3$s) - (%2$s/%3$s) + %2$s', $string, $x, $i)); 
         } 

         while (BC(sprintf('%s > %s', $x, $y))); 
        } 

        if (strpos($result = bcmul($x, $result), '.') !== false) 
        { 
         $result = rtrim(rtrim($result, '0'), '.'); 

         if (preg_match(sprintf('~[.][9]{%u}$~', $precision), $result) > 0) 
         { 
          $result = bcadd($result, (strncmp('-', $result, 1) === 0) ? -1 : 1, 0); 
         } 

         else if (preg_match(sprintf('~[.][0]{%u}[1]$~', $precision - 1), $result) > 0) 
         { 
          $result = bcmul($result, 1, 0); 
         } 
        } 

        return $result; 
       } 

       return intval(version_compare(call_user_func_array('bccomp', $string), 0, $operator)); 
      } 

      $string = array_shift($string); 
     } 

     $string = str_replace(' ', '', str_ireplace('e', ' * 10^', $string)); 

     while (preg_match('~[(]([^()]++)[)]~', $string) > 0) 
     { 
      $string = preg_replace_callback('~[(]([^()]++)[)]~', __FUNCTION__, $string); 
     } 

     foreach (array('\^', '[\*/%]', '[\+-]', '[<>]=?|={1,2}') as $operator) 
     { 
      while (preg_match(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), $string) > 0) 
      { 
       $string = preg_replace_callback(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), __FUNCTION__, $string, 1); 
      } 
     } 
    } 

    return (preg_match('~^[+-]?[0-9]++(?:[.][0-9]++)?$~', $string) > 0) ? $string : false; 
} 

Tự động xử lý lỗi làm tròn, chỉ cần đặt độ chính xác thành bất kỳ chữ số nào bạn cần.