বাইনারি লগারিদম

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে
পরিভ্রমণে ঝাঁপ দিন অনুসন্ধানে ঝাঁপ দিন


log2x

গনিতে, বাইনারি লগারিদম (log2n) হল সেই শক্তিমাত্রা-  n মান অর্জন করতে 2 এর মাত্রা যতটুকু বাড়াতে হবে। যার মানে, যে কোন বাস্তব সংখ্যা x এর জন্য,

উদাহরণস্বরূপ 1 এর বাইনারি লগারিদমের মান 0, 2 এর বাইনারি লগারিদমের মান 1, 4 এর বাইনারি লগারিদমের মান 2 এবং 32 এর বাইনারি লগারিদমের মান 5.

2 ভিত্তিক লগারিদমকে বাইনারি লগারিদম বলা হয়। আর বাইনারি লগারিদম ফাংশন হল দুই শক্তিমাত্রার বিপরীত ফাংশন। log2 ছাড়াও বাইনারি লগারিদমকে lg, ld, lb (এই গাণিতিক প্রতীকগুলো ISO 31-11 ও ISO 80000-2 কর্তৃক অগ্রাধিকারপ্রাপ্ত)এবং ( 2 ভিত্তিক লগ আগে উল্লেখ করে নিয়ে) log হিসেবে প্রকাশ করা যায়।

ইতিহাস বলে, লিওনার্ড অয়লার প্রথম সঙ্গীততত্ত্বে বাইনারি লগারিদম প্রয়োগ করেন:দুইটি সুরের কম্পাংকের অনুপাতের বাইনারি লগারিদম অষ্টকের সংখ্যা প্রকাশ করে যা দ্বারা সুরের পার্থক্য বোঝা যায়। বাইনারি লগারিদম বাইনারি সংখ্যা পদ্ধতিতে প্রতিনিধিত্বকারী সংখ্যার দৈর্ঘ্য নির্ণয় করতে অথবা ইনফরমেশন থিওরিতে কোন মেসেজ এনকোড করার জন্য প্রয়োজনীয় বিট সংখ্যা গণনা করতে ব্যবহৃত হয়। কম্পিউটার বিজ্ঞানে এটি বাইনারি অনুসন্ধান ও এ সংক্রান্ত এলগরিদমে প্রয়োজনীয় ধাপ গণনা করে।এছাড়া সমাবেশ-তত্ত্ব, বায়োইনফরমেটিক্স,বিভিন্ন স্পোর্টস টুর্নামেন্টের ডিজাইন এবং ফটোগ্রাফিতে বাইনারি লগারিদম প্রায়শই ব্যবহার করা হয়।

বাইনারি লগারিদম স্ট্যান্ডার্ড সি প্রোগ্রামের গাণিতিক ফাংশনে ও অন্যান্য গাণিতিক সফটওয়্যারের প্যাকেজে অন্তর্ভুক্ত করা হয়েছে। বাইনারি লগারিদমের পূর্ণসংখ্যা মানটি ফার্স্ট সেট অপারেশন করে অথবা ভাসমান বিন্দুর মানের সূচক থেকে পাওয়া যায়। লগারিদমের ভগ্নাংশ কার্যকর পদ্ধতিতে নির্ণয় করা যায়।

ইতিহাস[সম্পাদনা]

লিওনার্ড ইউলার ১৭৩৯ সালে সর্বপ্রথম সঙ্গীততত্ত্বে বাইনারি লগারিদম প্রয়োগ করেন

প্রাচীন কাল থেকেই দুইয়ের শক্তিমাত্রা সম্পর্কে মানুষ অবগত ছিল ; উদাহরণস্বরূপ, ইউক্লিডের "ইলিমেন্ট" গ্রন্থের IX.32 পরিচ্ছেদে (দুইয়ের শক্তিমাত্রাগুলোর উৎপাদক নির্ণয়ে) ও IX.36 পরিচ্ছেদে (ইউক্লিড-ইউলার উপপাদ্যের অর্ধাংশে- জোড় পারফেক্ট সংখ্যার কাঠামোতে) এর উপস্থিতি দেখা যায়।আর দুইয়ের যে কোন শক্তিমাত্রার লগারিদম দুইয়ের শক্তিমাত্রাগুলোর বিন্যাসক্রমে এর অবস্থান নির্দেশ করে। এ কারণে মিশেল স্টিফেলকে ১৫৪৪ সালে বাইনারি লগারিদমের প্রথম সুপরিচিত তালিকা প্রকাশের জন্য কৃতিত্ব দেয়া হয়। তার এরিথমেটিক্যা ইনটিগ্রা গ্রন্থে বেশ কয়েকটি সারণি আছে যাতে পূর্ণসংখ্যাগুলোকে তাদের অনুরূপ দুইয়ের শক্তিমাত্রা সহ দেখানো হয়েছে। এই সারণিগুলোর সারি বিপরীতকরণ করলে সেগুলোকে বাইনারি লগারিদমের টেবিল হিসেবে প্রকাশ করা যায়।[১][২]

স্টিফেলের পূর্বে অষ্টম শতকের ভারতীয় জৈন গণিতবিদ বীরসেনাকে বাইনারি লগারিদমের অগ্রদূত হিসেবে স্বীকৃতি দেয়া হয়। বীরসেনার "অর্ধচ্ছেদের" ধারণাটিকে এভাবে সংজ্ঞায়িত করা হয়েছিল- কোন একটি প্রদত্ত সংখ্যা দুই দ্বারা যতবার নিঃশেষে বিভাজিত হতে পারে, তাকে অর্ধচ্ছেদ বলা হবে। এই সংজ্ঞাটিই এমন একটি ফাংশনের ধারণা দেয় যা ২ এর শক্তিমাত্রার জন্য বাইনারি লগারিদমের অনুরূপ হয়। [৩] তবে অন্যান্য পূর্ণ সংখ্যার জন্য এটি বাইনারি লগারিদমের চেয়ে ভিন্ন মানের ছিল; কারণ সেসব ক্ষেত্রে লগারিদম নয়, এটি ২-মাত্রিক ক্রম প্রদান করত। [৪]

বাইনারি লগারিদমের আধুনিক রূপ, যে কোন সংখ্যা (শুধু ২ এর শক্তিমাত্রা নয়) -র উপর প্রয়োগ করার বিষয়টি ১৭৩৯ সালে লিওনার্ড অয়লার স্পষ্টভাবে বিবেচনা করেন। তথ্য তত্ত্ব ও কম্পিউটার বিজ্ঞানে আরও তাৎপর্যপূর্ণ প্রয়োগের অনেক আগেই অয়লার সঙ্গীত তত্ত্বে বাইনারি লগারিদমের প্রয়োগকে প্রতিষ্ঠিত করেন। তার কর্মপরিধির অংশ হিসেবে, অয়লার ১ থেকে ৮ পর্যন্ত পূর্ণসংখ্যার বাইনারি লগারিদমগুলোর একটি সারণি প্রকাশ করেন যাতে দশমিকের পর সাত ঘর পর্যন্ত নির্ভুল মান পাওয়া যাবে।

সংজ্ঞা এবং বৈশিষ্ট্য[সম্পাদনা]

বাইনারি লগারিদমকে দুই শক্তিমাত্রার কোন ফাংশনের বিপরীত ফাংশন হিসেবে সংজ্ঞায়িত করা যায় যা অবশ্যই কোন বাস্তব ধনাত্মক সংখ্যার ক্রমবর্ধমান ফাংশন হবে যে কারণে এর একটি অনন্য ফাংশন থাকবে। বিকল্প উপায়ে, একে ln n/ln 2 আকারে সংজ্ঞায়িত করা যায়, যেখানে ln একটি প্রাকৃতিক লগারিদম এবং যে কোন প্রমিত উপায়ে সংজ্ঞায়িত। এই সংজ্ঞায় জটিল লগারিদমের ধারণা প্রয়োগ করলে বাইনারি লগারিদমকে জটিল সংখ্যার আলোচনায় ব্যবহার করা যায়।[৫]

অন্যান্য লগারিদমের মত, বাইনারি লগারিদম নিম্নোক্ত সমীকরণগুলি মেনে চলে, যা গুণ ও সূচক বের করার সাথে বাইনারি লগারিদমের যোগসূত্র প্রকাশকারী সূত্রগুলোকে সহজ করে তুলতে ব্যবহৃত হতে পারে-[৬]

অঙ্কপাতন বা প্রতীক দিয়ে প্রকাশ[সম্পাদনা]

গণিতে যে কোন সংখ্যা n এর বাইনারি লগারিদমকে প্রায়ই log2n হিসেবে লেখা হয়।[৭] তবে বিশেষ করে বিভিন্ন ক্ষেত্রে প্রয়োগের সময় এই ফাংশনকে আরও বেশ কিছু উপায়ে প্রকাশ বা প্রস্তাব করা হয়।

কিছু লেখক বাইনারি লগারিদমকে lg n[৮][৯] হিসেবে লেখেন, "দ্যা শিকাগো ম্যানুয়াল অফ স্টাইল" গ্রন্থে এই নোটেশনটি তালিকাভুক্ত করা হয়েছিল। [১০]ডোনালড নাথ এই নোটেশন ব্যবহারের পরামর্শদাতা হিসেবে এডওয়ার্ড রেইনগোল্ডকে কৃতিত্ব দেন, কিন্তু রেইনগোল্ড সক্রিয় হওয়ার পূর্বেই তথ্য তত্ত্ব ও কম্পিউটার বিজ্ঞান উভয় ক্ষেত্রে এর ব্যবহার ছিল। লগারিদমের সাধারণ ভিত্তি ২- এ কথাটি পূর্বে উল্লেখ করে বাইনারি লগারিদমকে log n হিসেবেও লেখা হয়। একই ফাংশনের জন্য আরেকটি নোটেশন ব্যবহার করা হয় (বিশেষ করে জার্মান বৈজ্ঞানিক সাহিত্যে) আর তা হল "ল্যাটিন লগারিদমাস ডুয়ালিস" বা " লগারিদমাস ডায়াডিস" গ্রন্থে বর্ণিত প্রতীক ld n। দ্যা ডিআএন ১৩০২, আইএসও ৩১-১১ এবং আইএসও ৮০০০০-২ মানদণ্ড আরও একটি নোটেশনকে সুপারিশ করে আর তা হল lb n। এ সকল মানদণ্ড অনুযায়ী, বাইনারি লগারিদমে log n ব্যবহার করা উচিত নয় কারণ এ প্রতীকটি সাধারণ লগারিদম log10 n এর জন্য সংরক্ষিত।

প্রয়োগ[সম্পাদনা]

তথ্য তত্ত্ব[সম্পাদনা]

কোন ধনাত্মক পূর্ণ সংখ্যা n এর বাইনারি প্রকাশের ক্ষেত্রে অংকের সংখ্যা হয় 1 + log2n এর পূর্ণসংখ্যাবাচক অংশ অর্থাৎ

তথ্য তত্ত্বে, নিজস্ব তথ্য এবং তথ্য এনট্রপি পরিমাণের সংজ্ঞা প্রায়ই বাইনারি লগারিদমের সাথে প্রকাশ করা হয়, যেখানে সংশ্লিষ্ট বিটকে তথ্যের মৌলিক একক হিসেবে তৈরি করা হয়। তাছাড়া, প্রাকৃতিক লগারিদম এবং ন্যাট (তথ্যের মৌলিক একক) -ও এ সকল সংজ্ঞার জন্য বিকল্প অংকপাতনে ব্যবহার করা হয়।[১১]

সংযুক্তকারিতা তত্ত্ব[সম্পাদনা]

১৬ খেলোয়াড়ের অংশগ্রহণে একবার হারলেই বাদ এমন একটি টুর্নামেন্টের বাইনারি বৃক্ষ। গাছটির উচ্চতা (টুর্নামেন্টে রাউন্ডের সংখ্যা )হল খেলোয়াড় সংখ্যার বাইনারি লগারিদম, এখানে প্রাপ্ত মানের কাছাকাছি পূর্ণ সংখ্যা নেয়া হয়।

যদিও বিশুদ্ধ গণিতের অনেক শাখা যেমন- সংখ্যা তত্ত্ব ও গাণিতিক বিশ্লেষণে বাইনারি লগারিদমের চেয়ে প্রাকৃতিক লগারিদম অনেক গুরুত্বপূর্ণ, তবে সংযুক্তকারিতা তত্ত্বে বাইনারি লগারিদমের বেশ কিছু প্রয়োগ রয়েছেঃ

  • n সংখ্যক পাতা বিশিষ্ট প্রতিটি বাইনারি বৃক্ষের উচ্চতা অন্তত log2n হয়, এই সমতা বজায় থাকে যখন n ২ এর শক্তিমাত্রা হয় এবং গাছটি সম্পূর্ণ বাইনারি বৃক্ষ হয়। অনুরূপভাবে, n সংখ্যক শাখা নদীর প্রবাহ আছে এমন একটি নদী ব্যবস্থার স্ট্রালার সংখ্যার মান হবে সর্বোচ্চ n সংখ্যক পৃথক সেট নিয়ে গঠিত প্রতিটি সেট পরিবারের সংযোগে অন্তত log2n + 1 সংখ্যক উপাদান থাকে, এই সমতা বজায় থাকে যখন সেট পরিবারটি একটি শক্তি সেট হয়।
  • যখন পরিবারটি একটি শক্তি সেট হয় , n সংখ্যক ভিন্ন ভিন্ন সেট সংবলিত কোন সেট পরিবারের সংযোগে গঠিত সেটে অন্তত log2n সংখ্যক উপাদান থাকবে।
  • n শীর্ষবিশিষ্ট প্রতিটি আংশিক ঘনকে কমপক্ষে log2n সংখ্যক সমমাত্রা থাকে আর সর্বোচ্চ 1/2 n log2n সংখ্যক ধার থাকে, এই সমতা বজায় থাকে যখন আংশিক ঘনকটি একটি অধিঘনক লেখচিত্র উৎপন্ন করে।
  • রামসে-র উপপাদ্য অনুসারে, প্রতিটি nসংখ্যক শীর্ষবিশিষ্ট একমুখী লেখচিত্রে হয় n লগারিদম আকারের একটি উপদল বা স্বাধীন সেট থাকবে। এর কোন সুনিশ্চিত-সুনির্দিষ্ট আকার জানা যায় নি, তবে এর আকারের সেরা সীমানাগুলো বাইনারি লগারিদমের সাথে জড়িত। বিশেষ করে, সকল গ্রাফেই অন্তত 1/2 log2{n (1 − o(1)) আকারের একটি উপদল বা স্বাধীন সেট থাকবে এবং প্রায় সব গ্রাফেই 2 log2n (1 + o(1)) আকারের চেয়ে বড় কোন উপদল বা স্বাধীন সেট থাকবে না।
  • গিলবার্ট-শ্যানন-রিডের র‌্যান্ডম শাফল মডেলের গাণিতিক বিশ্লেষণ থেকে দেখানো যায়, রাইফেল শাফল ব্যবহার করে ও nসংখ্যক ডেক কার্ড শাফল করে প্রায় পুরোপুরি একটি র‌্যান্ডম বিন্যাস-বণ্টন পেতে প্রায় 3/2 log2n বার কার্ড শাফল করতে হয়। এই হিসাবের ওপর ভিত্তি করেই মত দেয়া হয় যে, ৫২ টি কার্ড ডেককে সাত বার শাফল করা উচিত।

গণনাগত জটিলতা[সম্পাদনা]

[একটি সাজানো শ্রেণীবিন্যাসে বাইনারি অনুসন্ধান, এই অ্যালগরিদমে বাইনারি লগারিদমের সাথে সময়গত জটিলতা সম্পৃক্ত থাকে

প্রায়শই অ্যালগরিদমের বিশ্লেষণে বাইনারি লগারিদমের ব্যবহার দেখা যায়, এর কারণ শুধু অ্যালগরিদমে বাইনারি সংখ্যার গণিতের বারংবার ব্যবহারই নয়, আরও একটি কারণ হল- দুই উপায়ে ব্রাঞ্চিং এর উপর ভিত্তি করে অ্যালগরিদম বিশ্লেষণের সময় বাইনারি লগারিদম কাজে লাগে। যখন কোন সমস্যার সমাধানের জন্য প্রাথমিকভাবে n সংখ্যক উপায় থাকে, এবং অ্যালগরিদমের প্রতিটি ইটারেশন বা পুনরাবৃত্তির জন্য এই উপায় সংখ্যা ২ এর কোন যে কোন গুণক হারে হ্রাস পায়, তখন যে কোন একটি উপায়কে নির্বাচন করার জন্য প্রয়োজনীয় পুনরাবৃত্তির সংখ্যা হবেlog2n। এই ধারনাটি বেশ কিছু অ্যালগরিদম ও তথ্য কাঠামোর বিশ্লেষণে ব্যবহৃত হয়। উদাহরণস্বরূপ, কোন বাইনারি অনুসন্ধানে, সমাধানের জন্য রাখা সমস্যার আকার প্রতিটি পুনরাবৃত্তিতে অর্ধেক হয়ে যায়, আর তাই কোন সমস্যাকে ১ আকারে নিয়ে এসে, ধ্রুব সময়ে সহজেই সমাধান করতে মোটামুটি log2n সংখ্যক পুনরাবৃত্তির প্রয়োজন হয়। অনুরূপভাবে, n সংখ্যক উপাদান ধারণ করা একটি সুষম বাইনারি অনুসন্ধান বৃক্ষের উচ্চতা হয় log2(n + 1) − 1[১২]

একটি অ্যালগরিদম কত সময় ধরে চলবে, তা সাধারণত বড় হাতের O দিয়ে প্রকাশ করা হয়, যা ধ্রুব গুণক এবং নিম্ন মাত্রার পদগুলোকে বাদ দিয়ে প্রকাশকে সহজ করতে ব্যবহৃত হয়। যেহেতু বিভিন্ন ভিত্তির জন্য পাওয়া বিভিন্ন লগারিদমের মান একে অন্যের চেয়ে শুধু একটি ধ্রুব গুণকের সাপেক্ষে ভিন্ন হয়, তাই যে লগারিদমটি O(log2n)সময় ধরে চলে, সেটি O(log13 n) সময় ধরে চলে বলেও ধরা যায়। তাই O(log n)O(n log n) এর বেলায় লগারিদমের ভিত্তি গুরুত্বপূর্ণ নয়, তাই এসব ক্ষেত্রে ভিত্তি বাদ দেয়াই যেতে পারে। [৮][১৩]তবে, সময় সীমার সূচকে যে লগারিদমগুলো থাকে, তাদের ভিত্তিকে বাদ দেয়া যায় না। উদাহরণস্বরূপ, O(2log2n) আর O(2ln n)একই নয়, কারণ প্রথমটি O(n) এর সমান আর পরেরটি O(n0.6931...) এর সমান।

যে সকল অ্যালগরিদম O(n log n) সময় ধরে চলে, তাদেরকে কখনো কখনো লিনিয়ারিথমেটিক বলা হয়। O(log n) বা O(n log n) সময় ধরে চলা কিছু অ্যালগরিদমের উদাহরণ হলঃ

  • গড় সময়ে দ্রুত বাছাই এবং অন্যান্য তুলনামূলক বাছাইয়ের অ্যালগরিদম
  • সুষম বাইনারি অনুসন্ধান বৃক্ষে খোঁজা
  • বর্গ করে সূচকীয় বৃদ্ধি
  • দীর্ঘতম ক্রমবর্ধমান অনুক্রম

কিছু বন্টিত ও লব্ধ অ্যালগরিদম যেমন- {{math|O(nlog23)} সময়ে n বিট সংখ্যা গুণের জন্য কারাতসুবা অ্যালগরিদম[১৪] এবং O(nlog2{7)সময়ে n × n ম্যাট্রিক্স গুণের জন্য স্ট্রাসেন অ্যালগরিদমে বাইনারি লগারিদম ঘটে।[১৫] এ সকল অ্যালগরিদম চলার সময় বাইনারি লগারিদম ঘটার এই ব্যাপারটি "ভাগ ও লাভের পুনরাবৃত্তির জন্য মুখ্য উপপাদ্য"- র সাহায্যে ব্যাখ্যা করা যায়।

বায়োইনফরমেটিক্স[সম্পাদনা]

প্রায় ৮৭০০ জিনের জন্য একটি মাইক্রোঅ্যারে । এই জিনের অভিব্যক্তি হার বাইনারি লগারিদম ব্যবহার করে তুলনা করা হয়

বায়োইনফরমেটিক্সে কোন একটি জৈব উপাদানের নমুনায় কত বেশি বিভিন্ন জিনের উপস্থিতি বিদ্যমান আছে তা পরিমাপ করতে মাইক্রোঅ্যারে ব্যবহার করা হয়। জিন প্রকাশের বিভিন্ন হারকে প্রায়শই দুইটি হারের অনুপাতের বাইনারি লগারিদম হিসেবে প্রকাশ করা হয়। বাইনারি লগারিদমের সাহায্যে অভিব্যক্তির হারকে সুবিধাজনকভাবে তুলনা করা যায়। যেমন- একটি দ্বিগুণ অভিব্যক্তির হারকে ১ এর লগ অনুপাত হিসেবে লেখা যায়, আবার অর্ধেক অভিব্যক্তির হারকে -১ এর লগ অনুপাত হিসেবে প্রকাশ করা যায় আর একটি অপরিবর্তিত অভিব্যক্তির হারকে ০-র লগ অনুপাত হিসেবে প্রকাশ করা যায়।[১৬]

এ উপায়ে প্রাপ্ত তথ্য থেকে বিন্দুগুলোকে প্রায়ই একটি বিক্ষিপ্ত লেখচিত্রে দেখানো হয় যেখানে এক বা উভয় অক্ষ বরাবরই তীব্রতার অনুপাতের বাইনারি লগারিদম থাকে, অথবা এমএ প্লট ও আরএ প্লট দিয়েও দেখানো যায় যারা এসব বিক্ষিপ্ত লেখচিত্রকে আবর্তিত করে ও আনুপাতিক হারে বর্ধিত করে।[১৭]

সংগীত তত্ত্ব[সম্পাদনা]

সংগীত তত্ত্বে দুইটি স্বরের বিরামকাল বা প্রত্যক্ষ পার্থক্য তাদের কম্পাঙ্কের অনুপাত দ্বারা নির্ধারিত হয়। ছোট লব ও হর সংবলিত মূলদ সংখ্যার অনুপাতের ব্যবধানগুলো শ্রুতিমধুর বলে অনুভূত হয়। সবচেয়ে সহজ ও সবচেয়ে গুরুত্বপূর্ণ বিরামকাল হল "অষ্টক"- যাতে কম্পাংকের অনুপাত থাকে ২:১। যে কয়টি অষ্টক সংখ্যা দিয়ে দুইটি স্বরের ব্যবধান নির্ধারিত হয়, তাকে স্বরদ্বয়ের কম্পাংকের অনুপাতের বাইনারি লগারিদম বলে।[১৮]

সুরকরণ পদ্ধতি ও সংগীত তত্ত্বের অন্যান্য দিক- যেগুলোর জন্য স্বরগুলোর মধ্যে আরও ভালো পার্থক্য করার দরকার হয়, সেসব শাখা অধ্যয়নের জন্য বিরামকালের দৈর্ঘ্যের এমন একটি পরিমাপ থাকলে ভালো হয় যা অষ্টকের চেয়েও ভালো আর (কম্পাংক অনুপাতের মত) গুণনীয় নয়, বরং (লগারিদমের মত) যোজনীয়। তার মানে, x,y,z স্বরগুলো যদি স্বরের একটি ক্রমবর্ধমান ক্রম তৈরি করে, তাহলে x ও y এর মধ্যবর্তী বিরামকাল আর y ও z এর মধ্যবর্তী বিরামকালের যোগফল হবে x ও z এর মধ্যবর্তী বিরামকাল। এ ধরনের পরিমাপকে সেন্ট দিয়ে প্রকাশ করা হয়, যা অষ্টকে ১২০০ টি সমান বিরামকালে বিভক্ত করে ( প্রতিটি ১০০ সেন্টে ১২ টি সেমিটোন থাকে)। গাণিতিকভাবে, f1f2 কম্পাংকের দুইটি স্বর থাকলে, f1 থেকে f2 এর মধ্যবর্তী সেন্ট সংখ্যা হবে-

মিলি-অষ্টক-কেও একই ভাবে সংজ্ঞায়িত করা হয়, কিন্তু সেক্ষেত্রে ১২০০ এর পরিবর্তে ১০০০ দিয়ে গুণ করা হয়। [১৯]

খেলার সূচী নির্ধারণ[সম্পাদনা]

প্রতিযোগিতামূলক খেলাধুলায় - যেখানে প্রতিটি খেলা বা ম্যাচে দুইজন খেলোয়াড় বা টিম অন্তর্ভুক্ত থাকে, সেখানে বাইনারি লগারিদম একটি "একবার হারলেই বাদ এমন টুর্নামেন্ট"-এ কয় রাউন্ড খেলা থাকবে, তা নির্ধারণ করে। যেমন- ৪ জন খেলোয়াড় নিয়ে করা একটি টুর্নামেন্টে বিজয়ী নির্ধারণ করতে log24 = 2 রাউন্ড খেলার দরকার হবে, ৩২ টিম নিয়ে করা একটি টুর্নামেন্টে log232 = 5 রাউন্ড খেলার দরকার হবে। এ ক্ষেত্রে, n সংখ্যক খেলোয়াড় বা দলের জন্য, যেখানে n, ২ এর কোন শক্তিমাত্রা নয়, সেখানে log2nএর মান নিকটবর্তী কোন পূর্ণসংখ্যা ধরা হয়, কারণ বাদবাকি প্রতিযোগীরা খেলবে না এমন অন্তত একটি রাউন্ড খেলার দরকার আছে। যেমন- log26 এর মান প্রায় 2.585 , নিকটবর্তী পূর্ণসংখ্যা ধরলে যার মান হয় 3- যার মানে ৬ টি টিম খেলছে এমন একটি টুর্নামেন্টে ৩ রাউন্ড খেলার দরকার হবে। ( হয় দুইটি টিম প্রথম রাউন্ডে বসে থাকবে অথবা একটি টিম দ্বিতীয় রাউন্ডে বসে থাকবে) । "সুইস সিস্টেম টুর্নামেন্ট"-এও একজন মাত্র বিজয়ীকে নির্ধারণ করতে একই পরিমাণ রাউন্ড খেলার প্রয়োজন হয়।[২০]

ফটোগ্রাফি[সম্পাদনা]

ফটোগ্রাফিতে এক্সপোজারের মান ফিল্ম বা সেন্সরে কতটুকু আলো পৌঁছায়, তার বাইনারি লগারিদমে পরিমাপ করা হয়। ওয়েবার-ফিঞ্চারের সূত্রটি আলোতে মানুষের দৃষ্টি ব্যবস্থার একটি লগারিদমিক প্রতিক্রিয়া বর্ণনা করে। এক্সপোজারের একটি একক বিরাম একটি ২ ভিত্তিক লগারিদমিক স্কেলে এক একক।[২১][২২] আরো সঠিকভাবে, একটি ফটোগ্রাফের এক্সপোজার মান এভাবে- সংজ্ঞায়িত করা হয়

যেখানে N হল এফ-নাম্বার যা এক্সপোজারের সময় লেন্সগুলোর রন্ধ্র সংখ্যা পরিমাপ করে, এবং t হল এক্সপোজারের সময় যা সেকেন্ডে প্রকাশিত হয়।[২৩]

বাইনারি লগারিদম (বিরাম হিসেবে প্রকাশিত) ডেনসিটোমেট্রিতেও ব্যবহার করা হয়, যা হালকা-সংবেদনশীল সামগ্রী বা ডিজিটাল সেন্সরগুলির পরিবর্তনশীল পরিসর প্রকাশ করতে পারে।[২৪]

হিসাব[সম্পাদনা]

১৯৭৪ সালের TI SR-50 সায়েন্টিফিক ক্যালকুলেটর- দ্বিতীয় সারিতে ln ও log বাটন রয়েছে ; কিন্তু log2 key নেই

অন্যান্য ভিত্তি থেকে রূপান্তর[সম্পাদনা]

যে সকল ক্যালকুলেটরে log2 ফাংশনটি নেই,সে সব ক্যালকুলেটরে log2n হিসাবের সহজ উপায় হল- প্রাকৃতিক লগারিদম (ln) বা সাধারণ লগারিদম (log or log10) ফাংশন ব্যবহার করা, যা অধিকাংশ সায়েন্টিফিক ক্যালকুলেটরেই থাকে। এ জন্য লগারিদমের ভিত্তি পরিবর্তনের সূত্রটি হল- [২২][২৫]


অথবা আসন্ন মান গ্রহণ করে-

পূর্ণ সংখ্যায় মান গ্রহণ[সম্পাদনা]

কোন পূর্ণ সংখ্যা থেকে গঠিত ফাংশন বাইনারি লগারিদমে পরিণত হতে পারে, আবার বাইনারি লগারিদম করে প্রাপ্ত মানকে বাড়িয়ে বা কমিয়ে পূর্ণ সংখ্যায় পরিণত করা যায়। বাইনারি লগারিদমের এ দুইটি পূর্ণ সংখ্যক রূপ নিম্নোক্ত সূত্র দ্বারা সম্পর্কিতঃ

[২৬]

ধরে নিয়ে এই সূত্রের আরও বিস্তার ঘটানো যায়। এ ক্ষেত্রে ফাংশনটি x এর ৩২ বিট আনসাইনড বাইনারি রূপ, nlz(x)এর মুখ্য শূন্য সংখ্যা-র সাথে সম্পর্কিত হবে ,

[২৬]

পূর্ণ সংখ্যক এই বাইনারি লগারিদমকে ইনপুটে সবচেয়ে তাৎপর্যপূর্ণ ১ বিটের শূন্য ভিত্তিক সূচক হিসেবে ব্যাখ্যা করা যেতে পারে। অনেক হার্ডওয়্যার প্ল্যাটফর্ম মুখ্য শূন্য সংখ্যা অনুসন্ধান বা অনুরূপ অপারেশনের জন্য সাপোর্ট দিয়ে থাকে, যা বাইনারি লগারিদমের মান দ্রুত খুঁজে বের করতে ব্যবহৃত হতে পারে।

পুনরাবৃত্তিমূলক আসন্ন মান গ্রহণ[সম্পাদনা]

একটি সাধারণ ধনাত্মক বাস্তব সংখ্যার জন্য, বাইনারি লগারিদমের মান দুই ভাগে হিসাব করা যায়। [২৭]প্রথমে, পূর্ণ সংখ্যা অংশ হিসেব করা হয় (যাকে লগারিদমের বৈশিষ্ট্য বলা হয়)। যে কোন x > 0 এর জন্য, এমন একটি অনন্য পূর্ণ সংখ্যা n থাকবে যেন 2nx < 2n+1 বা 1 ≤ 2nx < 2 হয় । এখানে লগারিদমের পূর্ণ সংখ্যা অংশটি সাধারণভাবে n আর ভগ্নাংশ অংশটি log2(2nx).[২৭] । অন্য কথায়,

সাধারণ ভাসমান বিন্দু সংখ্যাগুলোর জন্য, পূর্ণ সংখ্যা অংশটি ভাসমান বিন্দুর সূচক দিয়ে প্রকাশ করা হয় [২৮] আর মুখ্য শূন্যগুলো গণনা করে পূর্ণ সংখ্যার মানটি হিসাব করা হয়। [২৯]

ফলাফলের ভগ্নাংশ অংশটি হবে log2y আর পুনরাবৃত্তি পদ্ধতিতে, সাধারণ গুণ-ভাগের মাধ্যমে এর মান হিসেব করা হয়। ভগ্নাংশ অংশটি হিসাবের অ্যালগরিদম নিম্নোক্তভাবে বর্ণিত হতে পারে-

১] একটি অর্ধ-উন্মুক্ত ব্যবধি [1,2) তে একটি বাস্তব সংখ্যা y নিয়ে শুরু করি। যদি y = 1 হয়, তাহলে অ্যালগরিদম এর কাজ শেষ, ভগ্নাংশ অংশের মান শূন্য হবে।

২] অন্যথায়, y এর মানকে বর্গ করতে থাকি যতক্ষণ না ফলাফল z ব্যবধি [2,4)এ পৌঁছায়। ধরি , m হল যতবার বর্গ করতে হবে তার সংখ্যা। অর্থাৎ, z = y2mযেখানে m এর মান এমন হতে হবে যেন zএর মান [2,4) ব্যবধিতে থাকে।

৩] উভয় পক্ষে লগারিদম নিয়ে ও কিছু বীজগাণিতিক হিসাব করে পাইঃ

৪] আবারো z/2 একটি বাস্তব সংখ্যা যা [1,2) ব্যবধিতে থাকবে। এবার প্রথম ধাপে ফিরে যাই এবং একই পদ্ধতিতে z/2 এর বাইনারি লগারিদমের মান হিসাব করি।

ফলাফলটি নিম্নোলিখিত পুনরাবৃত্তিমূলক সূত্র দিয়ে প্রকাশ করা যায় - যেখানে হবে এলগরিদমের i তম পুনরাবৃত্তির জন্য প্রয়োজনীয় সংখ্যক বর্গ করার সংখ্যা

বিশেষ ক্ষেত্রে, যখন ১ম ধাপে প্রাপ্ত ভগ্নাংশ অংশের মান শূন্য হয়, তখন কোন একটি বিন্দুতে সমাপ্ত হয় এমন একটি সসীম ক্রম উৎপন্ন হবে। অন্যথায়, এটি একটি অসীম ধারা হবে যা অনুপাত পরীক্ষা অনুযায়ী একই বিন্দুতে মিলিত হবে, এর কারণ ধারাটির প্রতিটি পদই এর পূর্ববর্তী পদের তুলনায় ক্ষুদ্র ( যেহেতু প্রতিটি mi > 0) । ব্যবহারিক ক্ষেত্রে, আসন্ন মানে পৌঁছানোর জন্য এই অসীম ধারাটিকে ছেঁটে ফেলতে হবে অর্থাৎ একটি নির্দিষ্ট পদ পর্যন্ত মান নিতে হবে। যদি iতম পদ পর্যন্ত ধারাটির মান নেয়া হয়, তাহলে প্রাপ্ত ফলাফলে ভুলের পরিমাণ 2−(m1 + m2+ ... + mi) এর চেয়ে কম হবে। [২৭]

সফটওয়্যার লাইব্রেরির সমর্থন[সম্পাদনা]

log2 ফাংশনটি স্ট্যান্ডার্ড সি প্রোগ্রামের গাণিতিক ফাংশনের অন্তর্ভুক্ত। এই ফাংশনের ডিফল্ট সংস্করণটি দ্বিগুণ যথাযথ আর্গুমেন্টের মান গ্রহণ করে কিন্তু এর ভিন্ন সংস্করণ একক যথাযথ আর্গুমেন্ট বা "লং ডাবল" আর্গুমেন্টের মানও গ্রহণ করতে পারে।[৩০] ম্যাটল্যাব সফটওয়্যারের বেলায়, log2 ফাংশনের আর্গুমেন্ট ঋণাত্মক সংখ্যাও হতে পারে এবং সেক্ষেত্রে ফলাফল জটিল সংখ্যা হবে।[৩১]

তথ্যসূত্র[সম্পাদনা]

  1. Groza, Vivian Shaw; Shelley, Susanne M. (১৯৭২), Precalculus mathematics, New York: Holt, Rinehart and Winston, পৃষ্ঠা 182, আইএসবিএন 978-0-03-077670-0 .
  2. Stifel, Michael (১৫৪৪), Arithmetica integra (Latin ভাষায়), পৃষ্ঠা 31 . A copy of the same table with two more entries appears on p. 237, and another copy extended to negative powers appears on p. 249b.
  3. Joseph, G. G. (২০১১), The Crest of the Peacock: Non-European Roots of Mathematics (3rd সংস্করণ), Princeton University Press, পৃষ্ঠা 352 .
  4. See, e.g., Shparlinski, Igor (২০১৩), Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, 22, Birkhäuser, পৃষ্ঠা 35, আইএসবিএন 978-3-0348-8037-4 .
  5. For instance, Microsoft Excel provides the IMLOG2 function for complex binary logarithms: see Bourg, David M. (২০০৬), Excel Scientific and Engineering Cookbook, O'Reilly Media, পৃষ্ঠা 232, আইএসবিএন 978-0-596-55317-3 .
  6. Kolman, Bernard; Shapiro, Arnold (১৯৮২), "11.4 Properties of Logarithms", Algebra for College Students, Academic Press, পৃষ্ঠা 334–335, আইএসবিএন 978-1-4832-7121-7 .
  7. For instance, this is the notation used in the Encyclopedia of Mathematics and The Princeton Companion to Mathematics.
  8. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (২০০১) [1990], Introduction to Algorithms (2nd সংস্করণ), MIT Press and McGraw-Hill, পৃষ্ঠা 34, 53–54, আইএসবিএন 0-262-03293-7 
  9. Sedgewick, Robert; Wayne, Kevin Daniel (২০১১), Algorithms, Addison-Wesley Professional, পৃষ্ঠা 185, আইএসবিএন 978-0-321-57351-3 .
  10. The Chicago Manual of Style (25th সংস্করণ), University of Chicago Press, ২০০৩, পৃষ্ঠা 530 .
  11. Van der Lubbe, Jan C. A. (১৯৯৭), Information Theory, Cambridge University Press, পৃষ্ঠা 3, আইএসবিএন 978-0-521-46760-5 .
  12. Roberts, Fred; Tesman, Barry (২০০৯), Applied Combinatorics (2nd সংস্করণ), CRC Press, পৃষ্ঠা 206, আইএসবিএন 978-1-4200-9983-6 .
  13. Sipser, Michael (২০১২), "Example 7.4", Introduction to the Theory of Computation (3rd সংস্করণ), Cengage Learning, পৃষ্ঠা 277–278, আইএসবিএন 9781133187790 .
  14. Cormen et al., p. 844; Goodrich & Tamassia, p. 279.
  15. Cormen et al., section 28.2.
  16. Causton, Helen; Quackenbush, John; Brazma, Alvis (২০০৯), Microarray Gene Expression Data Analysis: A Beginner's Guide, John Wiley & Sons, পৃষ্ঠা 49–50, আইএসবিএন 978-1-4443-1156-3 .
  17. Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (২০১২), Computational and Statistical Methods for Protein Quantification by Mass Spectrometry, John Wiley & Sons, পৃষ্ঠা 105, আইএসবিএন 978-1-118-49378-6 .
  18. Campbell, Murray; Greated, Clive (১৯৯৪), The Musician's Guide to Acoustics, Oxford University Press, পৃষ্ঠা 78, আইএসবিএন 978-0-19-159167-9 .
  19. Randel, Don Michael, সম্পাদক (২০০৩), The Harvard Dictionary of Music (4th সংস্করণ), The Belknap Press of Harvard University Press, পৃষ্ঠা 416, আইএসবিএন 978-0-674-01163-2 .
  20. France, Robert (২০০৮), Introduction to Physical Education and Sport Science, Cengage Learning, পৃষ্ঠা 282, আইএসবিএন 978-1-4180-5529-5 .
  21. Allen, Elizabeth; Triantaphillidou, Sophie (২০১১), The Manual of Photography, Taylor & Francis, পৃষ্ঠা 228, আইএসবিএন 978-0-240-52037-7 .
  22. Davis, Phil (১৯৯৮), Beyond the Zone System, CRC Press, পৃষ্ঠা 17, আইএসবিএন 978-1-136-09294-7 .
  23. Allen & Triantaphillidou (2011), p. 235.
  24. Zwerman, Susan; Okun, Jeffrey A. (২০১২), Visual Effects Society Handbook: Workflow and Techniques, CRC Press, পৃষ্ঠা 205, আইএসবিএন 978-1-136-13614-6 .
  25. Bauer, Craig P. (২০১৩), Secret History: The Story of Cryptology, CRC Press, পৃষ্ঠা 332, আইএসবিএন 978-1-4665-6186-1 .
  26. Warren Jr., Henry S. (২০০২), Hacker's Delight (1st সংস্করণ), Addison Wesley, পৃষ্ঠা 215, আইএসবিএন 978-0-201-91465-8 
  27. Majithia, J. C.; Levan, D. (১৯৭৩), "A note on base-2 logarithm computations", Proceedings of the IEEE, 61 (10): 1519–1520, doi:10.1109/PROC.1973.9318 .
  28. Stephenson, Ian (২০০৫), "9.6 Fast Power, Log2, and Exp2 Functions", Production Rendering: Design and Implementation, Springer-Verlag, পৃষ্ঠা 270–273, আইএসবিএন 978-1-84628-085-6 .
  29. Warren Jr., Henry S. (২০১৩) [2002], "11-4: Integer Logarithm", Hacker's Delight (2nd সংস্করণ), Addison WesleyPearson Education, Inc., পৃষ্ঠা 291, আইএসবিএন 978-0-321-84268-8, 0-321-84268-5 .
  30. "7.12.6.10 The log2 functions", ISO/IEC 9899:1999 specification (PDF), পৃষ্ঠা 226 .
  31. Redfern, Darren; Campbell, Colin (১৯৯৮), The Matlab® 5 Handbook, Springer-Verlag, পৃষ্ঠা 141, আইএসবিএন 978-1-4612-2170-8 .