تفکر الگوریتمی

جواب تقریبی با اپسیلون: ریشهٔ سوم هر عدد در پایتون

۳ دقیقه مطالعه · به‌روزرسانی ۲۲ مهر ۱۴۰۵

در درس قبل ریشهٔ سوم صحیح را پیدا کردیم. اما ریشهٔ سوم ۲۹ عدد صحیح نیست؛ حدود 3.0723… است و رقم‌های اعشارش تا بی‌نهایت ادامه دارد. پیدا کردن جواب دقیق همیشه ممکن نیست، ولی می‌توانیم دنبال جوابی باشیم که به اندازهٔ کافی نزدیک است.

«به اندازهٔ کافی خوب» یعنی چه؟

به‌جای شرط guess ** 3 == cube، یک عدد خیلی کوچک به نام اپسیلون (ε) انتخاب می‌کنیم و می‌گوییم:

|guess³ - cube| < epsilon   ←   جواب به اندازهٔ کافی خوب است

اگر epsilon = 0.01 باشد، یعنی قبول داریم مکعب جوابمان حداکثر یک‌صدم با عدد اصلی فاصله داشته باشد.

الگوریتم

1. از یک حدس شروع کنید (مثلاً 0).
2. حدس را هر بار کمی (به اندازهٔ گام یا increment) زیاد کنید.
3. وقتی فاصله کمتر از اپسیلون شد، بایستید.

cube = 29
epsilon = 0.01
guess = 0.0
increment = 0.0001
num_guesses = 0

while abs(guess ** 3 - cube) >= epsilon:
    guess += increment
    num_guesses += 1

print("num_guesses =", num_guesses)
print(guess, "is close to the cube root of", cube)

اجزای کد:

• خطوط ۱ تا ۴: مقادیر اولیهٔ الگوریتم؛ عدد هدف، دقت مطلوب، حدس اول و اندازهٔ گام.
• num_guesses: شمارندهٔ تعداد حدس‌ها تا رسیدن به جواب؛ برای اینکه ببینیم الگوریتم چقدر کار کرده.
• abs: قدر مطلق. چون فاصله می‌تواند منفی باشد (حدس کوچک‌تر از جواب).
• guess += increment: تولید حدس بعدی.

بده‌بستان: دقت در برابر سرعت

با cube = 128 امتحان کنیم (جواب واقعی 5.0396842…):

دقت بیشتر = حدس‌های صد برابر بیشتر. برای cube = 5000 با گام 0.000001 حدود ۱۷ میلیون حدس لازم است.

مشاهدات:

• گام کوچک‌تر ← برنامهٔ کندتر. به‌طور تقریبی به x / step بار اجرا نیاز داریم.
• اپسیلون بزرگ‌تر ← دقت کمتر.
• گام خیلی بزرگ ← ممکن است از جواب رد شویم!

خطر رد شدن از جواب

گام را بزرگ کنیم و ببینیم چه می‌شود:

cube = 10000
epsilon = 0.01
guess = 0.0
increment = 0.01
while abs(guess ** 3 - cube) >= epsilon:
    guess += increment
# این حلقه هیچ‌وقت تمام نمی‌شود!

با گام 0.01، حدس‌ها از 21.54 به 21.55 می‌پرند. مکعب اولی حدود ۹۹۹۴ و مکعب دومی حدود ۱۰۰۰۸ است؛ هیچ‌کدام به فاصلهٔ کمتر از ۰٫۰۱ از ۱۰۰۰۰ نمی‌رسند. حلقه از جواب رد می‌شود و بعدش فاصله فقط بیشتر می‌شود: حلقهٔ بی‌نهایت!

راه‌حل: یک شرط توقف دوم اضافه کنید. وقتی حدس از خود عدد بزرگ‌تر شد، دیگر امیدی نیست:

cube = 10000
epsilon = 0.01
guess = 0.0
increment = 0.01
num_guesses = 0

while abs(guess ** 3 - cube) >= epsilon and guess <= cube:
    guess += increment
    num_guesses += 1

print("num_guesses =", num_guesses)
if abs(guess ** 3 - cube) >= epsilon:
    print("Failed on cube root of", cube)
else:
    print(guess, "is close to the cube root of", cube)

💡 درس مهم: هر حلقه‌ای که نوشتید، از خودتان بپرسید «اگر شرط پایان هیچ‌وقت برقرار نشود چه؟» یک حلقهٔ امن همیشه یک راه فرار دارد.

چرا از == برای اعداد اعشاری استفاده نمی‌کنیم؟

این را اجرا کنید:

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)

نتیجه 0.30000000000000004 و False است! کامپیوتر اعداد اعشاری را در مبنای ۲ ذخیره می‌کند و خیلی از اعداد ساده (مثل 0.1) در مبنای ۲ دقیقاً قابل نمایش نیستند، همان‌طور که 1/3 در مبنای ۱۰ نمی‌شود 0.333… را تمام کرد.

برای همین هیچ‌وقت دو عدد اعشاری را با == مقایسه نکنید. از همین ایدهٔ اپسیلون استفاده کنید:

import math
a = 0.1 + 0.2
print(abs(a - 0.3) < 1e-9)
print(math.isclose(a, 0.3))   # روش آمادهٔ پایتون

💡 این موضوع ربطی به پایتون ندارد. در C، جاوا، جاوااسکریپت و اکسل هم همین است. اگر با پول کار می‌کنید، یا با کوچک‌ترین واحد (ریال) به‌صورت int حساب کنید، یا از ماژول decimal استفاده کنید.

خلاصه

این روش کار می‌کند، ولی کند است: هر چه دقت بیشتر بخواهیم، تعداد حدس‌ها به نسبت مستقیم بیشتر می‌شود. سؤال این است: آیا می‌شود حدس‌ها را هوشمندانه‌تر تولید کرد؟ جواب، جست‌وجوی دوبخشی است؛ همان مسئله با چند ده حدس به‌جای میلیون‌ها.