ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Iassenev                     2:5020/400     24 Apr 2003  13:39:02
 To : Alex Astafiev
 Subject : Re: Большие числа
 -------------------------------------------------------------------------------- 
 

 "Alex Astafiev" <Alex.Astafiev@p16.f228.n5000.z2.fidonet.org> wrote in
 message news:1051136801@p16.f228.n5000.z2.fidonet.ftn...
 
 > DI> для умножения можно
 >  DI> использовать быстрое преобразование Фурье (FFT) или другие алгоритмы
 >  DI> быстрого умножения со сложностью менее O(N^2).
 >
 > Как?
 
 Выравниваешь числа по количеству знаков, чтобы их количество было равно
 степени двойки, потом применяешь FFT, потом попарно перемножаем коэффициенты
 полученных многочленов (алгоритм используется для перемножения многочленов,
 поэтому для перемножения чисел мы просто рассматриваем их в какой-то 2^N-й
 системе исчисления, каждую цифру этого числа мы рассматриваем как
 коэффициент многочлена), потом применяем обратное преобразование Фурье и
 получаем результат за O(NlogN).
 
 Есть более простые методы (разбить каждое из чисел на два меньших X = X1 * A
 + X2, Y = Y1*B + Y2, потом перемножить используя меньшее количество
 умножений, а если получишиеся числа слишком большие, то рекурсивно применяем
 эту же операцию для них. Алгоритм имеет название, но я его не помню)
 
 Желаю удачи,
 Дмитрий Ясенев.
 --- ifmail v.2.15dev5
  * Origin: Unknown (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Большие числа   Dmitriy Iassenev   23 Apr 2003 15:25:20   Большие числа   Alex Astafiev   23 Apr 2003 21:25:31   Re: Большие числа   Dmitriy Iassenev   24 Apr 2003 13:39:02   Большие числа   Evgenij Masherov   24 Apr 2003 20:43:47