метод Ньютона для решения нелинейных уравнений
Мне было дано такое задание: реализовать метод Ньютона для решения нелинейных уравнений, чтобы в итоге на экран выводилось: значение неизвестной, количество итераций, потребовавшихся для нахождения решения, а также время затраченное на нахождения ответа.
Я попробовал написать:
Код:
//#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
float f (float);
float df (float);
int main(int argc, char* argv[])
{
float x0,xk,a,b,e;
int count = 0;
cout<<"Vvedite à:"<<endl;
cin>>a;
cout<<"Vvedite b:"<<endl;
cin>>b;
cout<<"Vvedite x0:"<<endl;
cin>>x0;
cout<<"Vvedite e:"<<endl;
cin>>e;
while ( fabs(xk-x0)> e )
{
xk=x0-((f(x0))/(df(x0))) ;
cout << count <<"-iter = " << xk << endl;
count++;
}
getch();
system("pause");
return 0;
}
float f (float x)
{
// func
return (exp(x)+ x*x -2);
}
float df (float x)
// dif funk
{
return (exp(x)+ 2*x );
}
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
float f (float);
float df (float);
int main(int argc, char* argv[])
{
float x0,xk,a,b,e;
int count = 0;
cout<<"Vvedite à:"<<endl;
cin>>a;
cout<<"Vvedite b:"<<endl;
cin>>b;
cout<<"Vvedite x0:"<<endl;
cin>>x0;
cout<<"Vvedite e:"<<endl;
cin>>e;
while ( fabs(xk-x0)> e )
{
xk=x0-((f(x0))/(df(x0))) ;
cout << count <<"-iter = " << xk << endl;
count++;
}
getch();
system("pause");
return 0;
}
float f (float x)
{
// func
return (exp(x)+ x*x -2);
}
float df (float x)
// dif funk
{
return (exp(x)+ 2*x );
}
Но проблема в том, что цикл получается бесконечный и в связи с этим с количеством итераций проблема. Подскажите, пожалуйста, как исправить? И Что добавить, чтобы выводило время в наносекундах?
Код:
xk = x0;
while ( fabs(f(xk)) >= e )
{
xk=xk-((f(xk))/(df(xk))) ;
while ( fabs(f(xk)) >= e )
{
xk=xk-((f(xk))/(df(xk))) ;
Код:
#include <time.h>
//...
clock_t _time;
_time = clock();//запомним время ДО
//while (...
//{
//...
//}
_time = clock() - _time;//замерим время ПОСЛЕ и разность
cout << "time = " << (_time * 1e+6) << " ns" << endl;//время в мс умножаем на 1000000
//...
clock_t _time;
_time = clock();//запомним время ДО
//while (...
//{
//...
//}
_time = clock() - _time;//замерим время ПОСЛЕ и разность
cout << "time = " << (_time * 1e+6) << " ns" << endl;//время в мс умножаем на 1000000
Код:
cout << count <<"-iter = " << xk << endl;
Второе. Чтобы измерить время исполнения быстрого кода, обычно этот код помещают в цикл и замеряют время цикла. Функцию вам уже для этого подсказали. Я в винде обычно для замера милисекунд использую GetTickCount(). Потом вы можете время цикла перевести в наносекунды и поделить на число повтрений цикла. Получите искомое время (правильней сказать его среднее значение). Этот способ не лишен погрешности - сам цикл потребляет некоторое время. Можно и эту погрешность победить.
Третье. Если ваш препод изувер и требует измерить время напрямую (без зацикливания кода) -- вам светит гемор с подсчетом числа тактов выполнения на ассемблере и с пересчетом числа тактов в интервал времени. Для чего потребуется еще гемор - вычисление частоты. Но, думаю, вряд ли от вас требуется такое.
PS С помощью библиотеки time можно и микросекундное разрешение получить (насколько это точно - не знаю).
Цитата: sadovoya
вам светит гемор с подсчетом числа тактов выполнения на ассемблере и с пересчетом числа тактов в интервал времени
Зачем такой гемор-то? :) QueryPerformanceFrequency же.
Цитата: @pixo $oft
Цитата: sadovoya
вам светит гемор с подсчетом числа тактов выполнения на ассемблере и с пересчетом числа тактов в интервал времени
Зачем такой гемор-то? :) QueryPerformanceFrequency же.
В чём вообще профит замерять время на
эйн: системы с вымещающей многозадачностью;
звей: малых выборках, не используя статистические методы.
[offtop]
@pixo $oft, эт не критика в твой адрес. :)
[/offtop]
Код:
;ml /c /coff rdtsc-ex.asm
;(po)link /subsystem:console rdtsc-ex.obj
;
;По "мотивам" Фрога.
.586 ;как минимум
.model flat,stdcall
option casemap:none
include \masm32\include\windows.inc ; main windows include file
include \masm32\include\masm32.inc ; masm32 library include
include \masm32\include\kernel32.inc
include \masm32\include\msvcrt.inc ; printf
include \masm32\macros\macros.asm ; masm32 macro file
includelib \masm32\lib\masm32.lib ; masm32 static library
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\msvcrt.lib
.data
clock_lo dd ?
hProcess dd ?
.code
_start:
SetConsoleCaption "Test with RDTSC"
invoke GetCurrentProcess
mov hProcess,eax
invoke SetPriorityClass, hProcess, REALTIME_PRIORITY_CLASS
cmp eax,0
jne go
printf("Can not set realtime..\n")
go:
xor eax,eax
cpuid
rdtsc
mov clock_lo,eax
;=============сюда тестиуемый код================
REPT 250
imul eax,1
ENDM
;================================================
xor eax,eax
cpuid
rdtsc
sub eax,clock_lo
jc carry
xchg eax,clock_lo
printf("All ticks is %u\n",clock_lo)
carry:
invoke SetPriorityClass, hProcess, NORMAL_PRIORITY_CLASS
invoke Sleep,1000
;inkey
exit
end _start
;(po)link /subsystem:console rdtsc-ex.obj
;
;По "мотивам" Фрога.
.586 ;как минимум
.model flat,stdcall
option casemap:none
include \masm32\include\windows.inc ; main windows include file
include \masm32\include\masm32.inc ; masm32 library include
include \masm32\include\kernel32.inc
include \masm32\include\msvcrt.inc ; printf
include \masm32\macros\macros.asm ; masm32 macro file
includelib \masm32\lib\masm32.lib ; masm32 static library
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\msvcrt.lib
.data
clock_lo dd ?
hProcess dd ?
.code
_start:
SetConsoleCaption "Test with RDTSC"
invoke GetCurrentProcess
mov hProcess,eax
invoke SetPriorityClass, hProcess, REALTIME_PRIORITY_CLASS
cmp eax,0
jne go
printf("Can not set realtime..\n")
go:
xor eax,eax
cpuid
rdtsc
mov clock_lo,eax
;=============сюда тестиуемый код================
REPT 250
imul eax,1
ENDM
;================================================
xor eax,eax
cpuid
rdtsc
sub eax,clock_lo
jc carry
xchg eax,clock_lo
printf("All ticks is %u\n",clock_lo)
carry:
invoke SetPriorityClass, hProcess, NORMAL_PRIORITY_CLASS
invoke Sleep,1000
;inkey
exit
end _start
PS. О всех возможных проблемах такого подхода (через rdtsc) много чего написано, даже в Wikipedia. Здесь часть проблем смягчена reatime и самой скоростью процесса. Но, лучше почитать литературу. Другое неприятно - пустой тест проходит за примерно 200 тактов (значит порядка 100 нс на 2ГГц процессоре). Тут есть о чем подумать. Или почитать Фрога :)
По поводу QueryPerformanceFrequency -- с ней разве наносекунды получишь?
Код:
;ml /c /coff timer-ex.asm
;(po)link /subsystem:console timer-ex.obj
comment %
Таймер на основе QueryPerformanceFrequency/QueryPerformanceCounter
Важное замечание - предполагается, что код быстрый и счетчик не успевает переполнить
младшее 32-битное значение. Но есть вероятность, что запуск кода попадает на это
событие. Поэтому, если "не повезло", то просто по состоянию carry флага программа
уходит в exit.
%
.386 ;как минимум
.model flat,stdcall
option casemap:none
include \masm32\include\windows.inc ; main windows include file
include \masm32\include\masm32.inc ; masm32 library include
include \masm32\include\kernel32.inc
include \masm32\include\msvcrt.inc ; printf
include \masm32\macros\macros.asm ; masm32 macro file
includelib \masm32\lib\masm32.lib ; masm32 static library
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\msvcrt.lib
.data
clock_lo dd ?
hProcess dd ?
x qword ?
.code
_start:
SetConsoleCaption "Test with QueryPerformanceCounter"
invoke GetCurrentProcess
mov hProcess,eax
invoke SetPriorityClass, hProcess, REALTIME_PRIORITY_CLASS
cmp eax,0
jne go
printf("Can not set realtime..\n")
go:
invoke QueryPerformanceFrequency, addr x
printf("Timer Freq. is %u\n", dword ptr x);
invoke QueryPerformanceCounter, addr x
mov eax,dword ptr x
mov clock_lo,eax
;=============сюда тестиуемый код================
;REPT 1000
;imul eax,1
;ENDM
;================================================
invoke QueryPerformanceCounter, addr x
mov eax,dword ptr x
sub eax,clock_lo
jc carry
xchg eax,clock_lo
printf("All ticks is %u\n",clock_lo)
carry:
invoke SetPriorityClass, hProcess, NORMAL_PRIORITY_CLASS
invoke Sleep,1000
;inkey
exit
end _start
;(po)link /subsystem:console timer-ex.obj
comment %
Таймер на основе QueryPerformanceFrequency/QueryPerformanceCounter
Важное замечание - предполагается, что код быстрый и счетчик не успевает переполнить
младшее 32-битное значение. Но есть вероятность, что запуск кода попадает на это
событие. Поэтому, если "не повезло", то просто по состоянию carry флага программа
уходит в exit.
%
.386 ;как минимум
.model flat,stdcall
option casemap:none
include \masm32\include\windows.inc ; main windows include file
include \masm32\include\masm32.inc ; masm32 library include
include \masm32\include\kernel32.inc
include \masm32\include\msvcrt.inc ; printf
include \masm32\macros\macros.asm ; masm32 macro file
includelib \masm32\lib\masm32.lib ; masm32 static library
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\msvcrt.lib
.data
clock_lo dd ?
hProcess dd ?
x qword ?
.code
_start:
SetConsoleCaption "Test with QueryPerformanceCounter"
invoke GetCurrentProcess
mov hProcess,eax
invoke SetPriorityClass, hProcess, REALTIME_PRIORITY_CLASS
cmp eax,0
jne go
printf("Can not set realtime..\n")
go:
invoke QueryPerformanceFrequency, addr x
printf("Timer Freq. is %u\n", dword ptr x);
invoke QueryPerformanceCounter, addr x
mov eax,dword ptr x
mov clock_lo,eax
;=============сюда тестиуемый код================
;REPT 1000
;imul eax,1
;ENDM
;================================================
invoke QueryPerformanceCounter, addr x
mov eax,dword ptr x
sub eax,clock_lo
jc carry
xchg eax,clock_lo
printf("All ticks is %u\n",clock_lo)
carry:
invoke SetPriorityClass, hProcess, NORMAL_PRIORITY_CLASS
invoke Sleep,1000
;inkey
exit
end _start
P.S. Для частоты достаточно нижнего dword структуры, что использовано в коде. На C++ код с использованием "полнного" 64-битного поля дал те-же результаты. Вот этот код на С++:
Код:
#include <iostream>
#include <windows.h>
using namespace std;
int main(int argc, char **argv)
{
LARGE_INTEGER timerFrequency, timerStart, timerStop;
QueryPerformanceFrequency(&timerFrequency);
QueryPerformanceCounter(&timerStart);
//
//Здесь код, время работы которого замеряем
//
QueryPerformanceCounter(&timerStop);
double ticks1 = static_cast<double>(timerStart.QuadPart);
double ticks2 = static_cast<double>(timerStop.QuadPart);
double freq = static_cast<double>(timerFrequency.QuadPart);
double dt = (ticks2 - ticks1)/freq;
cout << "Freq. is " << freq << " Hz"<< endl;
cout << "All ticks is " << ticks2-ticks1 << endl;
cout << "All time is " << dt << " sec" << endl;
return 0;
}
#include <windows.h>
using namespace std;
int main(int argc, char **argv)
{
LARGE_INTEGER timerFrequency, timerStart, timerStop;
QueryPerformanceFrequency(&timerFrequency);
QueryPerformanceCounter(&timerStart);
//
//Здесь код, время работы которого замеряем
//
QueryPerformanceCounter(&timerStop);
double ticks1 = static_cast<double>(timerStart.QuadPart);
double ticks2 = static_cast<double>(timerStop.QuadPart);
double freq = static_cast<double>(timerFrequency.QuadPart);
double dt = (ticks2 - ticks1)/freq;
cout << "Freq. is " << freq << " Hz"<< endl;
cout << "All ticks is " << ticks2-ticks1 << endl;
cout << "All time is " << dt << " sec" << endl;
return 0;
}
GetTickCount - Возвращает количество миллисекунд, прошедших с момента запуска системы, до 49,7 дней.
QueryPerformanceFrequency - Не плохо, но наносекундную точность не получить. В современных системах частота может меняться в момент выполнения кода.
Про микросекунды ещё можно поговорить.
Проблема нестабильной частоты и перескоков - для rdtsc актуальна еще в большей степени. По большому счету про наносекунды лучше забыть :) А в контексте мануалов Фрога вообще и про оптимизацию :)
"ПРЕДУПРЕЖДЕНИЕ: ИСПОЛЬЗОВАНИЕ КОДА В ДАННОЙ СТАТЬЕ НАХОДИТСЯ НА СВОЙ СТРАХ И РИСК. Корпорация Майкрософт предоставляет этот код «как есть» без никаких гарантий, явных или подразумеваемых, включая, помимо прочего, подразумеваемые гарантии товарности или пригодности для определенной цели."
И выкладывают код на бэйсике с использованием QueryPerformanceFrequency, QueryPerformanceCounter, GetTickCount, timeGetTime.
В итоге у них получилось:
"Минимальное разрешение функции QueryPerformanceCounter: 1/1193182 сек (что равно - 8,3809511038550698887512550474278E-07)
Накладные расходы API: 1.92761875388667E-05 сек
"
Так что я думаю что препод всёже пошутил )))
Тоже читал их статейки, видимо не спроста от ответственности отнекиваются :) Преподу - респект, шутка удалась :)
int count = 0;
cout<<"Vvedite à:"<<endl;
cin>>a;
cout<<"Vvedite b:"<<endl;
cin>>b;
cout<<"Vvedite x0:"<<endl; = // здесь попробуйте плиз значения поменять и кое что добавить
cin>>x0;
cout<<"Vvedite e:"<<endl;
cin>>e;
while ( fabs(xk-x0)> e )
{
Код:
#include <iostream>
#include <ctime>
#include <cstdio>
//Линковать с -lrt
//Таймер на clock_gettime()
timespec res = {0}, t1 = {0}, t2 = {0};
const int mlrd = 1000000000;
int main(int argc, char **argv)
{
clock_getres(CLOCK_REALTIME, &res); //можно и др.
printf("Разрешение [с:нс] = %lu : %lu\n",res.tv_sec, res.tv_nsec);
clock_gettime(CLOCK_REALTIME, &t1);
//===================Сюда тестируемый код==================================
//=========================================================================
clock_gettime(CLOCK_REALTIME, &t2);
printf("Потрачено [нс] = %ld\n",(t2.tv_sec-t1.tv_sec)*mlrd + t2.tv_nsec - t1.tv_nsec);
return 0;
}
#include <ctime>
#include <cstdio>
//Линковать с -lrt
//Таймер на clock_gettime()
timespec res = {0}, t1 = {0}, t2 = {0};
const int mlrd = 1000000000;
int main(int argc, char **argv)
{
clock_getres(CLOCK_REALTIME, &res); //можно и др.
printf("Разрешение [с:нс] = %lu : %lu\n",res.tv_sec, res.tv_nsec);
clock_gettime(CLOCK_REALTIME, &t1);
//===================Сюда тестируемый код==================================
//=========================================================================
clock_gettime(CLOCK_REALTIME, &t2);
printf("Потрачено [нс] = %ld\n",(t2.tv_sec-t1.tv_sec)*mlrd + t2.tv_nsec - t1.tv_nsec);
return 0;
}
<041C><0410><0422><0415><041C><0410><0422><0418><041A><0423><0020><0421><041F><0410><0421><0418><0411><041E><0020><041E><0422><0020><041C><0415><041D><042F><002C><0020><0415><0413><041E><0020><041C><0415><0427><0422><0410><0020><0412><041E><0417><0412><0420><0410><0429><0410><0415><0422><0421><042F><0020><041A><0020><041D><0415><041C><0423><0020><0420><0415><0410><041B><042C><041D><041E><0421><0422><042C><042E><0021><0021><0021><0020><041E><041D><0410><0020><0415><0413><041E><0020><041B><042E><0411><0418><0422><0021><0021><0021><0020><041F><0420><041E><0421><0422><041E><0020><0412><0420><0415><041C><042F><0020><041D><0423><0416><041D><041E><0021><0021><0021><0020><041F><041E><0422><0415><0420><041F><0415><0422><042C><0021><0021><0021><0020>
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
float f (float);
float df (float);
int main(int argc, char* argv[])
{
float 8888,a,b,xk,e;
int count = 12;
cout<<"Vvedite HK03:"<<endl;
cin>>a;
cout<<"Vvedite HK06:"<<endl;
cin>>b;
cout<<"Vvedite 1CA8:"<<endl;
cin>>1111;
cout<<"Vvedite HK08:"<<endl;
cin>>e;
while ( fabs(xk-x1)> e )
}
{
xk=x1-((f(x2))/(df(x6))) ;
cout << count <<"-iter = " << xk << go to = count++;
}
{
getch();
system("pause");
return 111H1;
float f (float x1CA8)
{
func while ( fabs(xk-x1)> e )
return (exp(5)+ 1*8} -2);
float 8888,a,b,xk,e;
int count = 15
return;
}
{
float df (float x72657475726E202865787028)
dif funk if x0+HK03*(exp(5)+ 1*8} -2) << "-iter = " << xk << go to = count++
return (exp(5)+ 1*8} -2);
Теоретически одному не вычислять прошу, только с помощниками!!!