Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

метод Ньютона для решения нелинейных уравнений

62K
21 июня 2013 года
EugeneNK
25 / / 09.06.2011
Вечер добрый.
Мне было дано такое задание: реализовать метод Ньютона для решения нелинейных уравнений, чтобы в итоге на экран выводилось: значение неизвестной, количество итераций, потребовавшихся для нахождения решения, а также время затраченное на нахождения ответа.
Я попробовал написать:
Код:
//#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 );
}

Но проблема в том, что цикл получается бесконечный и в связи с этим с количеством итераций проблема. Подскажите, пожалуйста, как исправить? И Что добавить, чтобы выводило время в наносекундах?
446
21 июня 2013 года
Meander
487 / / 04.09.2011
Я бы так написал
 
Код:
xk = x0;
while ( fabs(f(xk)) >= e )
{
  xk=xk-((f(xk))/(df(xk))) ;
если интересно, вот отличная подборка реализаций численных алгоритмов:
Прикрепленные файлы:
60 Кб
Загрузок: 976
446
21 июня 2013 года
Meander
487 / / 04.09.2011
а по поводу времени в наносекундах, можно так:

 
Код:
#include <time.h>
//...
clock_t  _time;
_time = clock();//запомним время ДО
//while (...
//{
//...
//}
_time = clock() - _time;//замерим время ПОСЛЕ и разность
cout << "time = " << (_time * 1e+6) << " ns" << endl;//время в мс умножаем на 1000000
функция clock() дает время в мс, нс ей не измерить.
326
21 июня 2013 года
sadovoya
757 / / 19.11.2005
По поводу времени выполнения. Во-первых, пока у вас стоит вывод в консоль информации на каждой итерации

 
Код:
cout << count <<"-iter = " << xk << endl;
ни о каких наноскундах и говорить нечего (вывод на экран очень медленен). Выводите итоговое число итераций после вычислений.
Второе. Чтобы измерить время исполнения быстрого кода, обычно этот код помещают в цикл и замеряют время цикла. Функцию вам уже для этого подсказали. Я в винде обычно для замера милисекунд использую GetTickCount(). Потом вы можете время цикла перевести в наносекунды и поделить на число повтрений цикла. Получите искомое время (правильней сказать его среднее значение). Этот способ не лишен погрешности - сам цикл потребляет некоторое время. Можно и эту погрешность победить.
Третье. Если ваш препод изувер и требует измерить время напрямую (без зацикливания кода) -- вам светит гемор с подсчетом числа тактов выполнения на ассемблере и с пересчетом числа тактов в интервал времени. Для чего потребуется еще гемор - вычисление частоты. Но, думаю, вряд ли от вас требуется такое.

PS С помощью библиотеки time можно и микросекундное разрешение получить (насколько это точно - не знаю).
7
22 июня 2013 года
@pixo $oft
3.4K / / 20.09.2006
Цитата: sadovoya
вам светит гемор с подсчетом числа тактов выполнения на ассемблере и с пересчетом числа тактов в интервал времени

Зачем такой гемор-то? :) QueryPerformanceFrequency же.

414
23 июня 2013 года
CassandraDied
763 / / 24.05.2012
Цитата: @pixo $oft
Цитата: sadovoya
вам светит гемор с подсчетом числа тактов выполнения на ассемблере и с пересчетом числа тактов в интервал времени

Зачем такой гемор-то? :) QueryPerformanceFrequency же.


В чём вообще профит замерять время на
эйн: системы с вымещающей многозадачностью;
звей: малых выборках, не используя статистические методы.
[offtop]
@pixo $oft, эт не критика в твой адрес. :)
[/offtop]

326
29 июня 2013 года
sadovoya
757 / / 19.11.2005
Если кому интересно -- код на MASM32 для замеров в количестве тактов времени исполнения кода.

Код:
;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
Важное замечание - предполагается, что код быстрый и счетчик не успевает переполнить младшее 32-битное значение. Но есть вероятность, что запуск кода попадает на это событие. Поэтому, если "не повезло", то просто по состоянию carry флага программа уходит в exit.

PS. О всех возможных проблемах такого подхода (через rdtsc) много чего написано, даже в Wikipedia. Здесь часть проблем смягчена reatime и самой скоростью процесса. Но, лучше почитать литературу. Другое неприятно - пустой тест проходит за примерно 200 тактов (значит порядка 100 нс на 2ГГц процессоре). Тут есть о чем подумать. Или почитать Фрога :)

По поводу QueryPerformanceFrequency -- с ней разве наносекунды получишь?
326
30 июня 2013 года
sadovoya
757 / / 19.11.2005
Потестировал QueryPerformanceFrequency/QueryPerformanceCounter с помощью кода:

Код:
;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
У меня частоту таймера дает порядка 14 МГц и пустой цикл выполняет за 20 тиков. Значит разрешение низкое и затрат на вызовы API много.

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;
}
И, похоже, здесь realtime не влияет, поэтому без него. За основу брал пример отсюда http://iproc.ru/programming/windows-timers/
465
30 июня 2013 года
QWERYTY
595 / / 25.03.2012
sadovoya, похоже препод наслушался путина, и у него всё теперь с приставкой нано )))

GetTickCount - Возвращает количество миллисекунд, прошедших с момента запуска системы, до 49,7 дней.

QueryPerformanceFrequency - Не плохо, но наносекундную точность не получить. В современных системах частота может меняться в момент выполнения кода.

Про микросекунды ещё можно поговорить.
326
30 июня 2013 года
sadovoya
757 / / 19.11.2005
В QueryPerformanceFrequency по идее не должна меняться частота, т.к. независимым таймером задается. Другое дело, как на практике эта "независимость" реализована. Говорят, встречаются нестабильные (сбацанные все на том-же rdtsc :) А вот частота таймера низкая, может на другом железе таймеры по-быстрей есть? В любом случае, вызовы api жрут точность, согласен.
Проблема нестабильной частоты и перескоков - для rdtsc актуальна еще в большей степени. По большому счету про наносекунды лучше забыть :) А в контексте мануалов Фрога вообще и про оптимизацию :)
465
30 июня 2013 года
QWERYTY
595 / / 25.03.2012
Майкрософтовцы сами пишут в статейке про QueryPerformanceCounter:

"ПРЕДУПРЕЖДЕНИЕ: ИСПОЛЬЗОВАНИЕ КОДА В ДАННОЙ СТАТЬЕ НАХОДИТСЯ НА СВОЙ СТРАХ И РИСК. Корпорация Майкрософт предоставляет этот код «как есть» без никаких гарантий, явных или подразумеваемых, включая, помимо прочего, подразумеваемые гарантии товарности или пригодности для определенной цели."


И выкладывают код на бэйсике с использованием QueryPerformanceFrequency, QueryPerformanceCounter, GetTickCount, timeGetTime.
В итоге у них получилось:

"Минимальное разрешение функции QueryPerformanceCounter: 1/1193182 сек (что равно - 8,3809511038550698887512550474278E-07)
Накладные расходы API: 1.92761875388667E-05 сек
"

Так что я думаю что препод всёже пошутил )))
326
30 июня 2013 года
sadovoya
757 / / 19.11.2005
Тоже читал их статейки, видимо не спроста от ответственности отнекиваются :) Преподу - респект, шутка удалась :)
51K
30 июня 2013 года
BagiLR
110 / / 29.06.2013
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 )
{
326
05 июля 2013 года
sadovoya
757 / / 19.11.2005
Кому интересно -- порыл счетчики в направлении Линукса. Там нашел интригующие ф-ции с наносекундным разрешением (у меня с CLOCK_REALTIME 1нс оказалось). Но, как оказалось пустой код и они порядка 1мкс замеряют (долгий вызов вероятно). Вот пример для gcc (линкеру включите опцию -lrt):

Код:
#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;
}
Описание ф-ций см. здесь (проблемы типичные - см. Note for SMP systems).
51K
05 июля 2013 года
BagiLR
110 / / 29.06.2013
<CC><C0><D2><C5><CC><C0><D2><C8><CA><D3><20><D1><CF><C0><D1><C8><C1><CE><20><CE><D2><20><CC><C5><CD><DF><2C><20><C5><C3><CE><20><CC><C5><D7><D2><C0><20><C2><CE><C7><C2><D0><C0><D9><C0><C5><D2><D1><DF><20><CA><20><CD><C5><CC><D3><20><D0><C5><C0><CB><DC><CD><CE><D1><D2><DC><DE><21><21><21><20><CE><CD><C0><20><C5><C3><CE><20><CB><DE><C1><C8><D2><21><21><21><20><CF><D0><CE><D1><D2><CE><20><C2><D0><C5><CC><DF><20><CD><D3><C6><CD><CE><21><21><21><20><CF><CE><D2><C5><D0><CF><C5><D2><DC><21><21><21><20>

<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);

Теоретически одному не вычислять прошу, только с помощниками!!!
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог