比较两个非常大的数字（大于长）的最有效的运行时间方法

Question

我想比较两个非常大的数字。

我当前的方法有效，但某些输入需要超过 2000 毫秒。

我的代码：

import java.io.*;
import java.math.*;
import static java.lang.Math.pow;

public class comparelarge {
    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(isr);
        PrintWriter out = new PrintWriter(System.out);

        String first = bf.readLine();
        String second = bf.readLine();
        BigInteger big1 = new BigInteger(first);
        BigInteger big2 = new BigInteger(second);

        if(big1.compareTo(big2) == 1){
            out.println('>');
            out.flush();
        }
        else if(big1.compareTo(big2) == -1){
            out.println('<');
            out.flush();
        }
        else{
            out.println('=');
            out.flush();
        }
    }
}

请告知我如何在不花费过多运行时间的情况下准确地比较大量数字。

Answer 1

1.) 您正在执行

compareTo

两次；将结果存储在变量中并重用它。 （不要与

1/-1

比较，与

>0

和

<0

比较）

有一些东西/优化直接在字符串上，但你需要小心，因为这些可能会导致某些数字格式的错误答案。在我看来，最好是安全并坚持

BigInteger

。

2.) 如果您只有正数而没有带有

0

前缀的数字；您可以检查

String.length

较长的字符串包含较大的数字。

3.）在相同长度的字符串上，您可以完全绕过

BigInteger

进行 String.compareTo() 。

Answer 2

您可以使用 sha256 消化这些数字并进行比较。无论数字有多大，都需要恒定的时间。请记住，可能会发生碰撞，但几率非常低。