câu hỏi java.math.BigInteger pow (số mũ)

Question

Tôi đã thực hiện một số thử nghiệm về phương pháp pow (số mũ). Thật không may, kỹ năng toán học của tôi không đủ mạnh để xử lý vấn đề sau.

Tôi đang sử dụng mã này:

BigInteger.valueOf(2).pow(var); 

Kết quả:

• var | thời gian trong ms
• 2000000 |
• 2500000 |
• 3000000 | 22379
• 3500000 | 32147
• 4000000 |
• 4500000 |
• 5000000 | 49922

See? 2.500.000 số mũ được tính toán gần như nhanh chóng là 2.000.000. 4.500.000 được tính toán nhanh hơn nhiều, sau đó là 4.000.000.

Tại sao lại như vậy?

Để cung cấp cho bạn một số giúp đỡ, đây là việc thực hiện ban đầu của BigInteger.pow (mũ):

public BigInteger pow(int exponent) { 
    if (exponent < 0) 
     throw new ArithmeticException("Negative exponent"); 
    if (signum==0) 
     return (exponent==0 ? ONE : this); 

    // Perform exponentiation using repeated squaring trick 
     int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 
    int[] baseToPow2 = this.mag; 
     int[] result = {1}; 

    while (exponent != 0) { 
     if ((exponent & 1)==1) { 
     result = multiplyToLen(result, result.length, 
             baseToPow2, baseToPow2.length, null); 
     result = trustedStripLeadingZeroInts(result); 
     } 
     if ((exponent >>>= 1) != 0) { 
       baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); 
     baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); 
     } 
    } 
    return new BigInteger(result, newSign); 
    } 

Answer 1

Thuật toán sử dụng lặp lại bình phương (squareToLen) và nhân (multiplyToLen).Thời gian cho các hoạt động này chạy phụ thuộc vào kích thước của các con số có liên quan. Các phép nhân của các số lớn gần cuối của phép tính sẽ đắt hơn nhiều so với số đầu tiên.

Phép nhân chỉ được thực hiện khi điều kiện này là đúng: ((exponent & 1)==1). Số hoạt động vuông phụ thuộc vào số bit trong số (trừ số 0 đứng đầu), nhưng phép nhân chỉ được yêu cầu cho các bit được đặt thành 1. Dễ dàng hơn để xem các thao tác được yêu cầu bằng cách xem nhị phân đại diện của số:

 
2000000: 0000111101000010010000000 
2500000: 0001001100010010110100000 
3000000: 0001011011100011011000000 
3500000: 0001101010110011111100000 
4000000: 0001111010000100100000000 
4500000: 0010001001010101000100000 
5000000: 0010011000100101101000000 

Lưu ý rằng 2.5M và 4.5M may mắn khi chúng có ít bit cao hơn số xung quanh. Lần sau, điều này xảy ra là 8.5m:

 
8000000: 0011110100001001000000000 
8500000: 0100000011011001100100000 
9000000: 0100010010101010001000000 

các điểm ngọt là quyền hạn chính xác của 2.

 
1048575: 0001111111111111111111111 // 16408 ms 
1048576: 0010000000000000000000000 // 6209 ms 

Answer 2

Chỉ cần một đoán:

số mũ được xử lý từng chút một, và nếu ít nhất có ý nghĩa bit là 1 công việc bổ sung được thực hiện.

Nếu L là số bit trong số mũ và A số bit mà là 1 và t1 thời gian để xử lý phần chung và t2 việc xử lý thời gian bổ sung khi các LSbit là 1

sau đó thời gian chạy sẽ

L t1 + A t2

hoặc thời gian phụ thuộc vào số 1 trong biểu diễn nhị phân.

hiện đang viết một chương trình nhỏ để xác minh lý thuyết của tôi ...

Answer 3

Tôi không biết bạn đã chạy bao nhiêu lần. Như một số người bình luận đã chỉ ra, bạn cần thời gian hoạt động nhiều, nhiều lần để có được kết quả tốt (và họ vẫn có thể sai).

Giả sử bạn đã hẹn giờ tốt, hãy nhớ rằng có rất nhiều phím tắt có thể được thực hiện trong toán học. Bạn không phải thực hiện các thao tác 5 * 5 * 5 * 5 * 5 * 5 để tính toán 5^6.

Đây là một cách để thực hiện nhanh hơn rất nhiều. http://en.wikipedia.org/wiki/Exponentiation_by_squaring