Длинная арифметика. Класс работы с длинными числами. - C++ - Ответ 2847248

@User1990 · Регистрация: 03.11.2009

Author24 — интернет-сервис помощи студентам

C++

// модул_умнож.cpp : main project file.
 
#include "stdafx.h"
#include "vector"
#include <algorithm>
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
 
class long_{
    public:
        std::vector<unsigned short> chislo;
    bool znak;
    
        long_(): znak(true), chislo(0){};
        long_(std::vector <unsigned short>  mas,bool p): znak(p), chislo(mas){};
        long_(unsigned int size,bool p): chislo(size), znak(p) {
            int i;
            for(i=0;i<size;i++)
                chislo[i]=0;
        };
        long_(std::vector<unsigned short>::iterator  begin, std::vector<unsigned short>::iterator end,bool p):chislo(begin,end),znak(p){};
 
    /*static long_ & algorithm_euclida(long_ & a, long_ & b){
    
        long_  x1,y1,x2,y2,x,y;
        
        x1(1);x2(0);y1(0);y2(1);
        while(a%2==0 && b%2==0){
        
            a=a/2; b=b/2;   
        }
 
        x=a;y=b;
 
        do{
            while(x%2==0){
    
                x=x/2;
    
                if(x1%2==0 && y1%2==0){
                
                    x1=x1/2;y1=y1/2;
            
                }else{
                
                    x1=(x1+y)/2; y1=(y1-x)/2;
            
                }
            }
 
            while(y%2==0){
            
                y=y/2;
            
                if(x2%2==0 && y2%2==0){
            
                    x2=x2/2;y2=y2/2;
            
                }else{
                
                    x2=(x2+y)/2; y2=(y2-x)/2;
            
                }
            }   
    
            if(x>=y){
            
                x=x-y;
            
                x1=x1-x2; y1=y1-y2;
                
            }else{  
    
                y=y-x;
    
                x2=x2-x1; y2=y2-y1;
 
            }
 
        }while(x!=0);
    
    x=y1;y=y2;
 
    return x;
}*/
    
 
    static  long_  Montgomery(long_ & A, long_ & B, long_ & M, unsigned int & n){
                long_ p(15,true);
                unsigned int i,j,c,s,m,q;
            
                for(i=0;i<m;i++){
                
                    q=((n*p.chislo[0] + A.chislo[0]*B.chislo[i])) & 0xFFFF;
                    c=A.chislo[0]*B.chislo[i] + p.chislo[0] + M.chislo[0]*q;
                    s=c >> 16;
                    for(j=1;j<m;j++){
 
                        c=c + A.chislo[j]*B.chislo[i] + p.chislo[j] + q*M.chislo[j];
                        s=c;
                        p.chislo[j-1]=s;
                        c=c >> 16;
                    }
                    p.chislo[j-1]=c;
                }
            return p;   
        };
 
        bool operator >(long_ & c){
        if(znak && c.znak){ 
            
            if(!znak){
                
                if(chislo>c.chislo)
            
                    return false;
                else
                    return true;
                
            }
        
            else{
                if(chislo>c.chislo)
            
                    return true;
                else
                    return false;
            }
        }
        else{
            if(znak)
                return true;
            else
                return false;
        }
 
        }
        bool operator >=(long_ & c){
        if(znak && c.znak){ 
            
            if(!znak){
                
                if(chislo>c.chislo)
            
                    return false;
                else
                    return true;
                
            }
        
            else{
                if(chislo>=c.chislo)
            
                    return true;
                else
                    return false;
            }
        }
        else{
            if(znak)
                return true;
            else
                return false;
        }
        }
        bool operator <(long_ & c){
        if(znak && c.znak){ 
            
            if(!znak){
                
                if(chislo<c.chislo)
            
                    return false;
                else
                    return true;
                
            }
        
            else{
                if(chislo<c.chislo)
            
                    return true;
                else
                    return false;
            }
        }
        else{
            if(znak)
                return false;
            else
                return true;
        }
        }
        bool operator <=(long_ & c){
            if(znak && c.znak){ 
            
            if(!znak){
                
                if(chislo<c.chislo)
            
                    return false;
                else
                    return true;
                
            }
        
            else{
                if(chislo<=c.chislo)
            
                    return true;
                else
                    return false;
            }
        }
        else{
            if(znak)
                return true;
            else
                return false;
        }
        }
        bool operator !=(long_ & c){
        if(znak && c.znak){ 
    
                if(chislo!=c.chislo)
            
                    return true;
                else
                    return false;
                
            }
        
            else
                return true;
    
    
        }
        bool operator ==(long_ & c){
        if(znak && c.znak){ 
    
                if(chislo==c.chislo)
            
                    return true;
                else
                    return false;
                
            }
        
            else
                return false;
    
        }
 
        long_  operator +(long_ & y){
            long_ c;
            std::vector<unsigned short>::iterator j,i;
            unsigned int carry=0,k=0;
            if(znak==y.znak){
                c.znak=znak;
                i=chislo.begin();
                j=y.chislo.begin();
                for(;i!=chislo.end() && j!=y.chislo.end();++i,++j){ 
                    carry=(*i)+(*j)+carry;                  
                    c.chislo.push_back(carry & 0xFFFF);
                    carry=carry>>16;
                    }
            while(i!=chislo.end()){
                    carry=(*i++)+carry;
                    c.chislo.push_back(carry & 0xFFFF);
                    carry=carry>>16;
                }
            while(j!=y.chislo.end()){
                    carry=(*j++)+carry;
                    c.chislo.push_back(carry & 0xFFFF);
                    carry=carry>>16;
                }
            if(carry)
                c.chislo.push_back(carry & 0xFFFF);
            }
            else{
                if(znak){
                    y.znak=true;
                    c=*this-y;
                }
                else{
                    znak=true;
                    c=y-(*this);
                }
            }
 
 
        return c;
        
        };
        long_  operator-(long_ & y){
            long_ c;
            std::vector<unsigned short>::iterator j,i,p,l;
            unsigned int carry=0;
            
            if(!y.znak && znak){
                if(y.znak)
                    znak=true;
                else
                    y.znak=true;
                c=*this + y;
                }
            else{
                if(*this>=y){
                    if(znak){
                        c.znak=true;
                        i=chislo.begin();
                        p=chislo.end();
                        j=y.chislo.begin();
                        l=y.chislo.end();
                    }
                    else{
                        c.znak=false;
                        i=y.chislo.begin();
                        p=y.chislo.end();
                        j=chislo.begin();
                        l=chislo.end();
                    }
                }   
                else{
                    if(znak){
                        c.znak=false;
                        i=y.chislo.begin();
                        p=y.chislo.end();
                        j=chislo.begin();
                        l=chislo.end();
                    }
                    else{
                        c.znak=true;
                        i=chislo.begin();
                        p=chislo.end();
                        j=y.chislo.begin();
                        l=y.chislo.end();
                    }
                }
        for(;i!=p;i++){ 
            if(j!=l){   
                if((*i)<(*j)){
                    *(i+1)=*(i+1) - 0x1;
                    carry= *i | (1 << 16);
                    carry=carry - (*j++);
                }else
                    carry= (*i) - (*j++);
                c.chislo.push_back(carry & 0xFFFF);
            }
            else{
                c.chislo.push_back(*i);
            }
        }
    }
        return c;
 
    };
        long_ & operator =(long_ & y){
            if(!chislo.empty())
            chislo.clear();
            chislo=y.chislo;
            znak=y.znak;
            return *this;
        };          
 
        long_ operator *(unsigned int & y){
                unsigned int i,carry=0;
                long_ p;
 
                carry=chislo[0]*y ;
                p.chislo.push_back(carry);
                carry = carry >> 16;
                for(i=1;i<chislo.size();i++){
                    carry = chislo[i] + carry;
                    p.chislo.push_back(carry);
                    carry=carry >> 16;
                }
                if(carry) p.chislo.push_back(carry);
                return p;
        };
        long_  square(){
            long_ c(2*chislo.size(),true);
            unsigned int i,j, f, k;
        
            for(i=0;i<this->chislo.size();i++){
                f=0;
                for(j=0;j<i;j++){   
                    k=this->chislo[i]*this->chislo[j];
                    f=((k & 0xFFFF) << 1) + c.chislo[i+j];
                    c.chislo[i+j]= f & 0xFFFF;
                    f= f >> 16;
                    f= f + ((k >> 16) << 1);
                }
                k= this->chislo[i]*this->chislo[i];
                f= f+ (k & 0xFFFF) + c.chislo[2*i];
                c.chislo[2*i]= f & 0xFFFF;
                f= (f >> 16) + c.chislo[2*i+1] + (k >> 16);
                c.chislo[2*i+1]= f & 0xFFFF;
                c.chislo[2*i+2]= f >> 16;
            }
            if(c.chislo.at(c.chislo.size()-1)==0) c.chislo.erase(c.chislo.begin() + (c.chislo.size()-1));
        return c;   
        }
 
        long_ operator *(long_ & y){
            
            long_ c(y.chislo.size() + chislo.size(),true);
            std::vector<unsigned short>::iterator i,j;
            unsigned int carry,k=0,p;
                        
            for(i=y.chislo.begin();i!=y.chislo.end();i++){
                p=k;
                for(j=chislo.begin();j!=chislo.end();j++){
                                carry = (*i) * (*j) + carry;
                                c.chislo[k++] = carry + c.chislo[k];
                                carry = carry >> 16;
                            }
                if(carry) c.chislo[k]=carry;
                k=p+1;
                carry=0;    
                        }
            if(!c.chislo.at(c.chislo.size()-1)) c.chislo.erase(c.chislo.begin() + (c.chislo.size()-1));
        }
 
        bool operator ==(unsigned int y){
 
            for(int i=0;i<this->chislo.size();i++){
                if(this->chislo.at(i)!=0) return false;
            }
            return true;
        }
        long_ operator /(long_ & y){
            long_ c(abs(y.chislo.size()- chislo.size()), znak ^ y.znak);
            long_ * h,o(1,true),p(y.chislo.begin(),y.chislo.begin()+2,true);
            unsigned int i=0,u=0,carry=0,l;
            std::vector<unsigned short>::reverse_iterator j,k;
            l=abs(y.chislo.size()- chislo.size())-1;
            /*if (y==0){
                throw::dec();
            }*/
            if(*this<y){
                return o;
            }else{
            if(y.chislo.size()==1){
                for(i=chislo.size()-1;i>=0;i--){
                    u= chislo[i] + u;
                if(chislo[i]<y.chislo[0]){
                    u = u << 16;
                    u = chislo[i-1]  + u;
                    c.chislo[l--]=(u/y.chislo[0]);
                    u = u - c.chislo[l+1];
                    i--;
                }else{
                    u= u << 16;
                    c.chislo[l--]=(u/y.chislo[0]);
                    u = u - c.chislo[l+1];
                }
                }
            }else{
                unsigned int n=this->chislo.size()-y.chislo.size();
                while(i++<n){
                    y.chislo.erase(y.chislo.begin());
                }
                while(chislo>y.chislo){
                        carry= carry + 1;
                        *this = *this  - y;
 
                }
                j = chislo.rend()-1;
                k= y.chislo.rend()-1;
                for(i=this->chislo.size()-1;i<=y.chislo.size();i++){
                    carry=0;
                    if(*j>=*k) 
                        carry=0x10000 - 0x1;
                    else
                        carry=(int(chislo[i] << 16) + chislo[i-1])/(*k);
                    h=new long_(chislo.begin() + chislo.size()-1,chislo.begin() + chislo.size()-4,znak);
                    
                    while(p*carry>(*h)){
                            carry=carry-1;
                    }
                    delete h;
                    y.chislo.erase(y.chislo.begin());
                    *this=*this-y*carry;
                    if(*this<o){
                        y.chislo.erase(y.chislo.begin());
                        *this=*this+y*carry;
                        carry=carry-1;
                    }
                    c.chislo.push_back(carry);
                }
            }
            return c;}
        }
};
void zero(char * c,unsigned short n){
    while(n--){
        c[n]=0;
    }
}
int main()
{   
    FILE *fp;
    char c[4],symbol;
    long_ * h[2];
    unsigned short i=0,j, k=0;
    std::vector<unsigned short> mas;
 
    if(fopen_s(&fp,"opyt.txt","r")){
        printf("error\n");
    }
 
    while(1){
        symbol=fgetc(fp);
        while(symbol!='\n' && symbol!=EOF){
            if(j!=4)
                c[j++]=symbol;
            if(j==4){
                sscanf_s(c,"%x",&i,sizeof(unsigned short));
                mas.push_back(i);
                zero(c,4);
                printf("%d\n",i);
                j=0;
            }
            symbol=fgetc(fp);
            
        }
        if(j!=0){
                sscanf_s(c,"%x",&i,sizeof(unsigned short));
                mas.push_back(i);
                zero(c,4);
                printf("%d\n",i);
                j=0;
        }
        h[k++]=new long_(mas,true);
            mas.clear();
        if(symbol==EOF) break;
 
    }
 
    fclose(fp);
    long_ b=(*(h[0]))/(*(h[1]));
    std::cout<<std::endl;
    for(k=0;k<b.chislo.size();k++)
        std::cout<<hex<<b.chislo[k]<<std::endl;
    return 0;
}

необходимо написать класс работы с длинными числами, так вот что я сделал... чтение чисел пока из файла в шестнадцатеричном формате сначала младшие разряды , потом старшие, система 32 разрядная , поэтому для цифры 1 unsigned short, умножение в столбик , т.к. там где будет применяться не особо нужно , поэтому не Тоома-куку и не карацуба, просьба просмотреть на деление, в нем что-то неправильно...также высказывайте критику и найденные ошибки, а также как ускорить все это дело....БУДУ ПРИЗНАТЕЛЕН

Вернуться к обсуждению:
Длинная арифметика. Класс работы с длинными числами. C++

Следующий ответ

Другие темы раздела
C++ Отсортировать файл по первому символу строки Помогите пожалуйста с заданием: "Отсортировать файл по первому символу строки" Заранее спасибо! https://www.cyberforum.ru/ cpp-beginners/ thread533238.html	Запрограммировать рекурсивный алгоритм вычисления квадрата C++ Добрый вечер. Может кто нить помочь.. Запрограммировать рекурсивный алгоритм вычисления квадрата натурального числа, используя рекуррентное соотношение
C++ Затолкнуть в вектор aray const int size=3; int aray={{1,1,0},{1,1,-1},{1,0,-1}}; vector <int> s; for(int i=0;i<size;i++) { s.push_back(?) мне надо затолкнуть в вектор aray как это сделать? } https://www.cyberforum.ru/ cpp-beginners/ thread533224.html	C++ Считать с файла строки и записать в буфер. Удалить строки. https://www.cyberforum.ru/ cpp-beginners/ thread533223.html Считать с файла строки записать в буфер. Удалить строки с начиная с X введенным с клавиатуры по Y также введенным с клавиатуры.Т.е. если ввели 4 2, должно удалить 4,5 строки. Результат записать у файл. Вот что есть сейчас, работает только если вводить 1 2,1 3. Не хочет работать если ввести 2 1 или 2 4. #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <alloc.h> #include...
C++ C++, отсортировать методом выбора текстовый файл В текстовом файле содержатся сведения о группе студентов в формате: запись о каждом студенте группы, которая содержит следующие сведения: фамилия, имя, отчество, год рождения, оценки по пяти предметам. Переписать данные файла в новый текстовый файл, отсортировав их по фамилии студентов и убыванию их года рождения посредством "выбора". Добавлено через 1 час 8 минут *********up	C++ Пишу ОС, нужен доступ к экрану https://www.cyberforum.ru/ cpp-beginners/ thread533217.html Здравствуйте! Пишу свою ОС, основная работа на ассемблере есть, теперь осталось написать на Си. Проблема такая, есть адрес видеопамяти 0xb8000, нужно создать к ней указатель, затем запустить цикл, и циклом обнулить экран, размер экрана задан как: #define VIDEO_WIDTH 80 //ширина экрана #define VIDEO_HEIGHT 25 //высота экрана , кто знает как обнулить экран?
C++ Операция с файлами, графика нужна помощь Ребята помогите решить две задачки на С, очень прошу Вашей помощи, к сожалению мне девушке это не по силе, а друзей программистов нету, решила обратится на этот форум программистов. 1. Задан файл f, содержащий информацию об автомобиле (марка, номер, фамилия владельца) Вывести количество автомобилей каждой марки. 2. Нарисовать голубым цветом квадрат, в нем нарисовать желтым цветом круг,... https://www.cyberforum.ru/ cpp-beginners/ thread533216.html	C++ В строке вместо названия показывает какое-то число В строке вместо названия (nazvanie в моей программе) показывает какое-то число, вместо слов (Smart,Kingston,LG)#include <stdio.h> #include <stdlib.h> #include<conio.h> int k; void main() { clrscr(); struct informacia { char nositel; int obem; char nazvanue; char avtor;}
C++ С Паскаля на С++. Реализация модели распределения памяти. Задание. Программа реализация модели распределения памяти перемещаемыми разделами. Program Model_raspredelenia_pameati; uses crt; const n=10; type massiv=array of integer; Label L1,L2,L3; Var A:massiv; y:string; i,j,k,g,sum,w,x :integer; begin clrscr; randomize; {включение генератора случайных чисел } https://www.cyberforum.ru/ cpp-beginners/ thread533196.html	C++ Преобразовать последовательность из n вещественных чисел a1, ..., an. Ребят подкиньте идей. Дана последовательность из n вещественных чисел a1, ..., an. Преобразовать ее по следующему правилу: а) первый элемент равен первому элементу; б) второй равен max(a1, a2); в) третий - max(a1, a2, a3); . . . . . . . . . . . Добавлено через 1 час 46 минут UP UP! https://www.cyberforum.ru/ cpp-beginners/ thread533194.html
C++ Поиск корней (включая комплексные) полинома n-й степени Надо прожку на вижуале... чтобы искала все корни (включая комплексные) полинома н-й степени, когада известны коэвициенты...	C++ Использование цикла while и вложенных циклов 1. Используя цикл while, напишите программу, вычисляющую сумму цифр заданного целого числа. Например, суммой цифр числа 2155 будет 2 + 1 + 5 + 5 = 13. Для выделения цифр используйте остатки от последовательного деления числа на 10. 2. Используя вложенные циклы, напишите программу, выводящую на экран «полуелочку» из звездочек:* * * * * * * * * * * * * * * * * * * https://www.cyberforum.ru/ cpp-beginners/ thread533186.html

	28.03.2012, 21:50