Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 26.05.2012, 14:03   #1
Семоха Валерий
 
Регистрация: 04.10.2011
Сообщений: 7
По умолчанию Оптимизация программы

Здравствуйте, получил я задание написать программу перемножения двух больших чисел, используя быстрое преобразование Фурье. Дал мне преподаватель на это 4 дня, чему я очень удивился - маловато будет, да и к тому же зачетная неделя. Ну да ладно, нашел пару статей - худо-бедно написал. Прихожу сегодня сдавать, получаю ответ такой, что мол фуфло все, давай оптимизируй, мол, ускорь процесс. Вобщем идей у меня никаких, а делать нужно. Просьба натолкнуть на мысль, но готовые куски кода тоже приветствуются, поскольку со временем у меня туго - до вторника нужно сдать.
Ах, да, забыл, язык - C++
Вот первая часть кода (а то в одно сообщение не умещается):
Код:
// fft.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <malloc.h>
#include <vector>
#include <complex>
#include <time.h>
clock_t clock(void);

using namespace std;
typedef complex<double> base;
static double pi2 = 2*3.1415926535897932384626433832795;

char* s;
int sc;
int i2;
int op;

//***

class NUM
{
	private:
		char* chislo;
		int i,j,n;
	public:

	NUM () //конструктор
	{ 
		setlocale(LC_ALL, "Russian");
		chislo = (char*) malloc(1001);
	}

	~NUM () // деструктор
	{ 
		delete [] chislo;
		cout << " \n [ENTER] для выхода";
		getch ();
	}

	int stop ()
	{
		cout << " Завершение работы программы. Нажмите [ENTER]";
		return 0;
	}


	int prp ()
	{
		if (chislo == NULL)
		{
			cout << " Ошибка, память не выделена";
		}
		return 0;
	}

	vector<short> preobraz_to_vector(char* s, int ls, vector<short> a) //строка в вектор
	{
		for (int i=0; i<ls; i++)
		a[i]=s[ls-1-i]; 
		return a;
	}

	char* vector_to_obrpreobraz(vector<short> &a) //вектор в строку
	{
		int j=a.size();
		for (int i=a.size()-1; a[i]==0; i--)
		j--;
		char *s=(char*)malloc(j);
		for (int i=0; i<j; i++)
		s[j-1-i]=a[i]; 
		s[j]=-1;
		return(s);
	}

	void fft (vector<base> &a, bool invert) //алгоритм быстрого преобразования преобразования фурье
	{

		int n = (int) a.size();
		if (n == 1) return;

// деление массива пополам
		vector<base> a0 (n/2), a1 (n/2);
		for (int i=0, j=0; i<n; i+=2, ++j) 
		{
			a0[j] = a[i];
			a1[j] = a[i+1];
		}
		fft (a0, invert);
		fft (a1, invert);

		long double ang = pi2/n * (invert ? -1 : 1);
		base w (1), wn (cos(ang), sin(ang)); 

		for (int i=0; i<n/2; ++i)
		{
			a[i] = a0[i] + w * a1[i]; // ф-ла 1
			a[i+n/2] = a0[i] - w * a1[i]; // ф-ла 2
			if (invert)
			a[i] /= 2, a[i+n/2] /= 2;
			w *= wn;
		}

	}

	void multiply (const vector<short> & a, const vector<short> & b, vector<short> & res) //функция умножения
	{
		vector<base> fa (a.begin(), a.end()), fb (b.begin(), b.end());
		size_t n = 1;
		while (n < max (a.size(), b.size())) n <<= 1; // пока длина числа меньше max половины
		n <<= 1;
		fa.resize (n), fb.resize (n);

		fft (fa, false); 
		fft (fb, false); 
		for (size_t i=0; i<n; ++i)
		fa[i] *= fb[i];
		fft (fa, true);

		res.resize (n);
		for (size_t i=0; i<n; ++i)
		res[i] = int (fa[i].real() + 0.5);

		int carry = 0; //нормализация (перенос разрядов)
		for (size_t i=0; i<n; ++i) 
		{
			res[i] += carry;
			carry = res[i] / 10;
			res[i] %= 10;
		}

	}

Последний раз редактировалось Семоха Валерий; 26.05.2012 в 16:48.
Семоха Валерий вне форума Ответить с цитированием
Старый 26.05.2012, 14:04   #2
Семоха Валерий
 
Регистрация: 04.10.2011
Сообщений: 7
По умолчанию

Второй кусок кода:

Код:
	
	int fourie () //функция (ввод+использование умножения)
	{
		char* s1=(char*)malloc(1001);
		char* s2=(char*)malloc(1001);		// !
		complex<double>; 
		long ls1, ls2; // длины чисел
		int index;
		int indexs;
		int chs;

		setlocale(LC_ALL, "rus");

// ввод чисел
		//1
		printf (" \n\n Введите первое число\n ");
		char h=getche ();

		ls1=0;
		while ( h != 13)
			{ 
				s1[ls1] = h-48;
				ls1++;
				h = getche ();
			}
		if (sc != 0)
		{
			cout << "\n Ошибка ввода, [ENTER] для продолжения\n";
			getch ();
			return 0;
		}

		i2=ls1;
		if (s1[0] == 0)
		{
			for (ls1=1; ls1<i2; ls1++)
			{
				if (s1[ls1] != 0)
				{
					op++;
				}
			}

			if (op == 0)
			{
				cout << "\n произведение равно 0 \n";
				getch ();
				return 0;
			}
		}


		//2
		printf (" \n\n Введите второе число\n ");
		h=getche ();

		ls2=0;
		while ( h != 13)
			{ 
				s2[ls2] = h-48;
				ls2++;
				h = getche ();
			}
		if (sc != 0)
		{
			cout << "\n Ошибка ввода, [ENTER] для продолжения\n";
			getch ();
			return 0;
		}

		i2=ls2;
		if (s2[0] == 0)
		{
			for (ls2=1; ls2<i2; ls2++)
			{
				if (s2[ls2] != 0)
				{
					op++;
				}
			}

			if (op == 0)
			{
				cout << "\n произведение равно 0 \n";
				getch ();
				return 0;
			}
		}

		vector<short> a(ls1);
		vector<short> b(ls2);
		// !
	unsigned int start_time =  clock(); //начальное время
		a=preobraz_to_vector(s1, ls1, a);
		b=preobraz_to_vector(s2, ls2, b);

		vector<short> res;

		multiply (a, b, res);

		s=(char*)calloc(ls1+ls2,1);
		s=vector_to_obrpreobraz(res);

		cout << "\n Результат умножения:\n";
		indexs=0;
		cout << endl;
		for (index=0; s[indexs] != -1; index++)
		{
			chs =s[indexs];
			indexs++;
			cout << chs;
		}
		cout << "\n\n";
    unsigned int end_time = clock(); //конечное время
    unsigned int search_time = end_time - start_time; //затраченное 
	cout << "Затраченное время:" << search_time/1000.0 << "секунды" << endl;
		free(s1);
		free(s2);
		s=(char*)calloc(1,1);
		free(s);

		return 0;
	}
};

//***

int main()
{
	NUM mult; 
	setlocale(LC_ALL, "Russian");

	mult.fourie ();

	getch();
	return 0;
}
Семоха Валерий вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация программы GoldSieg Паскаль, Turbo Pascal, PascalABC.NET 17 22.05.2012 13:33
оптимизация программы Arsenx777 Работа с сетью в Delphi 1 28.08.2011 14:00
Оптимизация программы 0479 Помощь студентам 7 09.03.2011 17:15
Оптимизация программы Lenya Помощь студентам 2 05.01.2011 18:56