Большие числа на С++

Тема в разделе "Общие вопросы по С и С++", создана пользователем Natka, 17 дек 2006.

Статус темы:
Закрыта.
  1. Natka

    Natka Гость

    Быстрое умножение длинных целых чисел

    Главная идея быстрого умножения состоит в модификации выражения A×C×10N+(A×D+B×C)×10N/2+B×D таким образом, чтобы уменьшить количество операций умножения: A×C×10N+(AD+BC)×10N/2+B×D = A×C×10N+(A-B)×(D-C)×10N/2+B×D+(A×C+B×D)×10N/2. Видно, что теперь необходимо найти лишь три произведения N/2-значных чисел.

    Задание.

    1) Реализовать алгоритм сложения двух длинных целых чисел.
    2) Реализовать алгоритм умножения двух длинных целых чисел.
    3) Реализовать нерекурсивный алгоритм быстрого умножения.
    а) в программе должен присутствовать механизм контроля используемой памяти (пиковый расход).
    б) сделать модификацию алгоритма для перемножения чисел, разрядность которых не является степенью двойки.
    4) Реализовать рекурсивный алгоритм быстрого умножения.
    5) Написать тестовую программу для сравнения двух реализаций.
    6) Написать тестовые программы для демонстрации правильности работы программ.
    а) входные данные хранятся в файле mult.txt: в первой строке разрядность чисел, во второй и третьей - сами множители.
    б) входные данные должны дублироваться на экране, результат перемножения тоже выводить на экран.
    7) Разработать набор тестов для проверки правильности (включает не менее 10 тестовых случаев). Реализовать режим пакетной прогонки разработанных тестов.



    Необходимо реализовать на С/С++. Помогите, пожалуйста!
     

    Вложения:

    • Task_5.htm
      Размер файла:
      4,3 КБ
      Просмотров:
      159
  2. Creo

    Creo Гость

  3. sab0tage

    sab0tage Гость

    <!--QuoteBegin-Creo+19:12:2006, 09:20 -->
    <span class="vbquote">(Creo @ 19:12:2006, 09:20 )</span><!--QuoteEBegin-->Посмотри прикрепленный файл. Мот поможет чем. smile.gif
    Прикрепленный файл LONG.pdf ( 372.88 килобайт ) Кол-во скачиваний: 0
    [snapback]51123" rel="nofollow" target="_blank[/snapback]​
    [/quote]
    Четко, сам учился по этому документу. С профом спорили, кто лучше программирует, а тут такой мануал.

    Больше правдо на С не программирую, вот мой код, дарю :) компилировал под VS6.
    Находил числа до 50Кб длинной. Профу принес распечатку 2 в 20000й степени, пару листов А4 мелким шрифтом.

    Код (Text):
    #include <iostream.h>
    #include <fstream.h>

    struct NUM
    {
    short int n[20000];  /*this is a NUMber set.*/
    int n_size;         /*this is a size of the NUMber*/
    };

    //put in the NUMber from the file
    NUM fillNUMf(char filename[20])
    {
    NUM temp;
    ifstream f;
    int i,fr;
    char fr1;
    f.open (filename);
    i=0;
    while (!f.eof())
    {
    i++;
    f>>fr1;
    fr=fr1-48;
    temp.n[i-1]=fr;
    }
    temp.n_size=i-1;
    f.close();
    return temp;
    }

    //put in the NUMber manually
    NUM fillNUMk()
    {
    NUM temp;
    short int inp;
    int i,size;

    cout <<" \nHuge Number Input. (enter value > 9 to stop):";

    inp=0;
    i=0;

    while (inp<10)
    {
    cout<<"\n Enter the number posiotion " <<i <<" :";
    cin >>inp;
    temp.n[i]=inp;
    i++;
    }

    temp.n_size=i-1;
    temp.n[i]=0;

    return temp;
    }

    //display NUMber on console
    void showNUMd(NUM temp)
    {
    int i;
    cout<<"\nnum["<<temp.n_size<<"]";
    for (i=0;i<temp.n_size;i++)
    cout<< temp.n[i];
    cout<<endl;
    }

    //save NUMber into file
    void showNUMf(NUM temp, char filename[20])
    { int i;
    char tes;
    ofstream f;
    f.open(filename);
    for(i=0;i<temp.n_size;i++)
    {
    tes=temp.n[i]+48;
    f<<tes;
    }
    f.close();
    }

    //inverts NUMber
    NUM invertNUM(NUM temp)
    {
    int i,buf;
    for(i=0;i<temp.n_size/2;i++)
    {
    buf=temp.n[i];
    temp.n[i]=temp.n[temp.n_size-i-1];
    temp.n[temp.n_size-i-1]=buf;
    }
    return temp;
    }

    //delets the zeroes at the beginning
    NUM performNUM(NUM temp)
    {
    int i,pos;

    i=0;
    pos=0;

    while (temp.n[i]==0)
    {     pos++;
    i++;
    }

    if (pos!=0)
    {
    temp.n_size=temp.n_size-pos;
    for(i=0;i<=temp.n_size;i++)
    temp.n[i]=temp.n[i+pos];
    }
    return temp;
    }

    //multiplication itself
    NUM mul_(NUM NUM1, NUM NUM2)
    {  
    NUM res;
    int i,j,carry,temp;


    NUM1=performNUM(NUM1);
    NUM1=invertNUM(NUM1);
    NUM2=performNUM(NUM2);
    NUM2=invertNUM(NUM2);

    res.n_size=NUM1.n_size+NUM2.n_size;
    for(i=0;i<res.n_size;i++)
    res.n[i]=0;

    for(i=0;i<NUM2.n_size;i++)
    {
    carry=0;
    for(j=0;j<NUM1.n_size;j++)
    {
    temp=NUM2.n[i]*NUM1.n[j]+res.n[i+j]+carry;
    carry=temp/10;
    res.n[i+j]=temp-(carry*10);
    }
    res.n[i+j]=carry;
    }

    res=invertNUM(res);
    res=performNUM(res);
    return res;
    }

    //finds an entered power of two;
    void powerdemo()
    {  NUM t0,t1,t2;
    int i,power;

    t1.n_size=1;
    t1.n[0]=2;

    t2.n_size=1;
    t2.n[0]=2;

    cout <<"Enter the power: ";
    cin >>power;

    for(i=2;i<=power;i++)
    {
    t0=mul_(t1,t2);
    cout <<"2^" <<i <<endl;
    //showNUMd(t0);
    t1=t0;
    }
    showNUMf(t1,"c:/2^100000.txt");

    }

    //main module
    void main()
    {

    NUM t0,t1,t2;
    //t1=fillNUMf("c:/num1.txt");
    //t2=fillNUMf("c:/num2.txt");
    cout <<"\n 1st Number:";
    cout <<"\n -----------";
    t1=fillNUMk();
    cout <<"\n 2nd Number:";
    cout <<"\n -----------";
    t2=fillNUMk();


    cout <<"\nMultiplication in process\n";
    t0=mul_(t1,t2);

    cout <<"\n 1st Number:"; showNUMd(t1);
    cout <<"\n 2nd Number:"; showNUMd(t2);
    cout <<"\n The result of multiplication:";
    showNUMd(t0);
    //showNUMf(t0,"c:/res.txt");


    //powerdemo();
    }
     
  4. Homer37

    Homer37 Гость

    Программа была реализована? если да то напишите листинг умножения.
     
  5. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Некропостинг. Закрыто
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей