Провожал друга на поезд. Пройдя несколько вагонов мы решили спросить, пустят ли его по паспорту с электронной регистрацией в чужой вагон. Нам ответили, что полные списки есть только в первом вагоне. Пришлось возвращаться, так как до нужного уже было не добежать :)
Строим число, напимер, так:
Пусть N — максимальная длина префикса 3141592…
Строим число по следующему правилу:
1) Если текущий символ является частью префикса числа Pi длиннее N — заменяем на 0 (или на что угодно)
2) Иначе берем разряд из Pi.
Понятно, что иррациональным оно останется. Не понятно, с чего ему стать при этом алгебраическим, но строгое доказательство я тоже не приведу…
Смысл моего топика был не в том, что 2-е утверждение не верно, а в том, что есть повод в нем усомниться.
Второе утверждение хоть и является наиболее вероятным, его ещё нужно доказать…
Я могу легко построить трансцендентное число, не удовлетворяющее 2-му утверждению.
По-моему, задачей поинтереснее будет вычисление наибольшего количества знаков числа Пи за заданное время на одинаковой машине.
В прошлом году такой конкурс как раз проводила компания Intel. Результаты. Лучшая программа использовала GMP + OpenMP + формулу Чудновского.
Во многих языках программирования есть встроенная поддержка длинной арифметики (python, haskell, erlang, common lisp, java, etc.). Уверен, что почти для любого языка программирования можно найти соответствующие сторонние библиотеки.
Единственное, что по скорости с GMP не сравнится ни одна из них (конечно, если библиотека не является оберткой над GMP). Поправьте, если тут я не прав.
Конечно, каждая функция сравнивалась с базовой имплементацией на С++. К сожалению, конкретных цифр у меня не осталось, а провести эксперименты сейчас не представляется возможным (я там больше не работаю).
По памяти могу сказать, что ускорение было от 2-х до ~15-ти раз (обычно ~2-4 раза). Медленнее работало все, что на входе или выходе имело скалярные величины.
Для PS3 и XBox360 (процессор PowerPC, расширение VMX) цифры были аналогичными.
Задача была довольно специфическая, вектора длины 4, матрица 4х4, кватернионы. Точность не критична (GameDev). SSE (или SSE1) хорошо подходит для таких задач — одной операцией обрабатываем сразу все компоненты вектора. Писали на SSE интринсиках (обертка над SSE функциями).
Из практических советов могу сказать, что
1) между вызовами SSE функций не должно быть обычных x86 конструкций (даже if и подобные), это приводит к падению производительности. Чем дольше наш вектор хранится в SSE регистре, тем лучше.
2) часто для достижения большей производительности выгодно писать функции, обрабатывающие сразу по 4 вектора, или делающие по 4 операции над 1 вектором.
3) в SSE есть операции для аппроксимации вычисления обратного числа и обратного корня. Они работают значительно быстрее, но с пониженной точностью. С ними нужно обращаться предельно аккуратно.
В приведенных Вами ссылках ни о каком асимптотическом ускорении речи не идет (зависимость все равно линейная, просто коеффициент больше единицы). Тем не менее за информацию спасибо, примеры интересные…
Распараллеливание с помощью инструкций SSE активно применяется при низкоуровневых оптимизациях. В некоторых удобных случаях удавалось достичь более чем десятикратного ускорения (правда за счет снижения точности результата) в задачах с векторами, матрицами, кватернионами и тп. Компилятору это обычно не под силу (Intel C++ compiler мы не проверяли, но я сильно сомневаюсь что ситуация сильно изменится...)
Можешь привеcти хоть 1 пример задачи с зависимостью 2^n? Естественно, при оптимальном написании 1-поточной версии. По-моему, более чем линейного прироста получить невозможно.
Перечитал несколько раз, но вашей арифметики так и не понял…
83-53 = 53-23 = 30
523-313 = 313-103 = 210
6929-4619 = 4619-2309 = 2310
и тд
Для (2;3;5) цикл равен 30
Для (2;3;5;7) цикл равен 210
Для (2;3;5;7;11) цикл равен 2310
Для (2;3;5;7;11;13) цикл равен 30030
Найди закономерность :)))
Fixed issues:
Notifications — Audio notifications were not working when Skype was installed on removable storage
Пусть N — максимальная длина префикса 3141592…
Строим число по следующему правилу:
1) Если текущий символ является частью префикса числа Pi длиннее N — заменяем на 0 (или на что угодно)
2) Иначе берем разряд из Pi.
Понятно, что иррациональным оно останется. Не понятно, с чего ему стать при этом алгебраическим, но строгое доказательство я тоже не приведу…
Смысл моего топика был не в том, что 2-е утверждение не верно, а в том, что есть повод в нем усомниться.
Я могу легко построить трансцендентное число, не удовлетворяющее 2-му утверждению.
В прошлом году такой конкурс как раз проводила компания Intel. Результаты. Лучшая программа использовала GMP + OpenMP + формулу Чудновского.
Единственное, что по скорости с GMP не сравнится ни одна из них (конечно, если библиотека не является оберткой над GMP). Поправьте, если тут я не прав.
По памяти могу сказать, что ускорение было от 2-х до ~15-ти раз (обычно ~2-4 раза). Медленнее работало все, что на входе или выходе имело скалярные величины.
Для PS3 и XBox360 (процессор PowerPC, расширение VMX) цифры были аналогичными.
Из практических советов могу сказать, что
1) между вызовами SSE функций не должно быть обычных x86 конструкций (даже if и подобные), это приводит к падению производительности. Чем дольше наш вектор хранится в SSE регистре, тем лучше.
2) часто для достижения большей производительности выгодно писать функции, обрабатывающие сразу по 4 вектора, или делающие по 4 операции над 1 вектором.
3) в SSE есть операции для аппроксимации вычисления обратного числа и обратного корня. Они работают значительно быстрее, но с пониженной точностью. С ними нужно обращаться предельно аккуратно.
Разбор некоторых моментов можно почитать тут.