Порядок вычисления выражения Си

фибоначи через матрицы было вообщето-то контрпримером фибоначи через рекурсию (которой там фибоначи много) а затем её сверх низведение до линии через меморизацию 2ух текущих соседей.

с чего ты взял, что фиббоначи через рекурсию будет медленнее? IRL в 95% случаев таки быстрее. Просто потому, что в 95% случаев длинная арифметика не нужна. А если нужна, то тебе всё равно придётся делать свой велосипед для своих длинных чисел.

реально же примерами есть классическое логарифмическое возведение и поиск кратчайших ( либо связностей если на булевых) у флойда? а все это приводилось и здесь и там как примеры обобщённого.

ну дык речь и о том, что это твоё «обобщённое» внутри кода будет выглядеть вполне конкретно, и что оптимизировать его надо ПОСЛЕ конкретизации. А если оптимизацию проводить ДО, то в 95% случаев у тебя будет оверхед и отрицательный профит. Т.к. в 95% случаев твои допущения ошибочны.

Пример: ты делаешь для меня возведение в степень n за O(log(n)) умножений, а мне нужно считать x². В лучшем случае ты просто сделал бесполезную работу. А обычно ты мне всё поломал, т.к. компилятор уже не может увидеть простое x*x в глубине твоего кода.

Короче: абстрагирование это конечно хорошая идея, но не нужно перегибать палку. А то получится php, в котором _одна_ структура данных. Которая работает одинаково _плохо_ в любых конкретных случаях.

Например НЕ нужно писать x=(const int)123

Разумеется, только я написал const int x = 123 (собственно, потому что мысль была про неделание ++, временных переменных и т.п., а просто написание выражения (x + 1)^2 для которого достаточно const int <: int).

А если ты сделаешь например функцию, которая принимает uint64_t

То значит я хочу mulq, ты ж когда int-ы умножаешь занося в другие int-ы результат не смущаешься что у тебя там в верхние биты могут отбрасываться.

и тем не менее, неделю назад я лично написал код, который возводит число путём умножения в цикле в 1400ю степень

хорошо применяеш максиму Кнута

это бритва Оккама. Если-бы я написал функцию pow(), то это мне ничем-бы не помогло. А знаешь почему? Да просто потому, что возводить в 1400ю степень мне нужно для заполнения таблицы степеней. А эта таблица как раз и представляет собой быструю и простую функцию pow(), которая мне и нужна. Просто у меня скобки получились [квадратные]. А скорость получилась на ∞ выше твоей, т.к. таблица pow[] мне нужна для умножения, а твоё «логарифмическое возведение через умножения» мне пришлось бы выполнять через умножение реализованное через сложение.

Всё потому, что я исходил из верных предпосылок, а ты при оптимизации исходишь в 146% случаев из неверных предпосылок. Потому что оптимизация у тебя преждевременная.

да, в примитивных примерах всё работает точно также. Молодец.

Ты знаешь математику ничем не лучше моего сына первоклассника(в случае сложения/вычитания целых чисел 0..20).

Разумеется, только я написал const int x = 123

в данном контексте разницы нет. Вот если-бы x было-бы глобальным, и было-бы доступно хрен знает откуда, тогда const было-бы необходимо. А в двух строчках это ненужный мусор. И ты и я и компилятор видим, что x является const int равное 123.

а просто написание выражения (x + 1)^2 для которого достаточно const int <: int).

что-бы не писать x+1 дважды(раз это так плохо), куда как лучше написать t=x+1, а уже потом t*t. Возведение в степень тут вообще лишняя сущность, которую ты зря создал.

И const тут тоже лишняя сущность, ибо t эквивалентна 124. И это любому очевидно.

То значит я хочу mulq, ты ж когда int-ы умножаешь занося в другие int-ы результат не смущаешься что у тебя там в верхние биты могут отбрасываться.

меня это люто, бешено раздражает. То, что половину информации я теряю.

ты осознаёшь, что твое аргументы применимы и к qvicksort vs пузырёк?

ps. я в курсе про тимсорт.

ты осознаёшь, что твое аргументы применимы и к qvicksort vs пузырёк?

нет, неприменимы. Пузырёк и вставки работают одинаково только в бесконечности. Если N небольшое, то разница огромная.

я в курсе про тимсорт.

нет, я не про это. Я про то, что бинарное дерево обладает очень любопытным свойством: почти все узлы лежат внизу дерева. Потому скорость сортировки зависит в первую очередь от сортировки малых массивов, а от скорости сортировки больших практически не зависит. На практике такая картина наблюдается для N<10⁹ (т.е. по сути всегда). В итоге, реальная скорость сортировки для N<10⁹ очень сильно отличается от O(Nlog(N)), т.к. при выводе этой формулы зависимость предполагается линейной. Т.е. для N=10 скорость вдвое быстрее, чем при N=20. Это не проблема, т.к. ещё в глубокой древности при укорочении массива в qsort меньше ν включались вставки (если это не учебник конечно). Проблема в том, что 95..99% работы в итоге приходится именно на вставки, и оптимизация самой qsort ничего не даст. Нужно оптимизировать вставки, даже в ущерб qsort. Понятно это стало лишь совсем недавно (кстати потому и придумали тимсорт, из-за устойчивости слияния. qsort неустойчива, и в итоге всё портит, и превращает в хаос, даже если было хоть чуть порядка, в итоге qsort всегда сортирует одинаково медленно)

Как видишь, тут на первый план выходят второстепенные детали, о которых ты не знаешь, и не можешь знать заранее. В итоге, твоя оптимизация в лучшем случае ничему не поможет. А обычно только навредит.

Потому я и категорически против твоих любимых pow<2>. Ибо по опыту знаю, что оптимизация в этот момент пользы в принципе не приносит. Если надо возвести в 9001ю степень, то так и напиши: for(y=1, j=0; j<9001; y*=x, j++);, и ставлю 100 против одного, что тормозить будет совсем в другом месте. И такой код куда как проще сопровождать, ибо даже без комментариев понятно за секунду, что он делает. А что делает pow<2> надо полдня разбираться. Не, ясное дело, что возводит в квадрат, а «второстепенные детали», которые всё и решают IRL?

man sequence point