Курсова - аритметични мулти-битови числа

въведение
В продължение на много приложения, предлагани от процесора на основните типове е достатъчно. Въпреки това, има много проблеми, изходните данни, които са твърде големи. Брой 1000 номера няма да се поберат в никакъв случай. Ето защо, представителството компютър от числа и операции, необходими за прилагането им на техните собствени.
По този начин по време на работа външен алгоритъм използване на такива номера, е много зависи от ефективността на тяхното изпълнение. Например, ако прогнозата на времето, определена O (N2) умножения, използвайки за тази операция е два пъти по-бърз алгоритъм дава
ускоряване на 4 пъти. Ето защо, ние ще, може би, най-сериозният интерес не само в правото, но може би по-ефективни алгоритми, които могат да бъдат приложени на прилично ниво, ако е необходимо.

BYSTROE_UMNOZHENIE
Тръгнахме да пиша, не само как размножаването на дълги числа, но също така и за да се установи как да го направи по-бързо.
Съставете умножение алгоритъм:
1. Намерете най-малкият брой Лен - степен на две: Лен. A.Size + B.Size. За тези номера Len = 8.
2. Допълване А и Б нули до незначителна Лен. И този пример А = (3,4,0,0,0,0,0,0), В = (5,4,3,2,1,0,0,0).
3. Изчислете недвижими FFT вектори на двата масива от числа.
4. скаларни умножава вектора трансформира, като се получи вектор Len размер.
5. Нанесете обратна трансформация на Фурие, в резултат на което е намотка.
6. Convert спираловидност в масив от цели числа, да прави трансфери.
голям брой цифри, се съхраняват в число формат. Ето защо, FFT трябва да ги копирате във временен масив от числа с плаваща запетая. Ако имате намерение да се получи в резултат на максимална дължина N, е необходимо да се разпределят памет за тях минимален размер
MaxLen = 2k, където MaxLen - минимална мощност на две, голям N. Например, ако максималната мощност ще се състои от 1000 БАЗА цифри от основата, минималната паметта MaxLen = 1024, тъй като тя е такава дължина на FFT се изчислява.
недвижими * LongNum1 = NULL, * LongNum2 = NULL;
// Инициализация може да се направи само един път в програмата.
нищожен FastMulInit (ulong Len) <
ulong MaxLen;
ако ((Len -Len) == Len) // Len = мощност на две
MaxLen = Len;
още MaxLen = 2; // така че 2MaxLen. Лен
направи MaxLen * = 2; докато (MaxLen >
LongNum1 = нов реално [MaxLen];
LongNum2 = нов реално [MaxLen];
>
// deinitialization
анулира FastMulDeInit () <
изтриване LongNum1;
изтриване LongNum2;
>
Описание на функцията на съответната секция RealFFT () преобразува "ин ситу", връщане на резултат вектор в пресована форма.
Съответно, предназначение на вътрешния продукт трябва да обмисли този формат.
// скаларна умножение на комплексни вектори в компресиран вид: LongNum1 = LongNum1 * LongNum2
анулира RealFFTScalar (истинско * LongNum1, Конст недвижими * LongNum2, ulong Len) <
Комплекс * CF1 = (комплекс *) LongNum1;
конст * Комплекс CF2 = (комплекс *) LongNum2;
// първите два елемента - групирани в една интегрирана реални числа
LongNum1 [0] = LongNum1 [0] * LongNum2 [0];
LongNum1 [1] = LongNum1 [1] * LongNum2 [1];
за (ulong х = 1 х CF1 [X] = CF1 [X] * CF2 [х]; // трябва да бъде след DFT
>
Нека да направим един по-подробен анализ на последната стъпка.
Всички изчисления са в брой с плаваща запетая, се използват ирационални числа, така че резултатът не е набор от числа, а по-скоро приближение към нея. За всяка извивка координират отговор на закръгли до най-близкото цяло число.
на [0] на [N / 2] [1] [2] .... на [N / 2-1]
б [0] б [N / 2] б [1] б [2] .... б [N / 2-1]
Проблемът се състои в това, че ако точността на изчисление не е достатъчно висока, а след това не може да се случи закръгляване към този номер. В резултат на това, алгоритъмът приключи успешно, но отговорът е неправилно.
Част от въпросите, свързани с точност, е решен в обсъждането на FFT. Въпреки това, дори и с абсолютно точни грешки тригонометрични изчисление ще се натрупват, като аритметични операции не могат да бъдат извършени с абсолютна точност. Затова се използва типа на данните трябва да бъде достатъчно голям, за размер на грешка на всеки етикет е по-малко от 0,5.
Например, когато се използва размер на тип 1 данни, фракцията 1/3 е представена като 0.3. При добавяне на три фракции се
1/3 + 1/3 + 1/3 = (брой на плаваща запетая формат) 0.3 + 0.3 + 0.3 = 0.9
Ако същия размер - две цифри, след това 1/3 = 0.33,
1/3 + 1/3 + 1/3 = 0,33 + 0,33 + 0,33 = 0,99. изчислителна точност значително увеличен.
Най-общо казано, два начина за увеличаване на точността. Един от тях е свързано с увеличаване на вида на дължина: От поплавък за двойно, допълнително към дълго двойно, а след това с двойно double2 ...
Друг подход е по-гъвкав. Това предполага фиксиран тип да се намали дължината на базовата основа. По този начин, той ще се задържи по-дълго, ще отнеме повече памет, но поради тази повишена точност.
FFT умножение Ограничения
Интересен оценка за грешки даде Колин Пърсивал.
Да предположим, че искате да се размножават векторите от 2n координатна система чрез FFT вектори с реални координати. След това, от резултатите, че грешката ERR размножават х от Y е ограничена по-горе чрез експресията
заблуждавам <2n BASE2 ( .*3n +. 5 (3n+4) + .(3n+3) ) (2)
къде. - Освен / умножение точност. - точността на тригонометрични изчисления,
Следователно, за дадено. не е трудно да се намери възможно най-малката основа база.
Например, когато се използва тип двойно (53 бита). = 2-53. Грешки, обградени с тригонометрия. =. / 2.
Ние очакваме, горна граница грешка (2) номер. Приблизително обмислят константи получат 2n BASE2 2-53 (11.83 п + 11,07) <.
За номера с дължина 220, който води до базата от неравенството <4100. Такова оценка худшего случая, обоснованная математически.
На практика, обаче, е добър избор би бил BASE = 10000. FFT умножение в тази база може да работи дори и за много големи числа. Въпреки това, той няма да се гарантира правилното математически резултат.
Когато се закръглява трябва да бъде да разгледаме разликата между стойността и закръгляване на резултата закръгляване. Ако тя е по-малко от 0,2, а след това умножението е вероятно да се получи правилния резултат, ако повече - това се препоръчва да се намали базовата или използвайте друг тип база за съхранение на коефициенти.
След стъпка 5 не е завършен продукт, но само една гънка на мозъка - резултат без сричкопренасяне. Както беше споменато, когато се обмисля увеличаване на броя на пирамидата, стойностите на коефициентите на намотка може да бъде много по-земята, достигайки 2 N * BASE2. Ако допълнително припомни, че обратната трансформация на Фурие е резултат на разделянето на функцията RealFFT () върху максималните номера N. размер става равна на 2N2 * BASE2, така че трябва да се внимава да не преливане настъпили. По-специално, той не трябва да бъде обявена за BASE повече от 4 цифри след десетичната запетая.
Последните два вида подкрепа, не всички процесори

Като обобщение на по-горе, ние отбелязваме, че проблемите са само три:
1. Точност на тригонометрията
2. Точността на изчисляване на FFT
3. преливане база тип.
Първият проблем е решен в обсъждането на FFT. Вторият и третият се решават чрез намаляване BASE, всяко увеличение на база тип. Ефективността на алгоритъма намалява малка база означава удължаване на броя на цифри, и по-голямата основа на вида не винаги е налице.
Следната функция преобразува намотка Конволюция Len дължина на голям брой С, като закръгляването и мигрират. В края на една променлива MaxError ще съдържа максималната грешка закръгляване.
RealFFT () не произвежда нормализиране на резултата, така че трябва да се направи тук.
недвижими MaxError;
анулира CarryNormalize (истинско * Конволюция, ulong Лен, BIGINT C) <
реално инв = 1,0 / (Len / 2); // нормализиране фактор
// DFT извършва върху "комплекс" вектор
// 2 пъти по-малка дължина
недвижими RawPyramid, пирамида, PyramidError, Кери = 0;
кратко * C = C.Coef;
ulong X;
// В C постави част от резултата, който е да се получи добре
// DFT има дължина на 2k, но вектора на коефициентите
// инициализация може да бъде по-малък брой елементи от мощност от 2.
ако (Len> C.SizeMax) Len = C.SizeMax;
MaxError = 0;
за (х = 0 х RawPyramid = Конволюция [X] * инв + носене;
// Добавяме 0,5 закръгляване до най-близката цяла случи
Пирамида = етаж (RawPyramid + 0,5);
PyramidError = фабрики (RawPyramid - пирамида);
ако (PyramidError> MaxError)
MaxError = PyramidError;
Извършва = етаж (Pyramid / BASE); // изчисли трансфери
в [X] = (къса) (пирамида - Извършва * база);
>
// Всичко е готово, остава само да се определи количеството С, в първия
// ненулев коефициент.
правя докато (в [х] == 0);
C.Size = х + 1;
>
Сега е възможно да се приложи алгоритъма в своята цялост.
// Изчисли С = А * В, управлява FastMul повикване (А, В, А)
нищожен FastMul (Конст BIGINT А, Конст BIGINT B, BIGINT C) <
ulong X;
конст кратко * а = A.Coef, * б = B.Coef;
ако грешка ( "не FastMul initalized.") (LongNum1 || LongNum2 !!);
// Етап 1
ulong Len = 2;
докато (Len ако (Len <8 ) Len = 8; // FFT работает

// Етап 2. Препишете цифрите в временно масив, и е подплатена с нули
// в обратен ред на цифри, така нули ще бъде в края
за (х = 0 х и т.н.