Таблицы Брадиса

Там вроде бы инструкция была для подобной экстраполяции.

Вот и пытаюсь ее найти. Помню, что-то вроде S = sqrt(x) + 10^((n-1)/2), но скорее всего ошибаюсь. На википелии статью про таблицы удалили по причине «нет значимости»

Ждём топик «как пользоваться логарифмической линейкой».

Линейки не застал, но Брадисом пользовался. В 2009 здесь уже был топик про таблицы с еще меньшим смыслом, чем мой. Раз топик еще живой, значит правила не нарушает. Что-то не так?

Просто непонятно зачем такой архаизм мог понадобиться в 2014.

Есть подозрение, что можно транслировать таблицы в 16чную логику и быстро считать корень.

Плохо гуглил: http://infotables.ru/matematika/80-tablitsa-bradisa-kvadraty-vozvedenie-v-kva...

А вики-п...ры — идиоты, если правда. Уже не первая статья энциклопедии(!), которую изымают за «незначимость». (Вредные знания, что-ли?)

ты про что именно: логарифмы, корни или что?

Кстати, про логарифмическую линейку не зря напомнили, т.к. она — обязательное приложение к таблице Брадиса.

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

Даже в прошлом веке люди уже калькуляторами пользовались.

Ждём топик «как пользоваться логарифмической линейкой».

Есть подозрение, что пользоваться ей на этом форуме умеют не больше 5%. быстрофикс: не больше 0.5%.

//я не умею

Есть подозрение, что можно транслировать таблицы в 16чную логику и быстро считать корень.

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

опа. вспомнил 6 класс математики.

Мне квадратные корни: http://infotables.ru/matematika/59-tablitsa-bradisa-kvadratnye-korni

Но тут так и не разбирается.

Квадратные корни. Именно для чисел > 100.

Используй логарифмическую линейку. Или так: [latex]\sqrt{x} = 10\sqrt{\frac{x}{100}} = 100\sqrt{\frac{x}{10000}}\ldots[/latex]

Ну ведь абсолютно аналогично ведь:

sqrt(1024) = sqrt(10.24 * 10^2) = sqrt(10.24) * sqrt(10^2) = (3.194 + 0.006) * 10 = 32

Где твоё аналитическое мышление?

Я матан только по английской вики смотрю, в нашей нихрена не понять.

Ок, взял значение из столбца. Не кинете мануалом, какой столбец брать и как пользоваться поправками?

Спасибо.

Из моего примера (корень из 10.24):

• строка 10.
• столбец 2 (следующая цифра, т.е. 10.2)
• значение 3.194
• та же строка, столбец поправки 4 (следующая цифра, т.е. 10.24)
• поправка 6
• результат: 3.194 с поправкой 6 = 3.200

Ну так и надо делать. А промежуточные значения интерполяцией с помощью первых 2-3 членов ряда Тейлора.

Тэйлор сходится и работает на порядок медленнее, чем Герон.

Тебе шашечки нужны или ехать, внук Фейнмана?

Раздели на сто, примени таблицу, умножь на сто.

Спасибо за комплимент.

Спасибо большое.

Раздели на сто, примени таблицу, умножь на сто.

И получи завышенный результат...

Я хочу ее до 256 продлить.

Вопрос только «Зачем?» Значения 1.0 — 99.99 покрываеют всё.

Hint:

• 1023 = 10.23 * 10^2
• 256 = 2.56 * 10^2
• 0.000245 = 2.45 * 10^-4
• ...

Вопрос только «Зачем?» Значения 1.0 — 99.99 покрываеют всё.

Чтобы умножение и деление проводить не через * и /, а через << и >>.

И ты думаешь, что двигать «в голове» бинарные значения проще, чем десятичное деление/умножение?

Цель я так и не понял. Таблицы все эти создавались в до-компьютерную эру, что бы считать «на бумажке».

Люди бинарно не мыслят. А компьютерам эти таблицы не нужны.

Так в чём профит?

Совсем больной?

А компьютерам эти таблицы не нужны.

В соседнем топике я немного осветил тему что сейчас мучаю. Суть в том, чтобы написать интовый sqrt, который будет работать быстрее, чем ассемблерный fsqrt, который стоит внутри math.h/sqrt(double). Ну можете считать это моим бзиком, но я хочу из всех своих вычислений выкинуть float'ы.

На данный момент у меня такие данные - есть функция, в которой один раз вызывается sqrt и делаются некоторые вычисления. Она дергается 100 000 раз и засекается время. На math.h/sqrt это дело занимает 6.4 секунды. На моих различных реализациях по-разному. Тут типа табличка, с моими «пометками». Как видите, я пробовал все методы, которые мог найти. Минимальное время, к которому я подобрался это 7.6 (в табличке 7.7, я уже несколько коэффициенты успел улучшить).

Один из методов - это массив [0..MAX_UINT16-1], в котором содержатся квадраты значений i-счетчика. Занимает 256 кб в памяти, чем мне и не нравится. Суть в том, что после получения входного значения оно ищется в массиве а на выход выдается i, что и является ответом. 65536 ячеек дают 15 итераций на двоичном поиске и это очень много (в табличке это tables), если делать отсекание по первому биту и преустанавливать рамки, то это чуть быстрее (tables1lvl).

Теперь я хочу попробовать метод без поиска - строю в памяти (предварительно) таблицы брадиса - 256 х (16 + 16) это 32 КБ памяти, что гораздо меньше 256 и что я уже считаю приемлемым (хотя все равно введу функцию, чтобы инициализировать матблок по запросу, а без инициализации указатели на функции выставлять на более медленные варианты (указатели - это чтобы в каждую функцию не ставить условие на флаг - медленнее). Так вот - пришло число, лезем в таблицу, в которой не дробные значения, а так, как у нас максимум ответа будет 65536, то в таблице будут значения размером в 4 шестнадцатиричныйх разрядов (гм, т.е. можно тогда не 4 байта на число, а 2, с выключением выравнивания это всего 16 КБ, лол. Но тут надо скорость мерять). Так вот, получается, что вычисление корня сведется к:
0. С пустой функцией выполнение занимает 2.4 секунды времени на 100 000 итерациях. 1. Получение самого левого установленного бита в числе (через таблицы это 3.02 с) 2. Дальше мы сдвигаем значение на n-8 бит, чтобы получить самый левый байт. 3. Смотрим в таблице значение по байту и первой тетрадой, например это будет 12[.]345 (точку нарисовал условно, там будет целое) 4. Смотрим вторую тетраду после полученного байта и берем поправку (опять таки - прямой доступ к таблице - почти ноль. 5. Сносим влево на (m >> 1), где m - первоначальная позиция самого левого установленного бита.

Корень получен. В теории быстрее, чем что-то другое, потому что нет никаких итераций. Возможно я сейчас неправильно посчитал разряды и я таким образом недосчитался целого байта точности конечного результата. Но согласитесь, что если корень найден с точностью +-128, то найти оставшееся можно за пару шагов (еще не придумал, как, но все же)

Не там ты оптимизируешь. И вряд ли ты придумаешь способ лучший, чем придуманные до тебя за 100 лет развития информатики.

Глянь лучше сюда: http://netstorage.iar.com/SuppDB/Public/SUPPORT/000419/AN-G-002.pdf

PS: Таблицы Брадиса — это тоже только апроксимизация.

Глянь лучше сюда

Уже видел в виде разобранной статьи на русском. То, что описано в pdf - гогно, по причине того, что они, используя алгоритм Герона делают всего 2 итерации, а по хорошему там нужен while ([xn+1] - [xn]).

Не там ты оптимизируешь.

А я иду по порядку. И когда вижу функцию, которая в продакшене может вызываться 1280х800х60 раз в секунду - оптимизирую. Проблемы?

PS: Таблицы Брадиса — это тоже только апроксимизация.

А мне нужна точность до целых.

мне нужна точность до целых

а по хорошему там нужен while ...

Путаешься в показаниях. :)

Проблемы?

У меня? Да я так, мимо проходил. Какие у меня проблемы? ;)

когда вижу функцию, которая

Premature optimization is the root of all evil, помни об этом.

Оптимизировать надо с профайлером и то только там, где надо, а не где показалось.

Путаешься в показаниях. :)

Где? Я ж вам сказал, что там нужен while, пока разница между двумя итерациями меньше 1 (или 0 в случае целочисленных) - то прерываем цикл.

Оптимизировать надо с профайлером и то только там, где надо, а не где показалось.

НА! Задолбали уже о своих преждевременных оптимизациях говорить! 40 раз уже объяснил.

Мог бы сразу написать, что тебе нужно.

Значит так. Старшие биты результата берёшь из заранее посчитанной таблицы. Получишь некоторое приближение. Потом это приближение улучшаешь методом Ньютона. Обычно достаточно 1-2 итерации, так как для квадратного корня он сходится с квадратичной скоростью. Вот пример для ардуины: https://github.com/Shulyaka/quadro/blob/master/fplib.h

Я ж вам сказал, что там нужен while, пока разница между двумя итерациями меньше 1 (или 0 в случае целочисленных) - то прерываем цикл.

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

Старшие биты результата берёшь из заранее посчитанной таблицы. Получишь некоторое приближение.

Уже. Надо будет не только Ньютоном проверить. Просто есть мысли просчитать таблицу поправок (как у Брадиса) и применять их же. В общем попробую оба метода.

Это лишнее, учитывая квадратичную скорость у Ньютона.

У Герона тоже квадратичная, но тем не менее ему иногда до 32х итераций надо.

Герон - это тот же Ньютон. 32 итерации - эта какая-то неправильная квадратичная сходимость. Каждая итерация удваивает число верных разрядов. Начав с 8, через 2 итерации их будет никак не меньше 32.