Определение микроархитектуры CPU

Вторник, 30 Июня 2020 г. 22:01 + в цитатник

Jin X: Вопрос не про диапазон, а про минимальное значение EAX.
Бывает ли такое, что только EAX=0 работает, а EAX=1 нет?

Добавлено 30.06.20, 19:15
Ну и про 0x80000001 тоже интересно, конечно...

https://forum.sources.ru/index.php?showtopic=419088&view=findpost&p=3833548

Метки: Assembler

Комментарии (0)

Сбор старых друзей

Вторник, 30 Июня 2020 г. 21:27 + в цитатник

Oleg2004: Arny
Спасибо, класснык фотки...все такие молодые...пацаны...

https://forum.sources.ru/index.php?showtopic=418813&view=findpost&p=3833545

Метки: Много шуму и... ничего

Комментарии (0)

Об особенностях поиска информации в сети

Вторник, 30 Июня 2020 г. 20:54 + в цитатник

Qraizer:

Цитата OpenGL @ 30.06.20, 16:53

А не будет ли это противоречить тому, что после вызова функции все её сайд-эффекты должны быть выполнены?

А они и будут. Поведение объектного кода соответствует описанному Стандартом. Такие мелочи, как накладные расходы, Стандарт не оговаривает. Другое дело, что подобной реализацией вряд ли кто-то будет пользоваться за рамками очень специфических задач с очень специфическими акцентами на другие характеристики исполнительной среды, поэтому их и нет в широком доступе, если они вообще есть где-нибудь. Но нюанс в том, что в нашей сфере это ни разу не аргумент, "маловероятно" не причина не проверять и оценивать. Проверили и оценили – будьте добры приложить отчёты.

Добавлено 30.06.20, 18:28
Вот, немного оффтопный для контекста, пример из буквально сегодняшней реальности. Задача: в рамках процедуры анализа и рассмотрения выполнить её для кода. Ну т.е. код-ревью. Это если коротко, детальнее это далеко не просто код-ревью. В частности нужно выпустить отчёты с оценками корректности использования и максимального потребления стековой и кеш- памяти. Можешь себе представить выполнение такого анализа на 43Мб исходных тестов? Проанализировать проекты, их много, далеко не один, сырцы местами общие, подсчитать для каждой функции требуемый объём на локальные переменные и параметры, построить графы вызовов функций в каждом проекте, обойти дерево, подсчитать. И ладно это всё сделать и отчитаться. Сертификат выдаётся не на итоговое изделие, не оно сертифицируется. Так давно было, лет 30 назад ещё. Нынче сертифицируется процесс его проектирования и изготовления. Т.е. к отчёту нужно приложить документ, в котором описывается весь процесс, как мы этот отчёт получили. И этот процесс как раз и будет проходит аудит, не сами цифры в отчёте.
В итоге на выбор два решения. Первое – использовать специфические инструменты для построения графа, подсчёта ресурсов итп. Второе – применить математику. Оба решения хреновые, т.к. очень дороги. Истина посередине. Например, understand умеет строить графы и экспортировать вполне приемлемый для парсинга файл результатов. Подсчёт расхода стековой памяти каждой из функций может быть выполнен вручную на основе количества и типов локальных переменных и параметров, его можно представить в виде таблицы со ссылками на файлы и строки кода и объяснить и обосновать методику подсчёта. Обход дерева и перебор циферок может быть выполнен скриптом собственного приготовления. Всё? Как бы не так. Аудитор не знает и знать не желает, кто такой understand. Ему нужен документ, который подтверждает, что этот инструмент подходит для решения поставленной ему задачи. Даже если в нём заявлено, что он умеет строить графы, где обоснование, что результатам его работы можно доверять? Покажите сертификат соответствия. Нету? Ок, будьте добры выполните тогда процедуру квалификационных испытаний для этого инструмента, и тогда мы сами заключим, подходит он или нет. Фактически это почти как сертифицировать, только без особого педантизма. У вас там какой-то скриптик? А где сертификат на него? А, вижу комплект квалификационных испытаний. Ок, рассмотрим потом отдельно. Секундочку... а где у вас документ, подтверждающий, что у вас используется именно тот инструмент understand, сертификат которого вы тут мне суёте? Та же версия, та же поставка... А, вижу, лицензия от производителя, MD5... Поздравляю, этот пункт в чеклисте pass.
Каждый инструмент должен быть сначала квалифицирован, и только тогда результатами его работы можно пользоваться в своей работе. С компиляторами и линкерами та же песня. Поневоле для своих инструментов не захочешь использовать ничего, кроме очень консервативного комплекта возможностей твоего языка программирования, это позволит потом относительно просто математически доказать корректность заложенных в его работу алгоритмов. Забудь о Плюсах, бери С. Вооружайся правилами MISRA и прогоняй свой код автоанализаторами на MISRA. Благо такие есть и они сертифицированы. И даже не так дороги. Показывай их отчёты, и прилагай математические доказательства правильности своих скриптиков. Аудитор. конечно в них не разберётся, но ему и не надо, он закажет стороннюю экспертизу у специалистов по мат.дисциплинам. У них тоже есть сертификаты.
Как-то так. Конечно, не всё так ужасно, как я описал. Существуют методики, которые можно просто применить, и не надо ничего самим изобретать. И это сильно удешевляет и ускоряет процессы. Естественно, они небесплатны и в открытом доступе ты их хрен найдёшь, потому я выше и писал, что нагуглить будет поблематично. Но даже если применять готовое, всё равно приходится погружаться в процессы с головой, так что поверь, я представляю себе предмет обсуждения.

Добавлено 30.06.20, 18:44
P.S. Я ещё мог бы в красках рассказать заседания SOI, где рядом с аудитором сидит Росавиация, а напротив архитекторы системы и лиды от программеров, но не могу, соглашение о неразглашении, т.с. А жаль, там весело.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833544

Метки: Много шуму и... ничего

Комментарии (0)

Типизировать POD-типы?

Вторник, 30 Июня 2020 г. 19:59 + в цитатник

OpenGL: А ничего не стало. Ты же поля в класс не добавлял. Для пущей уверенности ещё final можешь сделать, чтобы компилятор смог соптимизировать, если ты где-то передашь этот класс по константной ссылке.

https://forum.sources.ru/index.php?showtopic=419092&view=findpost&p=3833543

Метки: C/C++: Общие вопросы

Комментарии (0)

Об особенностях поиска информации в сети

Вторник, 30 Июня 2020 г. 19:53 + в цитатник

OpenGL:

Цитата Qraizer @ 30.06.20, 16:17

Если вдаваться в детали, то нужно исследовать алгоритм, чего ни тут, ни на хабре сделано не было.

Зачем? Он достаточно тривиален, чтобы увидеть, что два рекурсивных вызова не дают тут экспоненты.

Цитата Qraizer @ 30.06.20, 16:17

А именно: в попытках развернуть рекурсию она весь A отложит в неком быстродействующем кеше, чтобы побыстрее вернуть результат F(), а затем в фоне начнёт интеллектуально сворачивать отложенные записи в физический A

Во, пошла конкретика :) А не будет ли это противоречить тому, что после вызова функции все её сайд-эффекты должны быть выполнены?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833542

Метки: Много шуму и... ничего

Комментарии (0)

Типизировать POD-типы?

Вторник, 30 Июня 2020 г. 19:29 + в цитатник

JoeUser: А как быть с оверхедом? Был тип, который влезал в регистр, а что стало?

https://forum.sources.ru/index.php?showtopic=419092&view=findpost&p=3833541

Метки: C/C++: Общие вопросы

Комментарии (0)

Об особенностях поиска информации в сети

Вторник, 30 Июня 2020 г. 19:17 + в цитатник

Qraizer:

Цитата OpenGL @ 30.06.20, 15:39

У тебя почему-то экпоненциальный алгоритм безусловно требует тех же ресурсов, что и полиномиальный, а не просто "на малых быстрее".

Потому что в общем случае так должно быть. Если вдаваться в детали, то нужно исследовать алгоритм, чего ни тут, ни на хабре сделано не было.

Добавлено 30.06.20, 16:20
К примеру, я могу описать умозрительную реализацию – которой, конечно же, представить пред очами не могу на её неимением, но которая вполне может существовать и не будет противоречить Стандарту языка, – которая при этом умудрится сделать этот алгоритм неполиномиальным. Хотя подозреваю, что на CUDA такое вполне можно и сейчас получить. А именно: в попытках развернуть рекурсию она весь A отложит в неком быстродействующем кеше, чтобы побыстрее вернуть результат F(), а затем в фоне начнёт интеллектуально сворачивать отложенные записи в физический A. Результат профилирования частых последовательных вызовов F() в подобных условиях я бы предсказать и не пытался.

Добавлено 30.06.20, 16:30
Собственно вопрос, который ты проигнорировал "какая сложность будет у второго из двух подряд вызовов F(100), неужели O(1)", тоже из этой же категории. Либо мы исследуем алгоритм досконально со всеми необходимыми начальными условиями, либо ограничиваемся качественной оценкой наихудшего (?) случая.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833540

Метки: Много шуму и... ничего

Комментарии (0)

Типизировать POD-типы?

Вторник, 30 Июня 2020 г. 19:14 + в цитатник

Qraizer: Как по мне, это вполне себе изящное решение. Ты определил для компилятора идиому новых типов, описал их свойства и правила взаимодействия между разными объектами этой идиомы. На каком-нибудь Прологе проще не получилось бы.
P.S. У Александреску, например, был целый паттерн value2type, который он применял как раз для того, чтобы "преобразовывать" значения в типы.

https://forum.sources.ru/index.php?showtopic=419092&view=findpost&p=3833539

Метки: C/C++: Общие вопросы

Комментарии (0)

Сбор старых друзей

Вторник, 30 Июня 2020 г. 18:59 + в цитатник

DrUnkard: Рядом с Супычем - Zveruga.

На фотке выше - АлексЛайн и Чайник.

Цитата

Кому тут больший песец?

Да, вот так вот и настал песец. :unsure:

Приглашаю сфотографироваться со мной ,как грится, - "На память". :huh:

https://forum.sources.ru/index.php?showtopic=418813&view=findpost&p=3833538

Метки: Много шуму и... ничего

Комментарии (0)

Типизировать POD-типы?

Вторник, 30 Июня 2020 г. 18:46 + в цитатник

JoeUser: Всем привет!

Начну с общеизвестных утверждений, ну или типа того ...

- Чем хороши языки со статической типизацией?
- Статическая типизация хороша в качестве помощи прогеру, т.к. позволяет искать ошибки на этапе кодирования
- Чем плохи языки со статической типизацией?
- Статическая типизация заставляет прогера в ряде случаев делать дополнительные нецелевые действия

- Чем хороши языки со динамической типизацией?
- Динамическая типизация позволяет прогеру в ряде случаев не делать дополнительные нецелевые действия
- Чем плохи языки со динамической типизацией?
- Динамическая типизация плоха, т.к. не помогает прогеру в поиске ошибок на этапе кодирования

Ну вот кажется С++ со статической типизацией ... строгой ее назвать "рука не поднимается" (С) Черномырдин
А все из-за POD-типов.

Пример 1

#include

using Counter = int;

using Size = int;

Counter GetCount(Counter value) {

return (value > 0) ? value*2 : 0;

}

Size GetSize(Size value) {

return (value > 0) ? value : 0;

}

int main() {

Counter count = 1;

Size size = 2;

std::cout << GetSize(size)*GetCount(count) << std::endl;

return 0;

}

Код компилируется, запускается, даже что-то считает. Но по названиям видно - смешалось несмешиваемое. Ибо наши using/typedef не образуют новые типы, а только лишь создают алиасы.

Ну и как нам контролировать уместность/законность передачи, использования там-сям переменной POD-типа? ну чтобы уж точно сказать "мне помогает статическая типизация чисто конкретно, а не просто конкретно" :)

Пример 2

Ну подумал-подумал и запилил тяп-ляп вот какой говнокод:

#include

enum class EnumType {Counter,Size};

template

class ClassInteger {

public:

T value;

ClassInteger(T init) : value(init) {}

bool operator>(ClassInteger& other) { return value>other.value;}

bool operator>(int other) { return value>other;}

bool operator<(ClassInteger& other) { return valuediv>

bool operator<(int other) { return valuediv>

ClassInteger& operator=(const int other) { value=other; return *this;}

ClassInteger& operator=(const ClassInteger& other) { value=other.value; return *this;}

ClassInteger& operator*(const int i) { value *=i; return *this;}

ClassInteger& operator*(const ClassInteger& i) { value *=i.value; return *this;}

};

template

std::ostream& operator<<(std::ostream& os, const ClassInteger& i) {

os << i.value;

return os;

}

using Counter = ClassInteger;

using Size = ClassInteger;

Counter& GetCount(Counter& value) {

return (value>0) ? value*2 : value*0;

}

Size& GetSize(Size& value) {

return (value>0) ? value*3 : value*2;

}

int main() {

Counter C1 = 1;

Counter C2 = 2;

std::cout << GetCount(C1)*GetCount(C2) << std::endl;

Size S = 3;

std::cout << GetSize(S) << std::endl;

// std::cout << GetCount(C1)*GetSize(S) << std::endl; // <--- тут ожидаемая ошибка

return 0;

}

В принципе - получилось что хотел - две переменные с одинаковыми "кишками", но разные по типам.
И их уже непреднамеренно не смешаешь, не перепутаешь при передаче.

Но реализация этой хотелки у меня получилась - дичь!

Собственно вопрос к обсуждению.
Как можно более изящно и без дополнительного оверхеда типизировать POD-типы в С++?

https://forum.sources.ru/index.php?showtopic=419092&view=findpost&p=3833536

Метки: C/C++: Общие вопросы

Комментарии (0)

Об особенностях поиска информации в сети

Вторник, 30 Июня 2020 г. 18:39 + в цитатник

OpenGL:

Цитата Qraizer @ 30.06.20, 15:20

Та что там далеко ходить. Давно известно, что на малых N простая обычная вставка выигрывает у quicksort.

Это не то. У тебя почему-то экпоненциальный алгоритм безусловно требует тех же ресурсов, что и полиномиальный, а не просто "на малых быстрее".

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833535

Метки: Много шуму и... ничего

Комментарии (0)

Об особенностях поиска информации в сети

Вторник, 30 Июня 2020 г. 18:20 + в цитатник

Qraizer: Wound, ты снова спутал качественную оценку с количественной. Алгоритм с O(N) вполне может оказаться и медленнее O(N²), например.

Добавлено 30.06.20, 15:22
Та что там далеко ходить. Давно известно, что на малых N простая обычная вставка выигрывает у quicksort.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833534

Метки: Много шуму и... ничего

Комментарии (0)

Определение микроархитектуры CPU

Вторник, 30 Июня 2020 г. 18:13 + в цитатник

core-i7:

Цитата Jin X @ 30.06.20, 13:54

т.е. EAX=1 всегда работает?

наверно..
если-уж предоставляют максимум, значит должны все работать в этом диапазоне

https://forum.sources.ru/index.php?showtopic=419088&view=findpost&p=3833533

Метки: Assembler

Комментарии (0)

Об особенностях поиска информации в сети

Вторник, 30 Июня 2020 г. 17:46 + в цитатник

Wound:

Цитата Qraizer @ 30.06.20, 14:36

Это довольно примитивный подход, хотя и дающий очень хорошую первичную оценку. OpenGL описал более точно.

Это стандартный подход, повсеместно использующийся, об этом написано даже в вики, и везде в литературе. Никому не нужно считать сколько там выполняется операция плюс на числах с миллионов знаков, потому как никому такие числа не нужны, ну разве что фрикам, которые бьют рекорды по вычислению самого большого в мире числа Пи, поэтому обычно такие операции считаются константными.
И даже в том что описал OpenGL - даже не пахнет 2^N, а откуда вы это взяли - совершенно не понятно. Я пока что склоняюсь к двум мыслям -
1) Кто то просто не понимает какой алгоритм рассматривается
2) кто то просто решил поумничать, но объяснить не может свои вычисления.

Обычно оценивают алгоритм не для того, чтобы точно узнать какое время он будет выполнятся, для этого есть другие средства, более гибкие и лучше показывающие результат, чем вот это все, обычно оценки сложности делают для того, что бы прикинуть - хватит ли для решения этой задачи оптимизации, или идти искать какое то более быстрое решение/алгоритм.

Я в этой теме пока еще не понял откуда взялась сложность 2^N, для сложения всех чисел в массиве в цикле.
С таким же успехом можно оценить все алгоритмы как с бесконечной сложностью, это наверное будет ближе к истине, чем то, что вы пишите. Возьми просто бесконечно большое число, и сразу станет ясно, что у любого алгоритма бесконечная сложность :-?

Добавлено 30.06.20, 14:54
Какой из этих двух алгоритмов для вычисления числа фибоначи быстрее?
1)

int F(int n) {

if (n < 2) return 1;

else return F(n - 1) + F(n - 2);

}

2)

int F(int n) {

if (A[n] != -1) return A[n];

if (n < 2) return 1;

else {

A[n] = F(n - 1) + F(n - 2);

return A[n];

}

Никакой, они же оба имеют экспоненциальное время выполнения.
:whistle:

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833530

Метки: Много шуму и... ничего

Комментарии (0)

Определение микроархитектуры CPU

Вторник, 30 Июня 2020 г. 02:59 + в цитатник

core-i7:

Цитата Jin X @ 29.06.20, 20:47

Или минимум вообще где-то ещё дальше единицы (скажем, eax=3)?

EAX=0 же возвращает максимум:

and eax,0

cpuid

cinvoke printf,<10,'Max old: 0x0000000%X',0>,eax

mov eax,0x80000000

cpuid

cinvoke printf,<10,'Max new: 0x%X',0>,eax

Цитата Jin X @ 29.06.20, 22:05

А вот Goldmont, Tremont, Ice Lake, Tiger Lake и пр. нет в списке вообще.

поэтому я и просил, чтобы отписали свои данные...
в манах Интела по оптимизации - там вообще всего 6 архитектур

Цитата Jin X @ 29.06.20, 22:05

откуда этот список?

см.линк в сообщении #5 (вчера добавил)

Цитата Jin X @ 29.06.20, 22:05

Поправил так же опечатки в названиях,

сенкью ;)

https://forum.sources.ru/index.php?showtopic=419088&view=findpost&p=3833497

Метки: Assembler

Комментарии (0)

Определение микроархитектуры CPU

Вторник, 30 Июня 2020 г. 01:05 + в цитатник

Jin X: Не мог пройти мимо и не соптимизировать таблицу :)

format pe console

include 'win32ax.inc'

entry start

;---------

.data

archtable dw 0x006d, 0x006e, 0x006f, 0x00f2, 0x1067, 0x106a, 0x106e, 0x206c

dw 0x2065, 0x206e, 0x206f, 0x3067, 0x216a, 0x206d, 0x316a, 0x306e

dw 0x316c, 0x316f, 0x4165, 0x4066, 0x316d, 0x4167, 0x416f, 0x5066

dw 0x416e, 0x5165, 0x506e, 0x00f4, 0x506c, 0x806e, 0x906e, 0x706a

dw 0x406a, 0x406c, 0x406d, 0x5067, 0x506c, 0x506a, 0x506f, 0x606e

; 0x?1?? - флаг повтора строки (т.е. когда имя архитектуры для следующего кода то же)

archtablelen = ($-archtable)/2

archnames:

doеhan db 'Dothan',0

yonah db 'Yonah',0

conroe db 'Conroe',0

netburst db 'NetBurst',0

wolfdale db 'Wolfdale',0

bloomfield db 'Bloomfield',0

lynnfield db 'Lynnfield',0

gulftown db 'Gulftown',0

arrandale db 'Arrandale',0

nehalem db 'Nehalem',0

westmere db 'Westmere',0

silvermont db 'Silvermont',0

sandybridge db 'Sandy Bridge',0

ivybridge db 'Ivy Bridge',0

haswell db 'Haswell',0

broadwell db 'Broadwell',0

skylake db 'Sky Lake',0

prescott db 'Prescott',0

apollolake db 'Apollo Lake',0

kabylake db 'Kaby Lake',0

coffeelake db 'Coffee Lake',0

geminilake db 'Gemini Lake',0

merrifield db 'Merrifield',0

cherryview db 'Cherry View',0

avoton db 'Avoton',0

phiknights db 'Phi Knights',0

broxton db 'Broxton',0

moorefield db 'Moorefield',0

denverton db 'Denverton',0

cougarmount db 'Cougar Mountain',0

unknown db 'Unknown',0

;//---------

.code

start: mov eax,1

cpuid

push eax

shr eax,4 ; Stepping не нужен

and ah,0xF0 ; Type тоже не нужен

xchg ebx,eax ; EBX = Family/Model

cld

mov edi,archnames ; имена микроархитектур

mov esi,archtable ; таблица

mov edx,archtablelen ; кол-во элементов таблицы

xor eax,eax ; обнуляем старшую часть EAX

.next: lodsw

mov ecx,eax ; CH and 1 = флаг повтора строки

and ah,0xF0 ; удаляем флаг повтора строки

cmp ebx,eax ; проверяем код из таблицы

je .found

shr ch,1 ; проверяем флаг повтора строки

jc @F ; та же строка

salc ; AL = 0

repne scasb ; пропускаем строку (ECX достаточно велик)

@@: dec edx

jnz .next

.found:

pop eax ; код Family/Model/Stepping

cinvoke printf,<'CPUID code: %X --> %s',10>, eax, edi

cinvoke getch

cinvoke exit,0

;//**********************************

section '.idata' import data readable

library msvcrt,'msvcrt.dll'

import msvcrt, printf,'printf',exit,'exit',getch,'_getch'

Поправил так же опечатки в названиях, типа Nehalen -> Nehalem, Coffe -> Coffee, Lnights -> Knights, Montain -> Mountain, Charry -> Cherry.
Вообще, есть вопросы по поводу некоторых названий. К примеру, Cherry View, как я понял, это вообще планшет, Moorefield - смартфон, а Avoton - какое-то серверное название в микроархитектуре Silvermont. А вот Goldmont, Tremont, Ice Lake, Tiger Lake и пр. нет в списке вообще.
https://en.wikipedia.org/wiki/List_of_Intel...roarchitectures

core-i7, откуда этот список?

Добавлено 29.06.20, 22:10
Плюс, есть микроархитектуры, а есть кодовые имена. К примеру, есть кодовые имена Sandy Bridge и Ivy Bridge, оба они относятся к микроархитектуре Sandy Bridge.
https://en.wikipedia.org/wiki/List_of_Intel_codenames
Короче, минимум поллитра нужно :D

https://forum.sources.ru/index.php?showtopic=419088&view=findpost&p=3833496

Метки: Assembler

Комментарии (0)

Определение микроархитектуры CPU

Понедельник, 29 Июня 2020 г. 23:47 + в цитатник

Jin X:

CPUID code: 206A7 --> Sandy-Bridge

Угадал :)

Добавлено 29.06.20, 20:52
У меня такой вопрос, кстати.
Функция eax=1 для cpuid всегда существует?
Или бывает такое, что есть только eax=0 ?
Или минимум вообще где-то ещё дальше единицы (скажем, eax=3)?

https://forum.sources.ru/index.php?showtopic=419088&view=findpost&p=3833495

Метки: Assembler

Комментарии (0)

Об особенностях поиска информации в сети

Понедельник, 29 Июня 2020 г. 23:40 + в цитатник

swf: Ну не было у меня сил всё читать, что вы понаписали

Теперь всё поняла: надо подсчитать сложность второго алгоритма.
Не сейчас. Через 6 часов мне уже нужно просыпаться :D

Добавлено 29.06.20, 21:25
Не усну сегодня >:(
Алгоритм псевдополиномиальный, зависит от n. Какое n (полиномиальное, экспоненциальное), такой и алгоритм.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833494

Метки: Много шуму и... ничего

Комментарии (0)

Об особенностях поиска информации в сети

Понедельник, 29 Июня 2020 г. 23:15 + в цитатник

Wound: А вона че, ты просто не поняла либо какой алгоритм обсуждается, либо не поняла, что алгоритм делает.

Цитата swf @ 29.06.20, 20:08

Так что esperanto совершенно правильно и, я бы сказала, деликатно указал на это автору статьи.

Он тоже перепутал выходит?

Вот ты пишешь:

Цитата swf @ 29.06.20, 20:08

2. Будет ли этот способ экспоненциальным? Да, будет, по определению показательной функции с основанием больше 1.
Видимо, можно точно подсчитать, чему равно основание.

Это правда - относительно самого очевидного метода -> f(n-2)+f(n-1)

Но речь то идет об этом алгоритме:

Цитата swf @ 29.06.20, 20:08

3. Самый простой и естественный способ - вычислять в цикле за время O(n), запоминая только два предыдущих значения.

Правильно ты все пишешь в третьем пункте, его то мы и обсуждаем, и сложность этого алгоритма, про который ты пишешь в 3 пункте esperanto оценил в O(2^N). Можете перечитать.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833493

Метки: Много шуму и... ничего

Комментарии (0)

Об особенностях поиска информации в сети

Понедельник, 29 Июня 2020 г. 23:08 + в цитатник

swf: Посмотрела.
1. Считать n-ное число Фибоначчи как f(n-2)+f(n-1), конечно, нельзя.
Это как считать последовательность факториалов 1, 2!, ..., n!, не умножая предыдущий член на текущий номер, а для каждого нового члена выполняя все умножения.
У меня студенты так на прологе сумму ряда с факториалом в знаменателе считают. И довольны собой: мы же рекурсией написали!
2. Будет ли этот способ экспоненциальным? Да, будет, по определению показательной функции с основанием больше 1.
Видимо, можно точно подсчитать, чему равно основание.
3. Самый простой и естественный способ - вычислять в цикле за время O(n), запоминая только два предыдущих значения. Можно ли это считать методом ДП?
Думаю, можно, раз есть правильное рекуррентное соотношение.

Так что esperanto совершенно правильно и, я бы сказала, деликатно указал на это автору статьи.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833492

Метки: Много шуму и... ничего

LiveInternetLiveInternet

-Поиск по дневнику

-Подписка по e-mail

-Постоянные читатели

-Статистика

Форум на Исходниках.RU

Перейти к полной формеБыстрая запись

Определение микроархитектуры CPU

Сбор старых друзей

Об особенностях поиска информации в сети

Типизировать POD-типы?

Об особенностях поиска информации в сети

Типизировать POD-типы?

Об особенностях поиска информации в сети

Типизировать POD-типы?

Сбор старых друзей

Типизировать POD-типы?

Об особенностях поиска информации в сети

Об особенностях поиска информации в сети

Определение микроархитектуры CPU

Об особенностях поиска информации в сети

Определение микроархитектуры CPU

Определение микроархитектуры CPU

Определение микроархитектуры CPU

Об особенностях поиска информации в сети

Об особенностях поиска информации в сети

Об особенностях поиска информации в сети