Перемножение длинных чисел

From

Илья Кантор (2:5020/175.2)

To

Vokin Andrei

Date

2002-11-10T12:26:29Z

Area

RU.ALGORITHMS

From: "Илья Кантор" <ilia@manual.ru>

Sun Nov 10 2002 11:38, Vokin Andrei wrote to All:

 VA> Существует ли алгоритм перемножения длинных чисел за O(n ^1.5)?
 VA> (Где n количество разрядов в числе.)

Для любого epsilon>0 существует алгоритм умножения сложностью O(n^{1+epsilon})

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)