У найзагальнішому вигляді статечної поліном від декількох змінних можна записати формулою
Тобто в поліном входять всі одночлени, в яких сума ступенів змінних не перевищує порядку полінома. Розглянемо алгоритми обчислення такого полінома, а також отримання масиву значень окремих одночленним, що входять такої поліном.
Обчислювати кожен одночлен по-окремо - не найкраща ідея. Якщо вірити відомій книзі Numerical Recipes. то коли машини захоплять світ, люди, винні в подібному знущанні над комп'ютером, будуть негайно страчені.
Насправді кожен одночлен порядку k може бути обчислений по одному з одночленним порядку k -1 за допомогою тільки одного множення. Наприклад, одночлени першого порядку виходять домноженіем одночлена нульового порядку (одиниці) на одну із змінних. Домножимо знову кожен з цих одночленним на одну із змінних, отримаємо всі можливі одночлени другого порядку і т.д. Одночлени k-1 -го порядку
множимо на одну із змінних і отримуємо одночлени k -го порядку.
Однак, починаючи з другого порядку з'являється проблема: одночлен буде отримано два рази. Власне, скільки є варіантів перестановки співмножників у формулі (2), стільки раз і буде отримана кожна одночлен. Щоб не робити подібних повторних обчислень, домовимося, з усіх послідовностей обчислення одночлена (2) вибирати такий, при якому індекси змінних впорядковані за зростанням. Щоб досягти цього, будемо домножать на тільки ті одночлени, які не містять змінних з номерами більше i. Тоді на домножаются тільки ті, які є ступенями, на - тільки містять і і т.д.
При такому підході кожен одночлен служить для обчислення відразу декількох інших. Ступені множаться на все D змінних. Одночлени, що містять і на всі змінні, починаючи з. І т.д. Процес обчислення в такому випадку можна представити у вигляді дерева:
Мал. 1. Процес обчислення одночленним багатовимірного полінома, представлений у вигляді дерева. Кожен вузол відповідає одночленной, а кожне ребро - домноженію на одну з змінних.
Обчислювальний процес можна подати у вигляді дерева найприродніше реалізується за допомогою рекурсивного алгоритму. У найпростішому варіанті рекурсивна процедура обчислює один одночлен і викликає себе для обчислення всіх дочірніх одночленним. Така процедура представлена нижче:
Загальна кількість одночленним в поліномі порядку n від D змінних можна розрахувати за формулою
Обчислення масиву одночленним за допомогою наведеної вище процедури виглядає так:
Якщо обчислення потрібно проводити багато разів для різних значень x. то для прискорення роботи слід позбутися рекурсії. Простий спосіб це зробити полягає в тому, щоб зробити рекурсивний обхід дерева один раз і при цьому для кожного одночлена запам'ятати номер батьківського одночлена і номер змінної, на яку він множився. Потім цю інформацію можна використовувати для обчислення одночленним без рекурсії.
Відповідний код виглядає так:
Виклик цієї процедури проводимо так:
А обчислення масиву одночленним для кожного значення змінних x так:
Практика показує, що таке нерекурсівние обчислення проводиться помітно швидше рекурсивного.
Повернемося тепер до обчислення власне полінома. Таке обчислення буде вийдуть обходом вузлів дерева одночленним з множенням їх на відповідні коефіцієнти і підсумовуванням. Це призводить нас до такої формули:
Тут індекси - номери гілок дерева за якими ми доходимо до відповідного одночлена.
Дана формула є узагальненням на багатовимірний випадок добре відомої схеми Горнера для обчислення одновимірного полінома:
Функція, яка виробляє обчислення відповідно до формули (4), представлена нижче:
Щоб приховати службові в общем-то параметри MN, depth, i_depth слід викликати цю функцію через іншу: