Số mũ lũy thừa trong OCaml

Question

Có hàm số mũ lũy thừa số nguyên trong OCaml không? ** chỉ dành cho phao. Mặc dù nó có vẻ là chủ yếu là chính xác, không phải là có một khả năng lỗi chính xác, một cái gì đó giống như 2. ** 3. = 8. trở về sai đôi khi? Có chức năng thư viện cho lũy thừa số nguyên không? Tôi có thể viết của riêng tôi, nhưng mối quan tâm hiệu quả đi vào đó, và tôi cũng sẽ ngạc nhiên nếu không có một chức năng như vậy.

Answer 1

Về phần dấu chấm động của câu hỏi của bạn: OCaml gọi hàm pow() của hệ thống nằm bên dưới. Điểm lũy thừa dấu chấm là một hàm khó thực hiện, nhưng nó chỉ cần trung thành (có nghĩa là chính xác đến một Unit in the Last Place) để làm cho 2. ** 3. = 8. đánh giá là true, vì 8.0 là chỉtrong một ULP của kết quả toán học chính xác 8.

Tất cả thư viện toán học nên (*) trung thành, vì vậy bạn không cần phải lo lắng về ví dụ cụ thể này. Nhưng not all of them actually are, vì vậy bạn có quyền lo lắng.

---

Một lý do tốt hơn để lo lắng sẽ là, nếu bạn đang sử dụng 63-bit số nguyên hoặc rộng hơn, rằng các đối số hoặc kết quả của các lũy thừa không thể được đại diện chính xác như OCaml nổi (trên thực tế IEEE 754 số tăng gấp đôi độ chính xác không thể đại diện cho 9_007_199_254_740_993 hoặc 2 + 1). Trong trường hợp này, lũy thừa dấu phẩy động là một thay thế xấu cho lũy thừa số nguyên, không phải vì một điểm yếu trong việc triển khai cụ thể, mà bởi vì nó không được thiết kế để biểu diễn chính xác các số nguyên lớn.

---

(*) Một tham khảo thú vị khác để đọc về chủ đề này là “A Logarithm Too Clever by Half” của William Kahan.

Answer 2

Không có trong thư viện chuẩn. Nhưng bạn có thể dễ dàng tự viết một mình (sử dụng exponentiation by squaring để nhanh) hoặc sử dụng lại thư viện mở rộng cung cấp. Trong Batteries, nó là Int.pow.

Dưới đây là một việc thực hiện đề xuất:

let rec pow a = function 
    | 0 -> 1 
    | 1 -> a 
    | n -> 
    let b = pow a (n/2) in 
    b * b * (if n mod 2 = 0 then 1 else a) 

Nếu có một nguy cơ tràn vì bạn đang thao tác với số lượng rất lớn, có lẽ bạn nên sử dụng một thư viện lớn nguyên như Zarith, cung cấp tất cả các loại của hàm mũ.

(Bạn có thể cần những "lũy thừa modulo", tính toán (a^n) mod p, điều này có thể được thực hiện trong một cách mà tránh tràn bằng cách áp dụng các mod trong tính toán trung gian, ví dụ trong hàm pow ở trên.)

Answer 3

Đây là một thực hiện trong đó sử dụng thuật toán bình phương và nhân (như một cung cấp bởi @gasche), nhưng điều này là đuôi-đệ quy

let is_even n = 
    n mod 2 = 0 

(* https://en.wikipedia.org/wiki/Exponentiation_by_squaring *) 
let pow base exponent = 
    if exponent < 0 then invalid_arg "exponent can not be negative" else 
    let rec aux accumulator base = function 
    | 0 -> accumulator 
    | 1 -> base * accumulator 
    | e when is_even e -> aux accumulator (base * base) (e/2) 
    | e -> aux (base * accumulator) (base * base) ((e - 1)/2) in 
    aux 1 base exponent