|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 30 Jan 2003 10:48:07
To : Alex Astafiev
Subject : Оптимизация сплайн-функции
--------------------------------------------------------------------------------
Thu Jan 30 2003 01:08, Alex Astafiev wrote to All:
AA> Требуется уменьшить количество умножений
AA> при кубической (степенной интерполяции): Ax^3 + Bx^2+Cx + D
AA> или того хлеще, в Ax^5 + Bx^3 + Cx + D
AA> предполагается что хотим посчитать все это с помощью ассемблера, на
AA> процессоре где умножение дорого.
AA> Чем можно заменить, включая _приближение_ или _эквивалент_ формулы выше?
AA> Приветствуются маленькие таблички логарифмов итп.
AA> Кстати, аргумент целочисленный и находится в диапазоне 0..4095 (12бит), а
AA> коэффициенты либо float, либо fixed-point. Либо вообще, зашиваются в
AA> табличку :)
1. Для многочлена четвертой и выше степени можно сократить число умножений
предварительной обработкой коэффициентов (см. Кнут, т.2, гл. 4, п. 4.5.4)
2. В свое время применялся метод замены умножения квадрированием, основанный
на тождестве
a*b=1/4*((a+b)^2-(a-b)^2)
Для квадратов можно держать таблицы, а деление на 4 - сдвигом.
3. Если коэффициенты неизменны - то, может, просто зашить таблицу многочлена?
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
