AlgoVerse

روش هورنر (مقدار چندجمله‌ای)

مقدار چندجمله‌ای درجه‌ی n را فقط با n ضرب و n جمع حساب می‌کند: x را پشت سر هم بیرون می‌کشد.

حساب مستقیم a_n·xⁿ + … + a_1·x + a_0 با محاسبه‌ی جداگانه‌ی هر توان، O(n²) ضرب لازم دارد (یا 2n با نگه داشتن توان قبلی). هورنر x را پشت سر هم بیرون می‌کشد:

ادامه‌ی توضیح ↓
ورودی:
coeffs 1×4 · x=3خروجی PDF

P(x) = 2x³ − 6x² + 2x − 1 در x = 3: سه ضرب و سه جمع، جواب ۵.

  1. def horner(coeffs, x):
  2. # coeffs holds one row: a_n, …, a_1, a_0 (the highest power first).
  3. y = 0
  4. rows = []
  5. for a in coeffs[0]:
  6. y = y * x + a
  7. rows.append((a, y))
  8. return y

ناوردا: بعد از خواندن k ضریب، y مقدار چندجمله‌ای‌ای است که فقط آن k ضریب بالاتر را دارد (با توان‌های کم‌شده).

شروع اجرا

y—

جدول هنوز خالی است.

متغیرهای محلی

x3

نارنجی = در همین گام عوض شد

coeffs list

[2, -6, 2, -1]

Call stack

  1. horner()خط 1
گام ۱ از ۱۷
خط سیاه = step · خط نارنجی = گام کلیدیstep: 0/4
    توضیح

    ایده

    حساب مستقیم a_n·xⁿ + … + a_1·x + a_0 با محاسبه‌ی جداگانه‌ی هر توان، O(n²) ضرب لازم دارد (یا 2n با نگه داشتن توان قبلی). هورنر x را پشت سر هم بیرون می‌کشد:

    2x³ − 6x² + 2x − 1  =  ((2·x − 6)·x + 2)·x − 1

    پس فقط n ضرب و n جمع لازم است.

    کاربردها

    • تبدیل عدد از هر مبنایی به ده‌دهی (ورودی «خواندن عدد دودویی»).
    • تقسیم چندجمله‌ای بر x − c (تقسیم مصنوعی): مقدارهای میانی y همان ضریب‌های خارج‌قسمت‌اند.

    در trace به چه چیزی نگاه کنی

    • هر سطر جدول یک ضریب و مقدار y بعد از آن است.