Как реализовать умножение больших чисел на Java?

Question

[Дмитрий]

Прохожу online курс, второй день бьюсь над заданием. Неудается пройти проверку, выдает ошибку: “Failed test #7. Time limit exceeded”. По заданию необходимо уложиться в 5 секунд. Подскажите, как ускорить, или укажите на ошибки, если они имеются

Задание:

Реализуйте умножение двух чисел алгоритмом Карацубы, по длине не превышающих 100000. Выведите их произведение.

Мой код

import java.math.*;
import java.io.*;
class prog{
	public static void main(String[] args) throws Exception {					
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger A = new BigInteger(br.readLine().trim());
        BigInteger B = new BigInteger(br.readLine().trim());                
		System.out.printf((kara(A, B)).toString());
	}	
	public static BigInteger kara(BigInteger x, BigInteger y) {
		int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) return x.multiply(y);
        N = (N / 2) + (N % 2);
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));
        BigInteger ac = kara(a, c);
        BigInteger bd = kara(b, d);
        BigInteger abcd = kara(a.add(b), c.add(d));
        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
		}
	}

UPD: можно ли как-то быстрее вывести BigInteger на экран, без конвертации в строку?

Answer 1

[Дмитрий]

Решение все еще не найдо, идей больше нет...

Comments

[Дмитрий]

Решено, все упиралось в вывод большого числа на экран, реализовав свой медот преобразования числа в строку, удалось уложиться в заданное время.

Answer 2

[Андрей Вершинин]

До того, как настанет необходимость выхода из рекурсии, работайте с этими большими числами как со строками. Как только понадобится числовое значение - только тогда конвертируйте.

Comments

[Дмитрий]

Через строки тоже пробовал, также превышение времени.

[Андрей Вершинин]

@souris_rus Попробуйте поменять значение 2000 в условии выхода из рекурсии. Поставьте меньшее значение, может быть там и есть горлышко.

[Дмитрий]

@WolfdalE как уменьшал, так и увеличивал. В комментариях к курсу все грешат на вывод. Как по другому вывести - без понятия. Выводил и через println, и преобразовывая в строку.

[Андрей Вершинин]

@souris_rus А вы его проверяли без лимита времени?