Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 29
Этот алгоритм, кстати, был упомянут в том топике:)
Как и обсуждение того, что асимптотика тут ни разу не O(log N), ибо N-е число Фибоначи имеет размер O(N), т.е. за это время его не получится даже вывести.
Как и обсуждение того, что асимптотика тут ни разу не O(log N), ибо N-е число Фибоначи имеет размер O(N), т.е. за это время его не получится даже вывести.
Да, он там был упомянут, но там нет объяснения алгоритма. O(log N) относится к количеству арифметических операций
Поэтому надо нормально описать рассматриваемую модель вычислений.
Например, что рассматриваем мы RAM. В качестве элементарной операции принимаются такие-то арифметические операции (или битовые операции над числами с учетом длины) и т.д.
Может быть я конечно зануден, но 80% (а может и больше) программистов на собеседовании не способны банально объяснить, что такое NP задачи и NPC, а про более глубокое понимание теории сложности я вообще молчу. И самое смешное, что все они считают себя гуру в хайлоаде.
Извините, что я так плачусь тут, но накипело.
Например, что рассматриваем мы RAM. В качестве элементарной операции принимаются такие-то арифметические операции (или битовые операции над числами с учетом длины) и т.д.
Может быть я конечно зануден, но 80% (а может и больше) программистов на собеседовании не способны банально объяснить, что такое NP задачи и NPC, а про более глубокое понимание теории сложности я вообще молчу. И самое смешное, что все они считают себя гуру в хайлоаде.
Извините, что я так плачусь тут, но накипело.
Почему функция называется factorial, а описание про числа Фибоначчи?
Вы решили повторить тоже не упоминать тот факт, что в итоге кол-во умножение (или сложений) у вас будет N * log(N), потому что для n-го числа придется использовать некоторые ухищрения по типу длинной арифметики?
Если так рассуждать, то асимптотика алгоритма быстрой сортировки применительно к строкам произвольной длины (и даже числам произвольной величины) тоже не N * log(N).
Конечно нет! Кто вам такое сказал? Асимптотическая оценка предполагает учет всего, что не является константой и влияет на скорость работы алгоритма. Скорость работы алгоритма быстрой сортировки на строках произвольной длины O(k*N*log(N)), где N — кол-во строк, k- максимальная длина строки.
Аналогично и с фибоначчи, если заметить что длина n — го числа фибоначчи будет O(n), что так же было у помянуть в комментариях к предыдущей статье.
Аналогично и с фибоначчи, если заметить что длина n — го числа фибоначчи будет O(n), что так же было у помянуть в комментариях к предыдущей статье.
Вы фиксируете максимальную длину строки. Т.е. превращаете ее в константу. Разве в этом случае не выполняется равенство O(k*N*log(N)) = k*O(N*log(N))?
Строки произвольной длины, про которые вы сказали, подразумевают что их длинна не фиксированная, а произвольная, не так ли? Иными словами К зависит от набора строк. Вы же не говорите что фиксируете N в быстрой сортировке и она выполняется за О(1).
Тем более что касается чисел Фибоначчи, то там длину можно зафиксировать только если зафиксировать само N.
К тому же стоило бы рассказать каким образом Вы собираетесь перемножать длинные числа за О(n), потому что обычное перемножение делается за O(N^2), и в таком случае ваш алгоритм скатывается до O(N^2*log(N)), что даже хуже чем реализация влоб.
Тем более что касается чисел Фибоначчи, то там длину можно зафиксировать только если зафиксировать само N.
К тому же стоило бы рассказать каким образом Вы собираетесь перемножать длинные числа за О(n), потому что обычное перемножение делается за O(N^2), и в таком случае ваш алгоритм скатывается до O(N^2*log(N)), что даже хуже чем реализация влоб.
Я разве писал, что собираюсь перемножать длинные числа за O(n)?
Допустим, что умножение «длинных» чисел у нас выполняется за 
операций умножения машинных слов. На каждой итерации выполняются 4 операции «длинного» умножения, т.е. сложность одной итерации равна 
простых операций умножения. Для числа 
по моему алгоритму будет выполнено m — 1 итераций. Можно допустить, что на каждой итерации размерность операндов у нас будет расти вдвое. Общая сложность всех итераций равна 
Можно заметить, что это сумма геометрической прогрессии:
Поскольку нас интересует асимптотика, то m у нас достаточно большое, чтобы отбросить отрицательные степени двойки:
Т.е. получили асимптотику
. Но 
, поэтому итоговая асимптотика равна 
операций умножения машинных слов.
операций умножения машинных слов. На каждой итерации выполняются 4 операции «длинного» умножения, т.е. сложность одной итерации равна простых операций умножения. Для числа по моему алгоритму будет выполнено m — 1 итераций. Можно допустить, что на каждой итерации размерность операндов у нас будет расти вдвое. Общая сложность всех итераций равна Можно заметить, что это сумма геометрической прогрессии:
Поскольку нас интересует асимптотика, то m у нас достаточно большое, чтобы отбросить отрицательные степени двойки:
Т.е. получили асимптотику
. Но , поэтому итоговая асимптотика равна операций умножения машинных слов.Допустил ошибку в оценке сложности итерации. Поскольку на каждой итерации мы оперируем числами Фибоначчи, которые сами порядка 
(где k — порядковый номер числа фибоначчи на текущей итерации), то сложность итерации будет равна 
. Сложность всех итераций равна 
. Асимптотика получается 
, что все равно лучше, чем ваша оценка 
. К тому же для умножения можно использовать более эффективные алгоритмы.
(где k — порядковый номер числа фибоначчи на текущей итерации), то сложность итерации будет равна . Сложность всех итераций равна . Асимптотика получается , что все равно лучше, чем ваша оценка . К тому же для умножения можно использовать более эффективные алгоритмы.Отлично, вы действительно доказали, что при нахождении двух чисел фибоначчи данным методом вы получите O(N^2) действий (т.к. последняя операция покрывает все предыдущие).
Но нужно понимать что при перемножении 2-х длинных чисел делается O(N^2) умножений и делений (деления необходимы для переноса разрядов), что очень существенно снижает производительность, по сравнению с обычным итеративным методом, который позволил бы выполнять в сумме O(N^2) операций сложения и сравнений (т.к. каждое сложение требует O(N) действий). Поэтому в данной форме метод не имеет преимуществ перед итеративным.
Однако при использовании быстрого преобразования Фурье (которое позволяет перемножать длинные числа за O(N*log(N)) ) вы получите заветные O(N*log(N)) и в таком случае метод действительно оправдан.
Но исходный вопрос был в другом — вы читали предыдущую статью и даже написали свою статью в ответ той. Почему же вы не исправили ошибку, допущенную предыдущим автором в оценке асимптотики, и на которую ему указали в первом же комментарии?
Но нужно понимать что при перемножении 2-х длинных чисел делается O(N^2) умножений и делений (деления необходимы для переноса разрядов), что очень существенно снижает производительность, по сравнению с обычным итеративным методом, который позволил бы выполнять в сумме O(N^2) операций сложения и сравнений (т.к. каждое сложение требует O(N) действий). Поэтому в данной форме метод не имеет преимуществ перед итеративным.
Однако при использовании быстрого преобразования Фурье (которое позволяет перемножать длинные числа за O(N*log(N)) ) вы получите заветные O(N*log(N)) и в таком случае метод действительно оправдан.
Но исходный вопрос был в другом — вы читали предыдущую статью и даже написали свою статью в ответ той. Почему же вы не исправили ошибку, допущенную предыдущим автором в оценке асимптотики, и на которую ему указали в первом же комментарии?
Не пойму, зачем нужна операция деления для реализации «длинного» умножения? Перенос разрядов легко реализуется на уровне ассемблера. По крайней мере в x86 команды умножения возвращают результат в 2 регистрах. Старшая часть результата в этом случае — это и есть перенос.
>>Почему же вы не исправили ошибку, допущенную предыдущим автором в оценке асимптотики, и на которую ему указали в первом же комментарии?
Я не считаю оценку автора предыдущей статьи ошибочной. «Длинная арифметика» нужна далеко не всегда. Чаще всего разрядность операндов фиксирована.
>>Почему же вы не исправили ошибку, допущенную предыдущим автором в оценке асимптотики, и на которую ему указали в первом же комментарии?
Я не считаю оценку автора предыдущей статьи ошибочной. «Длинная арифметика» нужна далеко не всегда. Чаще всего разрядность операндов фиксирована.
Для того что бы понять каким образом работает длинная арифметика вы можете почитать например здесь. Там достаточно подробно описан принцип действия и реализация.
Как работает длинная арифметика я понимаю. Непонятно мне ваше стремление включить операции деления в асимптотику умножения. Да, неявно деление выполняется, но деление на степени двойки выполняется за констатное время простым сдвигом. Я уже писал, что результатом выполнения команд умножения в x86-процессорах является пара числел, одно из которых — перенос в старшие разряды. На скорость умножения это никак не влияет.
По вашей логике и для выполнения сложения требуется операция деления — для вычисления переноса.
Вы меня не правильно поняли. Операция деления ни как не влияет на асимптотику, она лишь серьезно ухудшают константу. А при такой же асимптотике как и у обычного алгоритма, но с худшей константой, этот алгоритм теряет смысл.
Моя логика здесь не при чем, в приведенной мной ссылке все описано. При сложении операций деления нет, там достаточно одного сравнения и одного вычитания (так как при сложении 2-х чисел меньших заданного, результат не может быть больше него даже в 2 раза).
Если при умножении Вы будете использовать основание со степенью двойки (это вам понадобится что бы делать сдвиг вместо деления), то при выводе вы столкнетесь с проблемой перевода результата в нормальный вид. Да и сама операция умножения (короткого на короткое) дороже чем сложение.
При чтении ваших комментариев у меня сложилось настойчивое ощущение того, что Вы не понимаете как устроена длинная арифметика (точнее может и понимаете, но не сталкивались с реализацией). Потому вероятно Вы и говорите о разнесении результата умножения на 2 регистра, не понимая что я имею ввиду под переносом разрядов. Поэтому я и привел ссылку на описание и реализацию длинной арифметики.
Если Вы не согласны со мной, то можете это проверить самостоятельно, реализовав эти алгоритмы, и сравнив их время работы.
P.S.: Изначально мне интересовало почему вы сделали такую оценку асимптотики. Сейчас вы удовлетворили мой интерес.
Моя логика здесь не при чем, в приведенной мной ссылке все описано. При сложении операций деления нет, там достаточно одного сравнения и одного вычитания (так как при сложении 2-х чисел меньших заданного, результат не может быть больше него даже в 2 раза).
Если при умножении Вы будете использовать основание со степенью двойки (это вам понадобится что бы делать сдвиг вместо деления), то при выводе вы столкнетесь с проблемой перевода результата в нормальный вид. Да и сама операция умножения (короткого на короткое) дороже чем сложение.
При чтении ваших комментариев у меня сложилось настойчивое ощущение того, что Вы не понимаете как устроена длинная арифметика (точнее может и понимаете, но не сталкивались с реализацией). Потому вероятно Вы и говорите о разнесении результата умножения на 2 регистра, не понимая что я имею ввиду под переносом разрядов. Поэтому я и привел ссылку на описание и реализацию длинной арифметики.
Если Вы не согласны со мной, то можете это проверить самостоятельно, реализовав эти алгоритмы, и сравнив их время работы.
P.S.: Изначально мне интересовало почему вы сделали такую оценку асимптотики. Сейчас вы удовлетворили мой интерес.
И все-таки деление в явном виде для реализации «длинного» умножения не нужно. Вот простейшая реализация умножения «длинного» числа на беззнаковое целое.
Перемножение 2 «длинных» чисел выполняется аналогично умножению столбиком.
>> Если при умножении Вы будете использовать основание со степенью двойки
А в каком виде по-вашему хранятся числа в оперативной памяти компьютера? Вывод — это уже отдельная история. Если на то пошло, то можно и в шестнадцатеричном виде вывести данные. Несколько тысяч цифр человек все равно не в состоянии воспринять, поэтому это будет не сильно хуже, чем десятичное представление.
>> Да и сама операция умножения (короткого на короткое) дороже чем сложение
Дороже, но на современных процессорах оно выполняется относительно быстро.
unsigned multiply(unsigned* big_number, unsigned number_size, unsigned multiplier)
{
unsigned overflow;
__asm {
mov edi, big_number
mov ebx, multiplier
mov ecx, number_size
xor esi, esi
begin_loop:
mov eax, [edi]
mul ebx
add eax, esi
mov esi, edx
mov [edi], eax
add edi, 1
sub ecx, 1
jnz begin_loop
mov overflow, esi
}
return overflow;
}
Перемножение 2 «длинных» чисел выполняется аналогично умножению столбиком.
>> Если при умножении Вы будете использовать основание со степенью двойки
А в каком виде по-вашему хранятся числа в оперативной памяти компьютера? Вывод — это уже отдельная история. Если на то пошло, то можно и в шестнадцатеричном виде вывести данные. Несколько тысяч цифр человек все равно не в состоянии воспринять, поэтому это будет не сильно хуже, чем десятичное представление.
>> Да и сама операция умножения (короткого на короткое) дороже чем сложение
Дороже, но на современных процессорах оно выполняется относительно быстро.
Под основанием опять таки понимается не система счисления компьютера, а база, по которой берется модуль. В вашем коде это 2^32 -1.
Допустим ваш код заработал, после того как в нем поменялось add edi, 1 на add edi, 4. Однако результат, который он возвращает совершенно не читаем, после первого же выполняемого переноса. Если уж вы решили написать его на асме (хотя того же эффекта можно легко достичь битовыми операциями и в плюсах), то будте так любезны, напишите код дешифрации результата в человеческий вид.
Очень интересно возможно ли будет здесь обойтись без квадрата действий и делений (что бы не получилось так что вывод сложнее чем сам расчет).
Допустим ваш код заработал, после того как в нем поменялось add edi, 1 на add edi, 4. Однако результат, который он возвращает совершенно не читаем, после первого же выполняемого переноса. Если уж вы решили написать его на асме (хотя того же эффекта можно легко достичь битовыми операциями и в плюсах), то будте так любезны, напишите код дешифрации результата в человеческий вид.
Очень интересно возможно ли будет здесь обойтись без квадрата действий и делений (что бы не получилось так что вывод сложнее чем сам расчет).
>> В вашем коде это 2^32 -1.
База в данном случае 2^32
>> Допустим ваш код заработал, после того как в нем поменялось add edi, 1 на add edi, 4
Писал в торопях, допустил ошибку
>> Если уж вы решили написать его на асме
Тут нужен именно ассемблер либо intrinsic'и, которые позволяют получить доступ к старшей части результата умножения.
Код вывода в шестнадцатеричном виде элементарен. Если нужна десятичная форма, то код усложнится и, да, понадобится деление.
В этой функции и функции из предыдущего комментария предполагается порядок байтов little-endian, принятый в x86.
База в данном случае 2^32
>> Допустим ваш код заработал, после того как в нем поменялось add edi, 1 на add edi, 4
Писал в торопях, допустил ошибку
>> Если уж вы решили написать его на асме
Тут нужен именно ассемблер либо intrinsic'и, которые позволяют получить доступ к старшей части результата умножения.
Код вывода в шестнадцатеричном виде элементарен. Если нужна десятичная форма, то код усложнится и, да, понадобится деление.
void print_number(unsigned int* number, unsigned int number_size, int leading_zeros)
{
for(; number_size--;) {
if (!number[number_size]) {
if (leading_zeros)
printf("%08x", 0);
} else {
if (leading_zeros)
printf("%08x", number[number_size]);
else
printf("%x", number[number_size]);
for(; number_size--;)
printf("%08x", number[number_size]);
break;
}
}
}
В этой функции и функции из предыдущего комментария предполагается порядок байтов little-endian, принятый в x86.
Для типа unsigned есть O(1) алгоритм — таблица из 93 элементов)
Проще, чем тот метод, с матрицами :-)
Проще. При проведении упомянутых собеседований в подавляющем большинстве случаев предлагают решение с рекурсией, а не с матрицей. С матрицей лично мне рассказали решение лишь однажды.
Но с решение возведением в степень мне кажется более изящным.
P.S. комментарий от К.О. для зануд по поводу O(N) процитирую ещё раз: Быстро можно находить только числа фибоначи по какому-нибудь модулю.
Но с решение возведением в степень мне кажется более изящным.
P.S. комментарий от К.О. для зануд по поводу O(N) процитирую ещё раз: Быстро можно находить только числа фибоначи по какому-нибудь модулю.
когда увидел название той статьи, сначала попробовал сам получить алгоритм, и решение получилось такое же, как и у Вас :) оно просто гораздо более очевидно, чем то, что было приведено в той статье, и интуитивно понятное
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Еще один алгоритм вычисления чисел Фибоначчи