CODEWITHSUNDEEP
javanumberscomparebiginteger
Omar
Omar

Reputation: 31

Most run time efficient way to compare two very large numbers (bigger than long)

I want to compare two very large numbers.

My current method works, but it takes longer than 2000 ms on some inputs.

My code:

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();
        }
    }
}

Please advise on how I can accurately compare large numbers without excessive run time.

Upvotes: 3

Views: 506

Answers (2)

Arjya Dutta
Arjya Dutta

Reputation: 1

You can digest the numbers using sha256 and compare. It will take a constant time however big the number is. Remember there may be collisions but chances are very low.

Upvotes: 0

k5_
k5_

Reputation: 5568

1.) You are doing the compareTo twice; store the result in a variable and reuse it. (Dont compare to 1/-1 compare to >0 and <0

There are some things/optimization directly on the Strings, but you need to be careful as these can lead to wrong answers with some Number formats. In my opinion it is best to be safe and stick to BigInteger.

2.) if you have only positive numbers and not ones that have 0 prefixes; you can do a check on the String.length the longer string contains the bigger number.

3.) On same length Strings you can do a String.compareTo() bypassing BigInteger altogether.

Upvotes: 3

Related Questions