Форум программистов, компьютерный форум CyberForum.ru

MPI и возведение в степень - C++

Восстановить пароль Регистрация
 
StamSvam
6 / 6 / 0
Регистрация: 08.07.2012
Сообщений: 65
18.05.2013, 23:58     MPI и возведение в степень #1
Уважаемые коллеги, я зашел в тупик.

Необходимо написать алгоритм возведения числа 2 в степень, подразумеваются "длинные" числа. Реализовал с помощью массивов, алгоритм - умножение столбиком.
Но тут возникла проблема. У меня ума не хватает придумать, как распараллелить данный алгоритм (код приведен ниже) и разделить его между хотя бы двумя узлами.

Подскажите, пожалуйста, как его распараллелить.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include"MyMethods.h"
#include"Dos.h"
 
void main()
{
    
    int N;  
    printf("Enter the power of 2: ");
    scanf("%d", &N);   //  N - степень числа
    
    int len = 1, sum = 0, size = N/3+1; 
    int *m = new int[size], *res = new int[size];
    float timer_start, timer_end;
    VectNull(m,size); VectNull(res,size);  //пользовательская функция, заполняет массив нулями
    
    res[0]=2;
    
    for (int j=1; j<N; j++)
    {
        if (j%3==0) len++;
        CopyVect(m, res, len);      //пользовательская функция, копирует кол-во элементов из массива в массив
        VectNull(res,len);              //пользовательская функция, заполняет массив нулями
        for (int i = 0; i< len; i++)
        {
            if (m[i]*2>9) {res[i] += (m[i]*2)%10; res[i+1]=1;}  //   если происходит переполнение разряда, в
                                                                                   // следующем элементе пишется 1,а на текущей 
                                                                                   //позиции записывается младший разряд числа.
            else res[i] += m[i]*2;
        }
    }
//  в общих словах, выделяем память под весь массив "Степень/3+1", должно хватить, избыток будет до 2х 
//  элементов. Далее присваиваем первый элемент массива m равный двойке. Умножаем, результат добавляем в 
//  массив res. И так N-1 раз.
//  в итоге в массиве res хранится результат
 
    for (int i=0; i<len; i++) sum += res[i];  //вычисление суммы цифр числа (часть задания)
        
    printf("\nSum of digits = %d\n",sum);
    printf("\nTime = %f\n\n",(timer_end-timer_start)/CLOCKS_PER_SEC);
    system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2013, 23:58     MPI и возведение в степень
Посмотрите здесь:

Возведение в степень C++
C++ Возведение степень
Возведение в степень C++
C++ Возведение в степень
Возведение в степень C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
19.05.2013, 00:35     MPI и возведение в степень #2
Возможно это не совсем в тему, но может быть как то поможет.
Например, для возведения 3 в 4-ю степень нам нужно проделать 3 операции умножения. Однако если изменить порядок действий на такой: (3^2)^2, то потребуется всего два умножения. Следует помнить, что при возведении числа в степени еще в какую-либо степень показатели степеней перемножаются. Именно на сокращении четных степеней основывается идея быстрого возведения в степень.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 int pow(int a, int n) {
 int b, c, k;
 k = n;
 b = 1;
 c = a;
while (k)
 if (!(k%2)) {
 k /= 2;
c *= c;
 } else {
 k--;
b *= c;
}
 return b;
 }
StamSvam
6 / 6 / 0
Регистрация: 08.07.2012
Сообщений: 65
19.05.2013, 00:45  [ТС]     MPI и возведение в степень #3
Genn55, дело в том, что мне нужно разбить данный алгоритм.. что уж там, код надо разбить хотя бы на 2 части так, чтобы они работали независимо друг от друга и выполнить каждый кусок на своем узле, если вы понимаете о чем я.

например имея выражение 1*2*3*4, мы можем выполнить его последовательно, т.е. 1*2*3*4, или разбить на два куска, 1*2 и 3*4, которые будут вычисляться одновременно. А потом можно и результаты перемножить. Такой принцип распараллеливания у MPI, если я верно понял..
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
19.05.2013, 01:00     MPI и возведение в степень #4
Я понял,что не в тему.Ну может когда и пригодится.
StamSvam
6 / 6 / 0
Регистрация: 08.07.2012
Сообщений: 65
19.05.2013, 12:43  [ТС]     MPI и возведение в степень #5
Люди, ну неужели нет тут человека, который шарит?

Добавлено через 52 минуты
Если Вы знаете такого человека, который разбирается в MPI, позовите, пожалуйста, к пульту. Горит просто.
Yandex
Объявления
19.05.2013, 12:43     MPI и возведение в степень
Ответ Создать тему
Опции темы

Текущее время: 11:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru