LINUX.ORG.RU

Итеративно вычислить все 1/x при x = 1...n

 , , , ,


1

1

Изначально есть N/x, где N не меняется, а x = 1...n. Это можно свести к 1/x, поэтому далее будет идти речь о нём. Если есть более удачные варианты о них так же можно(и нужно) написать.

Гугл говорит, что основной методикой является это. Оно приспособлено для вычисления произвольного D, где в качестве нулевой итерации используется приближённое значение 1/D. Подобные методы так же предполагают аналогичное.

Я же предполагаю, что можно как-то использовать при вычислении 1/D предыдущие значения(1/(D - 1), 1/(D - 2), …), что должно дать куда более удачный метод, либо как минимум увеличить точно итераций.

Вопрос: Можно ли пользуясь тем, что нужно вычислить результат сразу для всех возможных D, упросить вычисление одного отдельного D.

P.S. чётные D можно не вычислять. Деление лучше вообще не использовать, либо использовать по минимуму.

Уточнение задачи: 1/x, где x целое, 3,5,7...n в диапазон не включены чётные числа.

Надо сумму всех N/x где x = 1...n? Это N / n!, зачем его вычислять? В каком виде это нужно в итоге?

где в качестве нулевой итерации используется приближённое значение 1/D

Точность значения 1/D тебя очень разочарует. Лучше его так и оставить.

crutch_master ★★★★★ ()

Если ты имплементируешь деление по Ньютону-Рафсону (NR), но сэкономить можно на том, что 1/(x-1) является хорошим приближением к 1/x, и ввиду квадратичной сходимости NR итераций (удвоение числа правильных цифр на каждой итерации), точное значение даже для double будет достигаться за 3-4 итерации на каждый x. Т.е. в твоём случае простейшей оптимизацией будет изначальное вычисление 1/1 (что тривиально), а затем вычисление 1/2 используя 1 как начальное приближение, потом 1/3 используя 1/2 как приближение и т.д. Можно даже сразу начать с 1/2 (захардкодить 1 и 1/2), и двигаться дальше, или, например, вычислять обратные к числам вида 2^n аналитически (обратные тривиально записать в бинарном виде), а промежуточные – по NR.

unanimous ★★★★★ ()
Ответ на: комментарий от sutrasarki

А какой длины у тебя ряд? Есть, если не ошибаюсь, асимптотическое разложение \sum_{k=1}^N 1/k \approx ln(N) - C0 + C1/N…

где C1 постоянная Каталана, а далее какие-то стремящиеся к 0 члены.

unanimous ★★★★★ ()
Ответ на: комментарий от unanimous

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

ZERG ★★★★★ ()
Ответ на: комментарий от ZERG

От N/x не уйти. Подобное условие железно закреплено в алгоритме. Я его изменять не могу.

Что хочу? Посчитать не(практически) используя деление. Пользуясь особыми условиями упростить базовые алгоритмы. Мне кажется, что оно есть. Но чётко я её не вижу. Очень-очень смутно. Вот прошу помощи знатоков.

sutrasarki ()
Ответ на: комментарий от sutrasarki

Ну выписываешь свой ряд sum(1/X(n)) и целяя Х уносишь его за скобки, а потом эту кучу скобок делишь на этапы, предыдущие скобки операнд для текущих и так далее.

torvn77 ★★★★★ ()
Ответ на: комментарий от anonymous

1/6 = 1/2 * 1/3

на моей тачке ускорение получилось только в 1.6 раза, при занимаемой памяти n*sizeof(double). канпелял с -O2 -flax-vector-conversions -ffast-math -fassociative-math -march=native.

кот.

anonymous ()

найти делитель для каждого числа, используя что-нибудь типа решета Эратосфена, и считать N/x как произведение соответствующих уже вычисленных дробей

Lrrr ()
Ответ на: комментарий от sutrasarki

Не стоит забывать, что некоторые буквально школьные задачи тоже играют на руку: замени деление вычитанием и будь таков. Это классический пример, когда нужно преобразовать ряд, а у тебя члены типа 1/2*3, что есть 1/2 - 1/3.

ZERG ★★★★★ ()
Ответ на: комментарий от ZERG

Направление там не очень успешное. Таблица не векторизуется. Для gpu/железяки вполне подойдёт, но это не универсальное решение.

Гуглёж - это то, о чём уже сказано в заглавии. Там те же самые ~4 итерации, только первая итерация заменена битхаком.

Я +/- знаю о многих подобных решениях. Вопрос заключается не в этом. Вопрос заключается в том - можно ли улучшить алгоритм вычисления пользуясь тем, что мне нужно вычислить не произвольное f(x), а диапазон f(1), f(3), ..., f(n).

sutrasarki ()
Ответ на: комментарий от sutrasarki

Ну смотри, по определению 1/n*(n+1)=1/n-1/(n+1), в качестве примера возьми 1/6=1/(2 * 3)=1/2-1/3. Это самый базовый случай, который как раз тебе и подходит. Заранее не нужно вычислять все значения, а только часть из них. Не супер много, но что есть. К этому можно добавить 1/(n * n) и прочие степени, следуя завету Lrrr

ZERG ★★★★★ ()
Последнее исправление: ZERG (всего исправлений: 1)
Ответ на: комментарий от ZERG

Проблема в том, что об этом даже не нужно думать. Любое наличие таблицы - тупиковый путь. Я понимаю о чём ты говоришь, о чём говорил он.

Вот у тебя есть 32байт simd. Это 8 float. Чтобы таблица имела хоть какой-то смысл - она должна быть в 8 раз быстрее. Попросту потому, что ты считаешь сразу 8 значение, а таблицей только одно. Это практически невозможно.

Поэтому, можешь сразу исключать табличные методы, если только таблицы специально не заточены под векторизацию. Это не везде применимо и эти мало кто занимается. Шансы найти что-то стремятся к нулю, а придумать ещё меньше.

sutrasarki ()
Ответ на: комментарий от anonymous

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

sutrasarki ()

ТС, у меня сразу к тебе ряд вопросов возник, основной: а какая точность тебе нужна? Потому как сходимость у алгоритмов разная, соответственно более сложные методы могут начать обгонять более быстрые при некоторой минимально необходимой точности.

Второй вопрос — а какие операции у тебя быстрые и доступные?

peregrine ★★★★★ ()
Ответ на: комментарий от peregrine

Сейчас это не принципиально. В данной задаче минимально бит 15-20, возможно весь флоат. Меня же интересуют, в том числе, и более общие решения. С произвольной точностью. Возможно в будущем пригодятся.

Второй вопрос — а какие операции у тебя быстрые и доступные?

Да практически любые. Все базовые, кроме деления. Битовые операции. Основной(и единственный, скорее всего) таргет - это современный процессор с simd.

sutrasarki ()
Ответ на: комментарий от ZERG

Любое наличие таблицы - спасение

Нет. Причины я назвал выше.

Делай elementwise operations, будет тебе счастье, код сам векторизуется.

Это так не работает. Ничего не может векторизоваться, когда осуществляется лукап для каждого отдельного элемента в векторе.

sutrasarki ()
Ответ на: комментарий от sutrasarki

считаешь сразу 8 значение, а таблицей только одно

Ничего не может векторизоваться, когда осуществляется лукап

можно загружать из таблицы сразу по 8 значений одной инструкцией.

anonymous ()
Ответ на: комментарий от ZERG

Векторизовывать сам метод не имеет смысла, но речь не об этом. Меня интересует лишь то, что сказано в заглавии. Зачем мне давать ссылку на метод, который я сам же привёл в качестве примера, про который знаю?

Задача заключается в том, чтобы пользуясь описанными обстоятельствами найти лучшее решение. Решение лучшее, нежели вычисление каждой операции по отдельности.

sutrasarki ()
Ответ на: комментарий от anonymous

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

sutrasarki ()
Ответ на: комментарий от a1batross

Тупой ответ. Предложения с таблицей сольют. Более ничего не предлагалось. К тому же что и зачем там реализовывать? Не все слепые, чтобы тыкаться в каждый угол. И ненужно биться головою о стену, чтобы оценить результат этого действия.

sutrasarki ()
Ответ на: комментарий от a1batross

Обязательно. Выше причины оговаривались. Таблица не векторизуется, если это не специальная таблица. Это значит, что отношение вычисляемых значений в каждый момент времени - это 1:8. 256bit/float. И это минимальное соотношение. Таким образом, чтобы хотя бы догнать векторизацию - таблица должна быть минимум в 8 раз быстрее.

Даже если мы инплейс вычисляем индекс, а не читаем его из памяти и сам индекс берём из астрала за ноль, то. Производительность только этой одной операции 2/такт, т.е. 4 для 8.

Производительность же полного вычисления методом на который я ссылался изначально - это в лучшем случае 2 такта. rcp + итерация NR(fma + mul). В худшем - это 3-4 итерации. Одна итерация ~1 такт.

Поэтому, даже в случае помощи астрала при реализации фантастической таблицы x => lut[x] - она никак не может быть быстрее. Она будет как максимум примерно равной худшему случаю оппонента.

sutrasarki ()
Ответ на: комментарий от sutrasarki

Пока ты рассуждаешь в отрыве от минимально необходимой точности и объёма ожидаемых данных, разговор ни о чём.

ЗЫ

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

peregrine ★★★★★ ()
Последнее исправление: peregrine (всего исправлений: 2)
Ответ на: комментарий от peregrine

Пока ты рассуждаешь в отрыве от минимально необходимой точности

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

и объёма ожидаемых данных

Мне ненужны рассказы про объёмы данных. На саму задачу это никак не влияет.

sutrasarki ()