Tag Archives: Binary Search

ক্যালকুলেটর কীভাবে log-এর মান বের করে?

ব্যাপারটা একটু ক্যালকুলেটরের মত করে চিন্তা করা যাক। সে খুব সাদাসিধে একটি যন্ত্র। ধরা যাক, সে লগারিদম বোঝে না, কিন্তু বড়ো বড়ো সংখ্যার যোগ, বিয়োগ, গুণ, ভাগ বা বর্গমূল এক নিমিষে বের করে ফেলতে পারে। তাকে লগারিদম না শিখিয়ে আমার \(\log 2017\)-এর মান নির্ণয় করানো দরকার। বলো তো আমি এখন কী করতে পারি?

আমি হয়তো ক্যালকুলেটরকে বলতে পারি যে \(\ln (1+x)\)-এর টেইলর সিরিজ
\[\ln(1+x)=x-\frac{x^2}2+\frac{x^3}3-\cdots\;(|x| < 1)\]

সে ডানপাশের ধারাটির প্রথম কিছু পদের যোগফল নিলে \(\ln (1+x)\)-এর মোটামুটি নিখুঁত মান পাবে। এরপর সহজেই যেকোন ধ্বনাত্নক সংখ্যার \(\log\) নির্ণয় করা সম্ভব, কেননা

\[\log 2017 = \frac{\ln 2017}{\ln 10}=\frac{\ln\left(1-\frac{2016}{2017}\right)}{\ln\left(1-\frac{9}{10}\right)}\]

কিন্তু আমার এভাবে করাটা পছন্দ হল না। কারণ কাজটা বড্ড রসকষহীন।

আরও মজার কিছু ভাবা যাক।

খুব সহজেই দেখা যায় যে \[10^3 < 2017 < 10^4 \Longrightarrow 3 <\log 2017 < 4\] কিন্তু দশমিকের পরের অঙ্কটি কত হবে? \(3.1\) থেকে \(3.9\) পর্যন্ত \(10\) এর পাওয়ার নিয়ে আমি দেখতে পারি কোনটা \(2017\) এর সবচেয়ে কাছাকাছি। এরপর দশমিকের পরের দ্বিতীয় অঙ্কের জন্যও একই কাজ করতে পারি। এভাবে একটি একটি করে অঙ্ক আমি নির্ণয় করে যেতে পারি। কিন্তু প্রতিটি অঙ্কের জন্য এতবার করে \(10\) এর পাওয়ার নেওয়া আসলে অপচয়। একই কাজ বাইনারিতে করলে কেমন হয়? সেক্ষেত্রে প্রতিটি অঙ্ক \(0\) অথবা \(1\).  হিসেব করে দেখা যায় যে \(2017 < 10^{3}\times 10^{\frac{1}{2}}\approx 3162\). অতএব, বাইনারিতে দশমিকের পরের অঙ্কটি  \(0\). এর পরের অঙ্কটি? দেখা যায় যে \(2017 > 10^3\times 10^{\frac{1}{4}} \approx 1778\). অতএব, দশমিকের পরের দ্বিতীয় অঙ্কটি \(1\). বাইনারিতেও আমি একই কাজ পরবর্তী অঙ্কগুলোর জন্যে করে যেতে পারি। এভাবে \(\log\)-এর মান যেকোন ঘর পর্যন্ত নিখুঁতভাবে নির্ণয় করা সম্ভব।

এবার তাহলে ঝটপট কোড লিখে ফেলা যাক!

from math import sqrt
def log(base, num, precision = 40): 
    n, e = float(base), 1.0 
    # Find a power of base greater than num 
    while n <= num: 
        n, e = n**2, e * 2 
    # that's initial guess for log(base, num) 
    approx, log_approx = n, e 
    for i in range(precision): 
        # improve guess 
        n, e = sqrt(n), e / 2 
        if approx / n >= num: 
            approx = approx / n 
            log_approx -= e 
    return log_approx

পুনশ্চ ১: তুমি কি ধরতে পেরেছ উপরের কোডটা যে আসলে বাইনারি সার্চ?

পুনশ্চ ২: সব ক্যালকুলেটর দ্বিতীয় পদ্ধতি অনুসরণ করে না।