Умножение и деление многочленов
Многочлен (полином) может быть представлен как вектор или одномерный массив. Например, у нас есть квадратный трёхчлен х*х + 5*х + 6 и можно хранить его в массиве (1,5,6). Степень данного полинома равна 2- это степень максимального слагаемого. Записываем по умолчанию от больших степеней к меньшим.
Ниже определено полиномиальное умножение- т.е. какой полином получится после умножения двух полиномов.
template <typename Type>
// элементы полинома будут разные, поэтому полином шаблонный- можно подставлять целые, вещественные, комплексные- что угодно- если для них определена операция умножения
Type *PolynomProd (Type p[], int pdeg, Type q[], int qdeg) {
int deg= pdeg+qdeg; // степень нового полинома
int psize= pdeg+1, qsize= qdeg+1, size= deg+1; // размеры массивов
Type *res= new Type[size]; // заготовка нового полинома
int ps= psize*qsize; // кол-во взаимных произведений
//
Type *prodmatrix= new Type [ps]; // массив из произведений элементов
int *powsum= new int [ps]; // массив из сумм номеров элементов- соответствует массиву произведений
// занесение значений в эти массивы
for (int k=0; k<ps; k++) {
prodmatrix[k]= p[k%psize] * q[k/psize];
powsum[k]= k%psize + k/psize;
}
// формирование нового полинома на основе этих вспомогательных массивов
for(int k=0; k<size; k++) {
res[k]= 0;
|
|
|
for(int i=0; i<ps; i++) if(k==powsum[i]) res[k]+= prodmatrix[i];
}
// возвращаем как раз наш полином
return res;
}
Ниже на картинках можно понять весь процесс лучше:
Теперь рассмотрим деление многочлена на двухчлен по схеме Горнера- это применяется при нахождении корней многочлена. Если мы например в кубическом уравнении подобрали что один корень равен например 3, то можно поделить этот кубур на x-3 и получить уже квадратное выражение- и искать уже корни в этом новом многочлене более низкой степени.
double *GornerDiv (double p[], int deg, double a=1) {
double *res= new double [deg];
res[0]= p[0];
for(int i=1; i<deg; i++) res[i]= p[i] + a*res[i-1];
return res;
}
// остаток- он равен нулю, если a- это корень многочлена
double GornerMod (double p[], int deg, double a=1) {
double *res= new double [deg+1];
res[0]= p[0];
for(int i=1; i<deg+1; i++) res[i]= p[i] + a*res[i-1];
return res[deg];
}
Мусическое умножение
Рассмотрим теперь реализацию кошических алгоритмов на примере мусического умножения на 2 и аналогичных.
Как вообще это происходит? Мы сначала разбиваем число на цифры- на массив цифр, естественно. Далее надо сформировать новое число- новый массив делаем, из которого потом это число соберём. Если первая цифра 5,6,7,8,9, то новый массив на единицу больше- т.е. при умножении на 2 разрядность числа вырастет.
|
|
|
Далее у нас есть соответствие- т.е. самих операций умножения, что интересно, тут вообще не будет- предположим что компьютер этого не умеет. И остальное тоже. У нас будут только соответствия- и всё.
Никаких операций сложения, умножения, больше-меньше- только одни соответствия. Этим алгоритм и будет интереснее и поэтому о нём и стоит тут упомянуть.
Благодаря такому вот преимуществу непривязки к плюсам-умножить и т.п, можно легко распространить его на работу в других системах счисления, а не только в привычной десятичной. Просто изменив некие параметры соответствия, можно и в восьмеричной, в пятеричной и т.п. системах легко делать всё то же самое.
Единственная загвоздка- разбиение на цифры- если человек и так легко определит, то компьютер только по десятичным логарифмам. Хотя есть вариант переведения числа в строку, подсчёт символов и на основе этого сделать понимание сколько там цифр, но пока заморачиваться не будем. Сделаем пока простой алгоритм, потом при желании можно будет его усовершенствовать в сторону большей непривязанности. Или сделать например чтобы можно было работать с бесконечными числами, чтобы нам не важно было знать количество цифр. Тем не менее, написание подобного алгоритма позволит лучше понять как вообще может происходить умножение на 2 и т.п. мелкие числа на глубинном уровне- это и изложено в моём старом рукописном труде "Кошика". И мусика- как раз-таки раздел, связанный с подобными умножениями.
|
|
|
Итак, в простом варианте алгоритм умножения на 2 выглядит так:
// проверка- является ли число больше 5- в таком случае меняется результат
bool half2 (int x) {
if ( (x==5) || (x==6) || (x==7) || (x==8) || (x==9) ) return true;
if ( (x==0) || (x==1) || (x==2) || (x==3) || (x==4) ) return false;
}
// сопоставление при умножении на 2 (если след.цифра больше 5, то +1 - но этого инкремента типа нет)
int digit2 (int cur, int next) {
if ( (cur==0) || (cur==5) ) {
if(half2(next)) return 1;
return 0;
}
if ( (cur==1) || (cur==6) ) {
if(half2(next)) return 3;
return 2;
}
if ( (cur==2) || (cur==7) ) {
if(half2(next)) return 5;
return 4;
}
if ( (cur==3) || (cur==8) ) {
if(half2(next)) return 7;
|
|
|
return 6;
}
if ( (cur==4) || (cur==9) ) {
if(half2(next)) return 9;
return 8;
}
}
// сама функция преобразования числа в удвоенное (поэтому в аргументе адрес)
void Kosh_x2 (int &x) {
int *X= NumberToDigits(x*10); // берём умноженное на 10 чтобы нолик ещё был в конце (т.к. он проверяется- чтобы не было выхода за границы массива)- да тут решили не заморачиваться с прямым обходом умножения- главное просто продемонстрировать алгоритм
int size= qq(x); // количество цифр в числе (эти функции приведу ниже позже)
if(half2(X[0])) size++;
int *X2= new int [size]; // массив цифр для удвоенного числа
if(half2(X[0])) {
X2[0]= 1; // первая цифра единичка
for (int i=0; i<qq(x); i++) X2[i+1]= digit2(X[i],X[i+1]); // следующие цифры
}
if(!half2(X[0])) {
for (int i=0; i<qq(x); i++) X2[i]= digit2(X[i],X[i+1]);
}
x= DigitsToNumber(X2,size);
}
Вот та же функция, но без использования умножения на 10: просто добавим дополнительную проверку в цикле прохода по цифрам, достигли ли последней цифры:
void Kosh_x2 (int &x) {
int *X= NumberToDigits(x);
int size= qq(x);
if(half2(X[0])) size++;
int *X2= new int [size];
if(half2(X[0])) {
X2[0]= 1;
for (int i=0; i<qq(x); i++) {
if(i==qq(x)-1) X2[i+1]= digit2(X[i],0);
else X2[i+1]= digit2(X[i],X[i+1]);
}
}
if(!half2(X[0])) {
for (int i=0; i<qq(x); i++) {
if(i==qq(x)-1) X2[i]= digit2(X[i],0);
else X2[i]= digit2(X[i],X[i+1]);
}
}
x= DigitsToNumber(X2,size);
}
Вот все вспомогательные функции, которые использовались:
#include <cmath>
int qq (int x) {
if (x<1) return 1;
else return log10(x)+1;
}
int qn (int x, int n) {
int dlg = pow(10, qq(x)+1-n);
int dlg1= pow(10, qq(x)-n);
return (x%dlg - x%dlg1) / dlg1;
}
int *NumberToDigits (int x) {
int *m= new int [qq(x)];
for(int i=0; i<qq(x); i++) m[i]= qn(x,i+1);
return m;
}
int DigitsToNumber (int m[], int size) {
int res=0;
for(int i=1; i<=size; i++) res+= m[i-1]*pow(10,size-i);
return res;
}
Тут уже используются продвинутые методы типа логарифма и степени- просто для упрощения. Но опять же, повторюсь, здесь нашей задачей просто было представить алгоритм самого умножения на 2- не зацикливаясь на том как оно там разбивалось на массив цифр и собиралось обратно. Важны нюансы самого этого алгоритма умножения на 2, в котором мы старались сделать всё более фундаментально и соответственно и более интересно.
...
Что касается умножения на 3, то тут будет гораздо сложнее- потому что нет определённости в следующей цифре- нужно смотреть след.цифра больше 66666 например- т.е. придётся анализировать всё оставшееся число. Это достаточно геморно. Поэтому можно либо всё-таки плюнуть на гемор и анализировать оставшееся (хоть алгоритм станет от этого более отвратным- неэффективным), либо пойти как это принято с конца и держать там сколько-то в уме и потом прибавлять. Прибавление на 1 и на 2 можно либо оставить, либо написать отдельные функции, либо как-то в допусловиях прописать. Но в мусическом умножении мы идём слева направо- при счёте на бумажке так нам, как человеку, бывает гораздо быстрее и удобнее т.к. не надо ничего держать в уме, но для программирования компьютера это будет гораздо более неэффективно.
...
Умножение на 5- это то же самое что деление на 2 по сути, т.к. умножить на 5 это поделить на 2 и потом умножить на 10 (изменить разряд). Тем не менее можно написать эту функцию по кошическим принципам тоже. Этот алгоритм будет сложнее умножения на 2, но тем не менее он не такой сложный как в случае с тройками и поэтому мы для полноты картины в качестве другого примера тоже его ниже представим:
// нечётная ли цифра
bool nchet (int x) {
if ( (x==1) || (x==3) || (x==5) || (x==7) || (x==9) ) return true;
if ( (x==0) || (x==2) || (x==4) || (x==6) || (x==8) ) return false;
}
// сопоставление (анализируем также предыдущую цифру на чётность)
int digit5 (int cur, int pred) {
if ( (cur==0) || (cur==1) ) {
if(nchet(pred)) return 5;
return 0;
}
if ( (cur==2) || (cur==3) ) {
if(nchet(pred)) return 6;
return 1;
}
if ( (cur==4) || (cur==5) ) {
if(nchet(pred)) return 7;
return 2;
}
if ( (cur==6) || (cur==7) ) {
if(nchet(pred)) return 8;
return 3;
}
if ( (cur==8) || (cur==9) ) {
if(nchet(pred)) return 9;
return 4;
}
}
// сам преобразователь числа в умноженное на 5 (или делённое на 2, если не учитывать разрядность)
void Kosh_x5 (int &x) {
int *X= NumberToDigits(x);
int size= qq(x);
if (X[0]!=1) size++;
int *X5= new int [size];
if(X[0]!=1) {
for(int i=0; i<qq(x); i++) {
if(i==0) X5[i]= digit5(X[i],0);
else X5[i]= digit5(X[i],X[i-1]);
}
if (nchet(X[qq(x)-1])) X5[qq(x)]= 5;
else X5[qq(x)]= 0;
}
if(X[0]==1) {
for(int i=1; i<qq(x); i++) X5[i-1]= digit5(X[i],X[i-1]);
if (nchet(X[qq(x)-1])) X5[qq(x)-1]= 5;
else X5[qq(x)]= 0;
}
x= DigitsToNumber(X5,size);
}
Обнаружилась проблема, связанная как раз-таки с использованием типа int- он вмещает в себя только числа до 2 млрд. Можно использовать long long int, будут помещаться более крупные цифры- но всё равно этот предел вместимости ограничен. Поэтому для представления огроменных великоразрядных чисел нужна совсем другая парадигма- очевидно что остаётся хранить число как массив цифр. Но это мы уже рассмотрим в следующих главах, не здесь.
Деление и периоды
Здесь же мы рассмотрим как можно запрограммировать деление и по сути попробуем эту реализацию чисел как массив цифр чтобы мы могли записывать длиннющие числа либо как периоды, либо как просто большие числа.
Деление можно производить несколькими алгоритмами. Самый известный и очевидный это стандартным столбиком- он хорош своей универсальностью. Но также рассмотрим ещё более сложный, но при этом крутой и интересный по-своему алгоритм нахождения периодов- по рыждвижному свойству.
Сначала нужно понять как нам в массиве цифр хранить число. Мы будем получать на вход 2 числа, которые нам нужно поделить- они, как правило, маленькие- и поэтому мы легко будем хранить их в интах (типа int). Выделим целую часть, напишем точку и далее уже идёт самое интересное- дробная часть и нахождение периода.
Для того чтобы понимать массив из скольки цифр составлять, будем указывать точность- т.е. сколько нам надо знаков после запятой.
Ниже представлен алгоритм деления столбиком- точнее, это функция которая возвращает массив цифр дробной части. И также напишем отдельную функцию для вывода этого числа в консоль.
Мы будем делить только меньшее число на большее пока что- т.е. заносится чисто дробная часть:
// k:n divide
int *Kosh_Div (int k, int n, int r= 20) {
int *res= new int [r];
int ost= k;
for(int i=0; i<r; i++) {
res[i]= ost*10/n;
ost= (ost*10)%n;
}
return res;
}
// вывод всей этой мешанины цифр в единую массу
void Kosh_Print (int a[], int r= 20) {
for (int i=0; i<r; i++) cout << a[i];
}
Под параметром r у нас задана точность- по умолчанию равна 20. Можно и поменять.
Вот функция, которая выводит деление уже 2 произвольных чисел- т.е. целое и дробное вместе:
void Kosh_Div_Full (int k, int n, int r= 20) {
cout << k/n;
if(k%n) {
cout << ".";
k%= n;
Kosh_Print(Kosh_Div(k,n,r),r);
}
}
...
Вот и всё. Теперь посмотрим алгоритм нахождения периода дроби по рыждвижному свойству- он сложный, но зато интересный.
Можно заметить, что:
1/99= 0.01010101...
1/98= 0.01020408...
1/97= 0.01030927...
И т.д. Эту закономерность можно использовать. Работает она вообще для любых чисел, а не только близким к 99, 98 и т.п- но понятно что для девяток работает гораздо лучше.
Тут нам понадобится опять размер числа выяснять и все такие дела. И при этом учитывать разрядное наложение. Будем действовать последовательным итерационным методом:
void Kosh_RDS (int n, int r= 20) {
int block= qq(n);
int t= pow(10,block) - n;
int *base= new int [r];
for (int i=0; i<r; i++) base[i]= pow(t,i);
for (int i=0; i<r; i++) {
for (int j=i; j>=0; j--) {
if( qq(base[j])>block ) {
base[j-1]+= (base[j]/(int)pow(10,block));
base[j] %= (int)pow(10,block);
}
}
}
for (int i=0; i<r; i++) {
if(i) for( int j=1; j<= ( block-qq(base[i]) ); j++ ) cout << 0;
cout << base[i];
}
}
Недостаток этого метода в том, что когда значение base какого-то элемента превышает 2 млрд, начинают искажаться данные и выводиться адреса- степени становятся слишком большие. Поэтому этот метод годится только для начальных чисел периода- вообще он используется при ручном подборе, а для компьютера очень неэффективен. Потому что когда степени становятся слишком большие, уже используются другие методы. Например, подбор коэфа и новый высчет на калькуляторе. Для компьютера же самый эффективный это всё же метод столбиком- вручную он наоборот часто не очень эффективен и удобен, поэтому и придумываются другие вещи типа РДС и подбора коэфа. Впрочем, здесь мы об этом подробный разговор вести не будем.
Работа с большими числами
Деление мы рассмотрели- теперь посмотрим умножение и вообще как можно работать с большими числами- когда они не помещаются в 1 байт памяти (или даже 2, 3, 4 байта- мы не хотим от этого ограниченного числа зависеть) и тогда приходится прибегать к хранению числа как массива цифр.
Если мы имеем дело с исходными большими числами, вводить их тоже придётся иначе- поциферно. Поэтому напишем и отдельную функцию для ввода числа. Чтобы вводить число непрерывно, будем переводить его как строку, а затем переводить в циферные данные.
Ввод числа:
int *Kosh_Input() {
string s; cin>>s;
int size= StringSize(s);
int *number= new int [size];
for(int i=0; i<size; i++) number[i]= CharToInt(s[i]);
return number;
}
Вспомогательные:
int CharToInt (char c) { return (int)c - (int)'0'; }
int StringSize (string s) {
char c= s[0]; int i=0; int stringsize=0;
while ((int)c != 0) { i++; c=s[i]; stringsize++; }
return stringsize;
}
Тут есть один недостаток- мы не знаем какой размер этого числа, т.е. сколько цифр в нём- и непонятно как выводить, как использовать. Поэтому можно написать ещё другую пару функций, где в массиве цифр хранятся помимо цифр ещё и количество этих цифр- в первый элемент засунуть. И вот они будут новые функции ввода и вывода:
int *Kosh_Input_New() {
string s; cin>>s;
int size= StringSize(s);
int *number= new int [size+1];
number[0]= size;
for(int i=1; i<=size; i++) number[i]= CharToInt(s[i-1]);
return number;
}
void Kosh_Print_New (int a[]) {
int r= a[0];
for (int i=1; i<=r; i++) cout << a[i];
}
Вот! Эти функции и способы хранения чисел уже более крутые и отлично работают. Переименуем их просто без приписки New, а к старым припишем Pure. Далее будем использовать уже эти новые принятые названия.
...
Будем теперь работать с этими новыми типами данных. Начнём с простого: сложение и вычитание. Тут есть один нюанс- разряды-то съезжают. Т.е. просто поциферно складывать не прокатит, нужно учитывать переходы. Будем складывать слева направо. И если сумма получается больше 10, то мы 10 вычтем. И при этом ещё нужно следующую сумму учитывать- если она больше 10, то прибавим единицу. Алгоритм поначалу кажется что похож на тот что был при мусическом умножении на 2, но только тут всё гораздо сложнее- размеры этих 2 слагаемых могут быть разные, возникают свои нюансы.
Сложение больших чисел можно разделить на следующие этапы:
1. Выравнивание- сделать эти 2 числа одинаковыми по-размеру, сдвинуть типа к правому концу. На пустые левые места поставить нули.
2. Выделение массива под суммарное число- понять какой размер этого суммарного массива.
3. Формирование суммарного числа из микросумм.
Для программирования гораздо эффективнее оказывается если производить сложение справа налево. Т.к. бывают ситуации типа 999+2, где неверно- нужно проверять всё до правого конца. Т.е. опять здесь ситуация такова что вручную считать проще слева направо (т.к. не надо ничего держать в уме, а ситуацию справа можно визуально быстро оценить и прикинуть), а для компьютера удобнее справа налево- тогда не нужно проверять огромные массивы цифр оставшихся для полной точности алгоритма. Всё-таки человеческий мозг может работать с неким другим восприятием что ли- он может быстро окинуть картину целиком и сделать вердикт. Компьютеру же надо проверять всё поступенчато, учитывать каждую даже редко встречающуюся мелочь.
// копирование числа
int *Kosh_Copy(int a[]) {
int *b= new int [a[0]+1];
b[0]= a[0];
for(int i=1; i<=a[0]; i++) b[i]=a[i];
return b;
}
// сама функция суммы
int *Kosh_Sum (int a[], int b[]) {
// ищем разрядность наибольшего числа
int n;
a[0]>b[0] ? n=a[0] : n=b[0];
// создаём новые выровненные числа-массивы
int *A= new int [n+1];
int *B= new int [n+1];
A[0]= n; B[0]= n;
// заполняем с учётом нулей
int d;
if(a[0]>b[0]) {
d= a[0]-b[0];
for(int i=1; i<=d; i++) B[i]= 0;
for(int i=d+1; i<=n; i++) B[i]= b[i-d];
for(int i=1; i<=n; i++) A[i]= a[i];
}
if(a[0]<b[0]) {
d= b[0]-a[0];
for(int i=1; i<=d; i++) A[i]= 0;
for(int i=d+1; i<=n; i++) A[i]= a[i-d];
for(int i=1; i<=n; i++) B[i]= b[i];
}
if(a[0]==b[0]) {
for(int i=1; i<=n; i++) A[i]= a[i];
for(int i=1; i<=n; i++) B[i]= b[i];
}
// определение разрядности суммы
int size= n;
int *_A= Kosh_Copy(A);
_A[0]= 0;
for(int i=n; i>=1; i--) if(_A[i] + B[i]>=10) _A[i-1]++;
if(_A[0]) size= n+1;
// создаём суммарное число (сложение справа налево)
int *C= new int [size+1];
C[0]= size;
bool inc= false; // метка учёта есть 1 в уме или нет
if(size==n) {
for(int i=n; i>=1; i--) {
C[i]= A[i] + B[i];
if(inc) {
C[i]++;
inc= false;
}
if(C[i]>=10) {
C[i]-=10;
inc= true;
}
}
}
if(size==(n+1)) {
C[1]= 1;
for(int i=n; i>=1; i--) {
C[i+1]= A[i] + B[i];
if(inc) {
C[i+1]++;
inc= false;
}
if(C[i+1]>=10) {
C[i+1]-=10;
inc= true;
}
}
}
return C;
}
Использовать данную прелесть можно так:
int *t1= Kosh_Input();
int *t2= Kosh_Input();
int *t= Kosh_Sum(t1,t2);
Kosh_Print(t);
...
Аналогично можно построить алгоритм вычитания- хотя здесь тоже придётся нехило погнуть мозг. Но после написания алгоритма сложения кажется уже попроще. Тут мы по умолчанию предполагаем, что уменьшаемое больше вычитаемого- т.е. работаем только на множестве положительных чисел и с нулём- без отрицательных.
Сначала мы выравниваем вычитаемое- забиваем недостающие цифры слева нулями и всё сдвигаем вправо. Далее обычное вычитание столбиком справа налево. И далее уже удаление лишних нулей в начале у разности.
int *Kosh_Subst (int a[], int b[]) {
int max= a[0], min= b[0], d= max-min;
int *B= new int [max+1];
B[0]= max;
for(int i=1; i<=d; i++) B[i]= 0;
for(int i=(d+1); i<=max; i++) B[i]= b[i-d];
int *A= Kosh_Copy(a);
//
int *C= new int [max+1];
C[0]= max;
bool razr= false;
for(int i=max; i>=1; i--) {
if(razr) {
A[i]--;
razr= false;
}
C[i]= A[i]-B[i];
if(C[i]<0) {
C[i]+= 10;
razr= true;
}
}
int nulls= 0;
for(int i=1; i<max; i++) {
if(!C[i]) nulls++;
else break;
}
int n= max-nulls;
int *c= new int [n+1];
c[0]= n;
for(int i=1; i<=n; i++) c[i]= C[i+nulls];
return c;
}
...
Что касается умножения, то тут можно применять разные методы. И самым удобным для программирования мне показался матричный метод- это отличается от стандартного умножения столбиком. Суть в том, что числа можно представить в виде полиномов, где цифры и будут как раз коэффициентами. И далее применить полиномиальное умножение поциферное- функция у нас для этого уже есть. И останется сделать только поразрядные сдвиги.
1. Преобразование цифромассивов в стандартные- где в первом элементе у нас не будет храниться количество чисел.
2. Перемножаем урезанные 2 цифромассива как обычные полиномы.
3. Добавляем опять в первый элемент кол-во цифр нового цифромассива.
4. Делаем поразрядный сдвиг справа налево.
Ниже представлен алгоритм. Функция полиномиального умножения та же самая что была в главах ранее.
int *Kosh_Prod (int a[], int b[]) {
int adeg= a[0]-1, bdeg= b[0]-1;
int *A= new int [a[0]];
int *B= new int [b[0]];
for(int i=0; i<=adeg; i++) A[i]= a[i+1];
for(int i=0; i<=bdeg; i++) B[i]= b[i+1];
int *C= PolynomProd(A,adeg,B,bdeg);
int n= adeg+bdeg+1;
int *c= new int [n+1];
c[0]= n;
for(int i=1; i<=n; i++) c[i]= C[i-1];
int fazla= 0;
for(int i=n; i>=1; i--) {
c[i]+= fazla;
if(c[i]>=10) {
fazla= c[i]/10;
c[i]= c[i]%10;
}
}
if(fazla) {
int *c1= new int[n+2];
c1[0]= n+1;
c1[1]= fazla;
for (int i=2; i<(n+2); i++) c1[i]= c[i-1];
return c1;
}
return c;
}
Дата добавления: 2018-09-22; просмотров: 292; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!