С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
StamSvam
6 / 6 / 0
Регистрация: 08.07.2012
Сообщений: 65
#1

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

18.05.2013, 23:58. Просмотров 557. Ответов 4
Метки нет (Все метки)

Уважаемые коллеги, я зашел в тупик.

Необходимо написать алгоритм возведения числа 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");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2013, 23:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос MPI и возведение в степень (C++):

Возведение в степень - C++
Подскажите пожалуйста алгоритм возвидения в степень, есть карта в которой храниться разные цифры мой велосипед for (std::map&lt;int,...

Возведение в степень! - C++
Возник вопрос - Возможно пока не понятна в чем мысль! Попробую на примере объяснить! Возведение числа 2 в 1000 - ую степень будет...

Возведение в степень - C++
подскажите,пожалуйста, способ реализации (алгоритм)операции возведение в степень числа с показателем более 200. Результат не должен...

возведение в степень! - C++
Кто помнит функцию возведения в степень.?? &quot;трам-пам-пам&quot; (a,b) ???? Добавлено через 3 минуты И еще желательно...

Возведение в степень. C++ - C++
можно ли написать программу для возведения в вводимую степень вводимого числа с помощью рекурсивной функции

Возведение в степень - C++
Совсем недавно начал изучать C++. Учу по книге. Было задание: Вводишь число Вводишь степень в которую надо возвести это число ...

4
Genn55
374 / 221 / 41
Регистрация: 26.12.2012
Сообщений: 727
19.05.2013, 00:35 #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;
 }
0
StamSvam
6 / 6 / 0
Регистрация: 08.07.2012
Сообщений: 65
19.05.2013, 00:45  [ТС] #3
Genn55, дело в том, что мне нужно разбить данный алгоритм.. что уж там, код надо разбить хотя бы на 2 части так, чтобы они работали независимо друг от друга и выполнить каждый кусок на своем узле, если вы понимаете о чем я.

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

Добавлено через 52 минуты
Если Вы знаете такого человека, который разбирается в MPI, позовите, пожалуйста, к пульту. Горит просто.
0
19.05.2013, 12:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.05.2013, 12:43
Привет! Вот еще темы с ответами:

Возведение a в степень b - C++
Пользователь вводит числа а и b, программа считает &quot;а&quot; в степени &quot;b&quot;. Помогите написать код

Возведение в степень - C++
Вам конечно это покажется тупой проблемой, но всё же. Напишите пожалуйста как возводить в степень на си и пример. В инете что ищу всё на...

возведение в степень - C++
помогите плиз! в файле есть задачка. нужно рекурсивно возвести в степень. Код: #include &lt;iostream&gt; float stepen(float a, int n) { ...

Возведение в степень - C++
Подскажите оператор для возведения числа в n-ую степень. Зарание спасиба


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.