М
Ну или так :)
Size: a a a
2021 November 01
ПФ
Я на достаточно больших числах считал и ыло врое корректно (сравнивал с вольфрамом). Там конечно же Floor надо
AN
К слову, я до сих пор считаю, что дизайн листов и массивов - один из главных проколов котлин. Скопировали джавовый лист со всеми его проблемами.
ПФ
Как я понимаю фибоначчи выражается какой-то штукой, называемой "рекуррентное соотношение". Не знаю что это, но оно выражается формулой )
М
Потому что была такая изначальная идея, хотя можно доделать еще в set или map
AN
Массив должен явно наследовать List. И должен быть базовый интерфейс random-access, не реализующий Iterable
AN
Рекуррентный - это однокоренное с рекурсией. Ты не можешь вычислить текущий элемент, не вычислив предыдущие.
ПФ
А рекуррентное соотношение?
AN
Ну так оно и есть. Соотношение между последующими элементами и предыдущими
RE
Вообще Фибоначчи точно и быстро можно считать за логарифм операций через быстрое возведение в степень матриц https://e-maxx.ru/algo/fibonacci_numbers
VS
Это «количества умножений матриц» там будет логарифм.
А *одно* умножение матриц требует 8 умножений длинных чисел, каждое из которых требует N^2
А *одно* умножение матриц требует 8 умножений длинных чисел, каждое из которых требует N^2
AN
Умножение матриц дешевле с точки зрения CPU за счет префетча, правда не сильно.
VS
Я что? Против умножения матриц что-ли?
Я говорю про то, что даже одно простое умножение длинных чисел это уже N^2, а таких умножений надо будет сделать несколько (8штук для каждого умножения 2x2 матриц)
Я говорю про то, что даже одно простое умножение длинных чисел это уже N^2, а таких умножений надо будет сделать несколько (8штук для каждого умножения 2x2 матриц)
AN
Ну там надо заоптимизировать, но шило на мыло, да.
AN
Там в принципе делается оптимизация, за счет которой на маленьких числах используются лонги в место бигинтов.
VS
в int помещается где-то 40 чисел. Значит, long’а перестанет хватать уже на 80ом числе
AN
Ну да, но если человек всерьез считает Фибоначи дальше, значит он или делает что-то не то, или спортивный программист.
AN
В свое время сделал очень изящное решение для подсчета длинных хвостов распределения, там как всегда факториал на экспорненту. Все считали в лоб и выходили за точность, а я сделал как раз итеративное вычисление с кэшированием и там были конечные числа
DK
Умножение длинных чисел это N log N по последним данным
BV
Очень интересная тема для поффтопа, предлагаю там продолжить