ลอการิทึมไบนารี

กราฟของบันทึก2 xเป็นฟังก์ชันของจำนวนจริงบวกx

ในทางคณิตศาสตร์ลอการิทึมไบนารี ( log 2 n ) คือกำลัง ที่ ต้องยกเลข2 ขึ้นเพื่อ ให้ได้ค่า  n นั่นคือ สำหรับจำนวนจริงxใด ๆ

ตัวอย่างเช่น ลอการิทึมไบนารีของ1คือ0ลอการิทึมไบนารีของ2คือ1ลอการิทึมไบนารีของ4คือ  2และลอการิทึมไบนารีของ 32คือ  5

ลอการิทึมไบนารีคือลอการิทึมของฐาน2และเป็นฟังก์ชันผกผันของกำลังของฟังก์ชัน ทั้งสอง เช่นเดียวกับlog 2สัญกรณ์อื่นสำหรับลอการิทึมไบนารีคือlb (สัญกรณ์ที่ต้องการโดยISO 31-11และISO 80000-2 )

ในอดีต การใช้ลอการิทึมไบนารีครั้งแรกเกิดขึ้นในทฤษฎีดนตรีโดยเลออนฮาร์ด ออยเลอร์ : ลอการิทึมไบนารีของอัตราส่วนความถี่ของสองโทนเสียงดนตรี ให้จำนวนอ็อกเทฟที่โทนต่างกัน ลอการิทึมไบนารีสามารถใช้เพื่อคำนวณความ ยาวของการแสดงตัวเลขในระบบเลขฐานสองหรือจำนวนบิตที่จำเป็นในการเข้ารหัสข้อความในทฤษฎีสารสนเทศ ในวิทยาการคอมพิวเตอร์พวกเขานับจำนวนขั้นตอนที่จำเป็นสำหรับการค้นหาแบบไบนารีและอัลกอริธึมที่เกี่ยวข้อง พื้นที่อื่นๆ ที่ใช้ลอการิทึมไบนารีบ่อยครั้ง ได้แก่เชิงผสมชีวสารสนเทศศาสตร์การออกแบบการแข่งขัน กีฬา และการถ่ายภาพ

ลอการิทึมไบนารีรวมอยู่ในฟังก์ชันทางคณิตศาสตร์มาตรฐาน Cและชุดซอฟต์แวร์ทางคณิตศาสตร์อื่นๆ

ประวัติศาสตร์

เลออนฮาร์ด ออยเลอร์เป็นคนแรกที่ใช้ลอการิทึมไบนารีกับทฤษฎีดนตรีในปี ค.ศ. 1739

พลังของทั้งสองเป็นที่รู้จักกันมาตั้งแต่สมัยโบราณ ตัวอย่างเช่นปรากฏในEuclid's Elements , Props IX.32 (เรื่องการแยกตัวประกอบของกำลังสอง) และ IX.36 (ครึ่งหนึ่งของทฤษฎีบทยุคลิด–ออยเลอร์บนโครงสร้างของจำนวนสมบูรณ์คู่ ) และลอการิทึมไบนารีของกำลังสองเป็นเพียงตำแหน่งในลำดับกำลังสองตามลำดับ บนพื้นฐานนี้Michael Stifelได้รับเครดิตจากการตีพิมพ์ตารางลอการิทึมไบนารีที่รู้จักเป็นครั้งแรกในปี 1544 หนังสือของเขาArithmetica Integraมีตารางหลายตารางที่แสดงจำนวนเต็มด้วยกำลังสองที่สอดคล้องกัน การกลับแถวของตารางเหล่านี้ทำให้สามารถตีความได้ว่าเป็นตารางลอการิทึมไบนารี [1] [2]

ก่อนหน้านี้กว่า Stifel นักคณิตศาสตร์ชาวเชน ในศตวรรษที่ 8 Virasenaได้รับการยกย่องว่าเป็นปูชนียบุคคลของลอการิทึมไบนารี แนวคิดเรื่อง อาธาเชดาของวิราเสนาถูกกำหนดให้เป็นจำนวนครั้งที่ตัวเลขที่กำหนดสามารถหารเท่าๆ กันด้วยสองได้ คำจำกัดความนี้ทำให้เกิดฟังก์ชันที่เกิดขึ้นพร้อมกันกับลอการิทึมไบนารี่ที่กำลังสอง[3]แต่จะแตกต่างกันสำหรับจำนวนเต็มอื่นๆ โดยให้ลำดับ 2-เอดิกแทนที่จะเป็นลอการิทึม [4]

รูปแบบสมัยใหม่ของลอการิทึมไบนารีที่ใช้กับจำนวนใดๆ (ไม่ใช่แค่กำลังสอง) ได้รับการพิจารณาอย่างชัดเจนโดยเลออนฮาร์ด ออยเลอร์ในปี 1739 ออยเลอร์ได้ก่อตั้งการประยุกต์ใช้ลอการิทึมไบนารีกับทฤษฎีดนตรี นานก่อนที่การประยุกต์ใช้ในทฤษฎีสารสนเทศและวิทยาการคอมพิวเตอร์จะกลายเป็น เป็นที่รู้จัก. ในส่วนหนึ่งของงานของเขาในสาขานี้ ออยเลอร์ได้ตีพิมพ์ตารางลอการิทึมไบนารีของจำนวนเต็มตั้งแต่ 1 ถึง 8 จนถึงทศนิยมเจ็ดหลักที่มีความแม่นยำ [5] [6]

ความหมายและคุณสมบัติ

ฟังก์ชันลอการิทึมไบนารีอาจถูกกำหนดให้เป็นฟังก์ชันผกผันยกกำลังของฟังก์ชันสองฟังก์ชัน ซึ่งเป็นฟังก์ชันที่เพิ่มขึ้นอย่างเข้มงวดเหนือจำนวนจริง บวก ดังนั้นจึงมีการผกผันเฉพาะ [7] หรืออีกทางหนึ่ง อาจนิยามเป็นln n /ln 2โดยที่lnคือลอการิทึมธรรมชาติซึ่งกำหนดด้วยวิธีมาตรฐานใดๆ ก็ตาม การใช้ลอการิทึมเชิงซ้อนในคำจำกัดความนี้จะทำให้ลอการิทึมไบนารีขยายเป็นจำนวนเชิงซ้อนได้ [8]

เช่นเดียวกับลอการิทึมอื่นๆ ลอการิทึมไบนารีเป็นไปตามสมการต่อไปนี้ ซึ่งสามารถใช้เพื่อลดความซับซ้อนของสูตรที่รวมลอการิทึมไบนารีกับการคูณหรือการยกกำลัง: [9]

หากต้องการข้อมูลเพิ่มเติม โปรด ดูรายการข้อมูลประจำตัวลอการิทึม

สัญกรณ์

ในทางคณิตศาสตร์ ลอการิทึมฐานสองของตัวเลขnมักเขียนเป็นlog 2 n [10]อย่างไรก็ตาม มีการใช้หรือเสนอสัญลักษณ์อื่นๆ หลายประการสำหรับฟังก์ชันนี้ โดยเฉพาะในด้านการใช้งาน

ผู้เขียนบางคนเขียนลอการิทึมไบนารีเป็นlg n , [11] [12]สัญกรณ์ที่ระบุไว้ในThe Chicago Manual of Style [13] โดนัลด์ คนุธให้เครดิตสัญกรณ์นี้เป็นคำแนะนำของเอ็ดเวิร์ด ไรน์โกลด์[14]แต่การใช้ทั้งในทฤษฎีสารสนเทศและวิทยาการคอมพิวเตอร์มีขึ้นก่อนที่เรนโกลด์จะใช้งานอยู่ [15] [16] ลอการิทึมไบนารียังถูกเขียนเป็นlog nด้วยคำสั่งก่อนหน้าว่าฐานเริ่มต้นสำหรับลอการิทึม  คือ2 [17] [18] [19]สัญกรณ์อีกรูปแบบหนึ่งที่มักใช้สำหรับฟังก์ชันเดียวกัน (โดยเฉพาะในวรรณกรรมทางวิทยาศาสตร์ของเยอรมัน) คือld n , [20] [21] [22]จากภาษาละติน logarithmus dualis [20]หรือlogarithmus dyadis . [20] มาตรฐาน DIN 1302  [de] , ISO 31-11และISO 80000-2 แนะนำ ให้ใช้สัญลักษณ์อื่นlb n ตามมาตรฐานเหล่านี้ไม่ควรใช้lg n สำหรับลอการิทึมไบนารี เนื่องจากมันถูกสงวนไว้สำหรับ บันทึกลอการิทึมทั่วไป 10 nแทน [23] [24] [25]

การใช้งาน

ทฤษฎีสารสนเทศ

จำนวนหลัก ( บิต ) ในการเป็นตัวแทนไบนารีของจำนวนเต็มบวกnเป็นส่วนสำคัญของ1 + log 2 nเช่น[12]

ในทฤษฎีสารสนเทศ คำจำกัดความของปริมาณข้อมูลตนเองและเอนโทรปีของข้อมูลมักแสดงด้วยลอการิทึมไบนารี ซึ่งสอดคล้องกับการทำให้บิตเป็นหน่วยพื้นฐานของข้อมูล ด้วยหน่วยเหล่านี้ทฤษฎีบทแชนนอน–ฮาร์ตลีย์จะแสดงความจุข้อมูลของช่องสัญญาณในรูปลอการิทึมไบนารีของอัตราส่วนสัญญาณต่อเสียงรบกวน บวกหนึ่ง อย่างไรก็ตามลอการิทึมธรรมชาติและnatยังใช้ในรูปแบบอื่นสำหรับคำจำกัดความเหล่านี้ [26]

เชิงผสม

กลุ่มทัวร์นาเมนต์แบบแพ้คัดออก ผู้เล่น 16 คนซึ่งมีโครงสร้างของแผนผังไบนารีที่สมบูรณ์ ความสูงของแผนภูมิ (จำนวนรอบของทัวร์นาเมนต์) คือลอการิทึมไบนารีของจำนวนผู้เล่น โดยปัดขึ้นเป็นจำนวนเต็ม

แม้ว่าลอการิทึมธรรมชาติจะมีความสำคัญมากกว่าลอการิทึมไบนารีในหลายพื้นที่ของคณิตศาสตร์บริสุทธิ์ เช่นทฤษฎีจำนวนและการวิเคราะห์ทางคณิตศาสตร์[27]ลอการิทึมไบนารีมีการนำไปใช้หลายอย่างในเชิงคณิตศาสตร์ :

  • ต้นไม้ไบนารีทุก ต้น ที่มี ใบ nมีความสูงอย่างน้อยlog 2 nโดยมีความเท่าเทียมกันเมื่อnเป็นกำลังของสองและต้นไม้นั้นเป็นต้นไม้ไบนารีที่สมบูรณ์ [28]ที่เกี่ยวข้องกันจำนวน Strahlerของระบบแม่น้ำที่มี ลำธารสาขา nมีค่าสูงสุดlog 2 n + 1 [29]
  • ทุกตระกูลของเซตที่มีn เซ็ตที่แตกต่างกันจะมี องค์ประกอบอย่างน้อย2 nองค์ประกอบในการรวมกัน โดยจะมีความเท่าเทียมกันเมื่อตระกูลนั้นเป็น เซ็ กำลัง [30]
  • ลูกบาศก์บางส่วนทุกอันที่มี จุดยอด nมีมิติสามมิติอย่างน้อยlog 2 nและมีขนาดมากที่สุด 1/2 nบันทึก2 n edge ด้วยความเท่าเทียมกันเมื่อลูกบาศก์บางส่วนเป็นกราฟไฮเปอร์คิวบ์ [31]
  • ตามทฤษฎีบทของแรมซีย์ทุกกราฟที่ไม่มีทิศทางของ n -vertexจะมีกลุ่มหรือ ชุด ลอการิทึมขนาดอิสระ ใน n ขนาดที่แน่นอนที่สามารถรับประกันได้ไม่เป็นที่รู้จัก แต่ขอบเขตที่ดีที่สุดที่ทราบเกี่ยวกับขนาดของมันนั้นเกี่ยวข้องกับลอการิทึมไบนารี โดยเฉพาะอย่างยิ่ง กราฟทั้งหมดจะมีกลุ่มหรือชุดขนาดที่เป็นอิสระเป็นอย่างน้อย1/2log 2 n (1 − o (1))และกราฟเกือบทั้งหมดไม่มีกลุ่มหรือชุดอิสระที่มีขนาดใหญ่กว่า2 log 2 n (1 + o (1 ) ) [32]
  • จากการวิเคราะห์ทางคณิตศาสตร์ของแบบจำลองการสุ่มไพ่ของกิลเบิร์ต–แชนนอน–รีดส์เราสามารถแสดงให้เห็นได้ว่าจำนวนครั้งที่เราต้องสับไพ่สำรับไพ่n ใบ โดยใช้การสับ ไพ่แบบริฟเฟิลเพื่อให้ได้การกระจายตัวของการเรียงสับเปลี่ยนที่ใกล้เคียงกับ สุ่มสม่ำเสมอก็ประมาณ3/2บันทึก2 _ การคำนวณนี้เป็นพื้นฐานสำหรับคำแนะนำว่าควรสับไพ่สำรับ 52 ใบเจ็ดครั้ง [33]

ความซับซ้อนในการคำนวณ

การค้นหาแบบไบนารี่ในอาร์เรย์ที่เรียงลำดับ ซึ่งเป็นอัลกอริทึมที่มีความซับซ้อนด้านเวลาเกี่ยวข้องกับลอการิทึมไบนารี

ลอการิทึมไบนารียังปรากฏบ่อยครั้งในการวิเคราะห์อัลกอริทึม[19] ไม่เพียงเพราะมีการใช้เลขคณิตเลขฐานสองบ่อยครั้งในอัลกอริทึมเท่านั้น แต่ยังเป็นเพราะ ลอการิทึมไบนารีเกิดขึ้นในการวิเคราะห์อัลกอริทึมที่มีพื้นฐานอยู่บนการแยกย่อยแบบสองทางด้วย [14] ถ้าปัญหาเริ่มแรกไม่มีทางเลือกสำหรับวิธีแก้ปัญหา และการวนซ้ำของอัลกอริทึมแต่ละครั้งจะลดจำนวนตัวเลือกลงด้วยปัจจัยสอง ดังนั้นจำนวนการวนซ้ำที่จำเป็นในการเลือกทางเลือกเดียวก็จะเป็นส่วนสำคัญของบันทึก2 อีกครั้ง . แนวคิดนี้ใช้ในการวิเคราะห์อัลกอริธึมและโครงสร้างข้อมูลต่างๆ ตัวอย่างเช่น ในการค้นหาแบบไบนารีขนาดของปัญหาที่จะแก้ไขจะลดลงครึ่งหนึ่งในแต่ละการวนซ้ำ และดังนั้นจึง จำเป็นต้อง มีการวนซ้ำประมาณ2 nครั้งเพื่อให้ได้วิธีแก้ปัญหาสำหรับปัญหาขนาดn [34]ในทำนองเดียวกันแผนผังการค้นหาแบบไบนารี ที่มีความสมดุลอย่างสมบูรณ์แบบ ซึ่งมี องค์ประกอบ nรายการจะมีบันทึก ความสูง 2 ( n + 1) − 1 [35]

เวลาทำงานของอัลกอริทึมมักจะแสดงในรูปแบบ O ใหญ่ซึ่งใช้เพื่อลดความซับซ้อนของนิพจน์โดยละเว้นปัจจัยคงที่และเงื่อนไขที่มีลำดับต่ำกว่า เนื่องจากลอการิทึมในฐานที่ต่างกันแตกต่างกันเพียงปัจจัยคงที่เท่านั้น อัลกอริธึมที่ทำงานใน เวลา O (บันทึก2 n )จึงสามารถกล่าวได้ว่าทำงานในเวลาO (บันทึก13 n ) ฐานของลอการิทึมในนิพจน์ เช่นO (log n )หรือO ( n log n )จึงไม่สำคัญและสามารถละเว้นได้ [11] [36]อย่างไรก็ตาม สำหรับลอการิทึมที่ปรากฏในเลขชี้กำลังของขอบเขตเวลา จะละเว้นฐานของลอการิทึมไม่ได้ ตัวอย่างเช่นO (2 log 2 n )ไม่เหมือนกับO ( 2 ln n )เพราะค่าแรกเท่ากับO ( n )และค่าหลังเท่ากับO ( n 0.6931... )

อัลกอริทึมที่มีเวลาทำงานO ( n  log  n )บางครั้งเรียกว่าเชิงเส้นตรง [37]ตัวอย่างของอัลกอริธึมที่มีเวลาทำงานO (log n )หรือO ( n log n )ได้แก่:

ลอการิทึมไบนารียังเกิดขึ้นในเลขชี้กำลังของขอบเขตเวลาสำหรับอัลกอริธึมการหารและการพิชิตเช่น อัลกอริธึมคารัตสึบะสำหรับการคูณ จำนวน nบิตในเวลาO ( n log 2  3 ) , [42] และอัลกอริธึม Strassenสำหรับการคูณn × n เมทริก ซ์ในเวลา O ( n log 2  7 ) [43]การเกิดขึ้นของลอการิทึมไบนารีในช่วงเวลาทำงานเหล่านี้สามารถอธิบายได้โดยการอ้างอิงถึงทฤษฎีบท หลักสำหรับการเกิดซ้ำแบบแบ่งและพิชิต

ชีวสารสนเทศศาสตร์

ไมโครอาร์เรย์สำหรับยีนประมาณ 8,700 ยีน อัตราการแสดงออกของยีนเหล่านี้ถูกเปรียบเทียบโดยใช้ลอการิทึมไบนารี

ในชีวสารสนเทศศาสตร์ไมโครอาร์เรย์ใช้ในการวัดว่ายีนที่แตกต่างกันอย่างมากแสดงออกในตัวอย่างวัสดุชีวภาพอย่างไร อัตราการแสดงออกของยีนที่แตกต่างกันมักจะถูกเปรียบเทียบโดยใช้ลอการิทึมไบนารีของอัตราส่วนของอัตราการแสดงออก: อัตราส่วนบันทึกของอัตราการแสดงออกทั้งสองถูกกำหนดให้เป็นลอการิทึมไบนารีของอัตราส่วนของสองอัตรา ลอการิทึมไบนารีช่วยให้เปรียบเทียบอัตรานิพจน์ได้อย่างสะดวก: อัตรานิพจน์สองเท่าสามารถอธิบายได้ด้วยอัตราส่วนบันทึกที่1อัตราการแสดงออกที่ลดลงครึ่งหนึ่งสามารถอธิบายได้ด้วยอัตราส่วนบันทึกที่−1และอัตราการแสดงออกที่ไม่เปลี่ยนแปลงสามารถอธิบายได้ด้วย อัตราส่วนบันทึกเป็นศูนย์ เป็นต้น [44]

จุดข้อมูลที่ได้รับในลักษณะนี้มักจะถูกมองเห็นเป็นแผนภาพกระจายโดยที่แกนพิกัดหนึ่งหรือทั้งสองแกนเป็นลอการิทึมไบนารีของอัตราส่วนความเข้ม หรือในการแสดงภาพ เช่น แผนภาพMAและแผนภาพ RAที่หมุนและปรับขนาดอัตราส่วนการกระจายของล็อกเหล่านี้ [45]

ทฤษฎีดนตรี

ในทฤษฎีดนตรีช่วงเวลาหรือความแตกต่างในการรับรู้ระหว่างสองโทนเสียงถูกกำหนดโดยอัตราส่วนของความถี่ ช่วงที่มาจาก อัตราส่วน จำนวนตรรกยะที่มีทั้งเศษและส่วนน้อยจะถูกมองว่าไพเราะเป็นพิเศษ ช่วงเวลาที่ง่ายที่สุดและสำคัญที่สุดคืออ็อกเทฟซึ่งมีอัตราส่วนความถี่2:1 จำนวนอ็อกเทฟที่เสียงสองโทนต่างกันคือลอการิทึมไบนารีของอัตราส่วนความถี่ [46]

ในการศึกษาระบบการปรับเสียงและแง่มุมอื่นๆ ของทฤษฎีดนตรีที่ต้องการความแตกต่างระหว่างโทนเสียงที่ละเอียดยิ่งขึ้น การวัดขนาดของช่วงความถี่ที่ละเอียดกว่าอ็อกเทฟและเป็นการบวก (ตามลอการิทึม) แทนที่จะเป็นการคูณ (ตามความถี่) จะเป็นประโยชน์ อัตราส่วนเป็น) นั่นคือ ถ้าโทนเสียงx , yและzสร้างลำดับโทนเสียงที่เพิ่มขึ้น การวัดช่วงจากxถึงyบวกกับการวัดช่วงจากyถึงz ควรเท่ากับ การวัดช่วงจากxถึงz การวัดดังกล่าวกำหนดโดยเปอร์เซ็นต์ซึ่งแบ่งอ็อกเทฟออกเป็น1,200ช่วงเท่าๆ กัน ( 12 ครึ่งเสียง ครึ่งเสียง ละ 100เซ็นต์) ในทางคณิตศาสตร์ เมื่อกำหนดโทนเสียงที่มีความถี่f 1และf 2จำนวนเซนต์ในช่วงตั้งแต่f 1ถึงf 2คือ[46]

มิลลิ อค เทถูกกำหนดในลักษณะเดียวกัน แต่มีตัวคูณ1,000แทนที่จะเป็น1200 [47]

กำหนดการกีฬา

ในเกมการแข่งขันและกีฬาที่เกี่ยวข้องกับผู้เล่นสองคนหรือทีมในแต่ละเกมหรือการแข่งขัน ลอการิทึมไบนารีจะระบุจำนวนรอบที่จำเป็นในทัวร์นาเมนต์แบบแพ้คัดออกซึ่งจำเป็นในการตัดสินผู้ชนะ ตัวอย่างเช่น ทัวร์นาเมนต์ที่ มีผู้เล่น 4คนต้องใช้บันทึก2  4 = 2รอบเพื่อตัดสินผู้ชนะ ทัวร์นาเมนต์ที่มี32ทีมต้องใช้บันทึก2  32 = 5รอบ เป็นต้น ในกรณีนี้ สำหรับ ผู้เล่น nคน/ทีม โดยที่nไม่ใช่พาวเวอร์ จาก 2 บันทึก2 nถูกปัดเศษขึ้นเนื่องจากจำเป็นต้องมีรอบอย่างน้อยหนึ่งรอบซึ่งผู้แข่งขันที่เหลือไม่ทั้งหมดจะลงเล่น ตัวอย่างเช่นบันทึก2  6มีค่าประมาณ2.585ซึ่งปัดขึ้นเป็น3แสดงว่าทัวร์นาเมนต์ที่มี6ทีมต้องใช้3รอบ (ทั้งสองทีมออกจากรอบแรก หรือทีมหนึ่งออกจากรอบที่สอง) จำนวนรอบที่เท่ากันยังเป็นสิ่งจำเป็นในการตัดสินผู้ชนะที่ชัดเจนในการแข่งขันระบบสวิส [48]

การถ่ายภาพ

ในการถ่ายภาพค่าแสงจะถูกวัดในรูปของลอการิทึมไบนารีของปริมาณแสงที่ส่องถึงฟิล์มหรือเซ็นเซอร์ ตามกฎหมายของเวเบอร์-เฟชเนอร์ซึ่งอธิบายการตอบสนองลอการิทึมของระบบการมองเห็นของมนุษย์ต่อแสง การหยุดรับแสงเพียงครั้งเดียวคือหนึ่งหน่วยในระดับลอการิทึม ฐาน 2 [49] [50]แม่นยำยิ่งขึ้น ค่ารับแสงของภาพถ่ายถูกกำหนดเป็น

โดยที่Nคือค่า fที่วัดรูรับแสงของเลนส์ระหว่างการเปิดรับแสง และtคือจำนวนวินาทีของการเปิดรับแสง [51]

ลอการิทึมไบนารี (แสดงเป็นจุดหยุด) ยังใช้ในการวัดความหนาแน่นเพื่อแสดงช่วงไดนามิกของวัสดุที่ไวต่อแสงหรือเซ็นเซอร์ดิจิทัล [52]

การคำนวณ

เครื่องคิดเลขวิทยาศาสตร์HP-35 (1972) ปุ่มบันทึกและ ln อยู่ที่แถวบนสุด ไม่มี คีย์ บันทึก 2

การแปลงจากฐานอื่น

วิธีง่ายๆ ในการคำนวณlog 2 nบนเครื่องคิดเลขที่ไม่มี ฟังก์ชัน log 2คือการใช้ฟังก์ชันลอการิทึมธรรมชาติ ( ln ) หรือ ฟังก์ชัน ลอการิทึมทั่วไป ( logหรือlog 10 ) ซึ่งพบได้ในเครื่องคิดเลขวิทยาศาสตร์ ส่วน ใหญ่ หากต้องการเปลี่ยนฐานลอการิทึมจากeหรือ10เป็น2คุณสามารถใช้สูตร : [50] [53]

หรือประมาณ

การปัดเศษจำนวนเต็ม

ลอการิทึมไบนารีสามารถสร้างเป็นฟังก์ชันจากจำนวนเต็มและเป็นจำนวนเต็มได้โดยการปัดเศษขึ้นหรือลง ลอการิทึมไบนารีจำนวนเต็มสองรูปแบบนี้มีความสัมพันธ์กันโดยสูตรนี้:

[54]

คำจำกัดความสามารถขยายได้โดยการกำหนด ขยายด้วยวิธี นี้ ฟังก์ชันนี้สัมพันธ์กับจำนวนศูนย์นำหน้าของการแสดงไบนารี่ที่ไม่ได้ลงนามแบบ 32 บิตของx , nlz( x )

[54]

ลอการิทึมไบนารีจำนวนเต็มสามารถตีความได้ว่าเป็นดัชนีฐานศูนย์ของ 1 บิต ที่สำคัญที่สุดในอินพุต ในแง่นี้ มันเป็นส่วนเสริมของ การดำเนินการ ค้นหาชุดแรกซึ่งจะค้นหาดัชนีที่มีนัยสำคัญน้อยที่สุด1บิต แพลตฟอร์มฮาร์ดแวร์จำนวนมากรองรับการค้นหาจำนวนศูนย์นำหน้าหรือการดำเนินการที่เทียบเท่า ซึ่งสามารถใช้เพื่อค้นหาลอการิทึมไบนารีได้อย่างรวดเร็ว และflsฟังก์ชันflslในเคอร์เนล Linux [55]และใน ไลบรารีซอฟต์แวร์ libc บางเวอร์ชัน ยังคำนวณลอการิทึมไบนารีด้วย (ปัดเศษขึ้นเป็นจำนวนเต็มบวกหนึ่ง)

การประมาณซ้ำ

สำหรับ จำนวนจริงบวกทั่วไปลอการิทึมไบนารีอาจคำนวณได้เป็นสองส่วน [56] ขั้นแรก ให้คำนวณส่วนจำนวนเต็ม ( เรียกว่าคุณลักษณะของลอการิทึม) วิธีนี้จะช่วยลดปัญหาให้เหลือเพียงอาร์กิวเมนต์ของลอการิทึมในช่วงที่จำกัด นั่นคือช่วง[1, 2)ซึ่งทำให้ขั้นตอนที่สองของการคำนวณเศษส่วนง่ายขึ้น (แมนทิสซาของลอการิทึม) สำหรับx > 0 ใดๆ จะมีจำนวนเต็มเฉพาะnอยู่ที่2 nx < 2 n +1หรือเทียบเท่า1 ≤ 2 n x < 2 ตอน นี้ส่วนจำนวนเต็มของลอการิทึมเป็นเพียงnและส่วนที่เป็นเศษส่วนคือlog 2 ( 2 nx ) (56) กล่าวอีกนัยหนึ่ง:

สำหรับ จำนวน จุดลอยตัว ที่ทำให้เป็นมาตรฐาน ส่วนจำนวนเต็มจะได้รับจากเลขชี้กำลังจุดลอยตัว[57]และสำหรับจำนวนเต็มนั้นสามารถกำหนดได้โดยดำเนินการนับเลขศูนย์นำหน้า [58]

เศษส่วนของผลลัพธ์คือlog 2 yและสามารถคำนวณซ้ำได้ โดยใช้เพียงการคูณและการหารเบื้องต้นเท่านั้น [56] อัลกอริธึมสำหรับการคำนวณเศษส่วนสามารถอธิบายได้ด้วยรหัสเทียมดังนี้:

  1. เริ่มต้นด้วยจำนวนจริงyในช่วงครึ่งเปิด[1, 2 ) ถ้าy = 1แสดงว่าอัลกอริทึมเสร็จสิ้น และส่วนที่เป็นเศษส่วนจะเป็นศูนย์
  2. มิฉะนั้น ให้ยกกำลังyซ้ำๆ จนกระทั่งผลลัพธ์zอยู่ในช่วงเวลา[2, 4 ) ให้mเป็นจำนวนกำลังสองที่ต้องการ นั่นคือz = y 2 mโดยที่mเลือกไว้ โดยที่zอยู่ใน[2, 4 )
  3. หาลอการิทึมของทั้งสองข้างแล้วทำพีชคณิต:
  4. อีกครั้งหนึ่งz /2เป็นจำนวนจริงในช่วง[1, 2 ) กลับไปที่ขั้นตอนที่ 1 และคำนวณลอการิทึมไบนารีของz /2โดยใช้วิธีเดียวกัน

ผลลัพธ์นี้แสดงโดยสูตรแบบเรียกซ้ำต่อไปนี้ ซึ่งก็คือจำนวนกำลังสองที่ต้องการในการวนซ้ำอัลกอริทึมครั้งที่ i :

ในกรณีพิเศษที่พบว่าเศษส่วนในขั้นตอนที่ 1 เป็นศูนย์ นี่เป็น ลำดับ จำกัดที่สิ้นสุด ณ จุดใดจุดหนึ่ง มิฉะนั้น มันจะเป็นอนุกรมอนันต์ที่มาบรรจบกันตามการทดสอบอัตราส่วนเนื่องจากแต่ละเทอมจะน้อยกว่าเทอมก่อนหน้าอย่างเคร่งครัด (เนื่องจากทุกๆm i > 0 ) สำหรับการใช้งานจริง อนุกรมอนันต์นี้ต้องถูกตัดทอนเพื่อให้ได้ผลลัพธ์โดยประมาณ ถ้าอนุกรมถูกตัดทอนหลัง เทอมที่ iความคลาดเคลื่อนในผลลัพธ์จะน้อยกว่า2 −( m 1 + m 2 + ⋯ + m i ) [56]

การสนับสนุนไลบรารีซอฟต์แวร์

ฟังก์ชัน นี้log2รวมอยู่ในฟังก์ชันทางคณิตศาสตร์มาตรฐานของC เวอร์ชันเริ่มต้นของฟังก์ชันนี้ใช้ อาร์กิวเมนต์ที่มีความ แม่นยำสองเท่าแต่ตัวแปรของมันอนุญาตให้อาร์กิวเมนต์เป็นแบบความแม่นยำเดียวหรือเป็นสองเท่าแบบยาว ในสภาพแวดล้อมการคำนวณที่รองรับจำนวนเชิงซ้อนและการแปลงประเภทโดยนัย เช่นMATLABอาร์กิวเมนต์ของlog2ฟังก์ชันได้รับอนุญาตให้เป็นจำนวนลบโดยส่งคืนจำนวนเชิงซ้อน [60]

อ้างอิง

  1. โกรซา, วิเวียน ชอว์; Shelley, Susanne M. (1972), คณิตศาสตร์พรีแคลคูลัส, New York: Holt, Rinehart และ Winston, p. 182, ไอเอสบีเอ็น  978-0-03-077670-0.
  2. Stifel, Michael (1544), Arithmetica integra (ในภาษาละติน), หน้า 103 31. สำเนาของตารางเดียวกันที่มีอีกสองรายการปรากฏบนหน้า 237 และสำเนาอีกฉบับที่ขยายไปสู่กำลังลบปรากฏบนหน้า 249บ.
  3. โจเซฟ, GG (2011), The Crest of the Peacock: Non-European Roots of Mathematics (3rd ed.), Princeton University Press, p. 352.
  4. ดู เช่นShparlinski, Igor (2013), การประยุกต์การเข้ารหัสของทฤษฎีจำนวนวิเคราะห์: ขอบเขตล่างที่ซับซ้อนและการสุ่มเทียม, ความก้าวหน้าในวิทยาการคอมพิวเตอร์และลอจิกประยุกต์, ฉบับที่ 22, บีร์ฮอเซอร์, น. 35, ไอเอสบีเอ็น 978-3-0348-8037-4.
  5. ออยเลอร์, เลออนฮาร์ด (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus", Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (ในภาษาละติน), Saint Petersburg Academy, หน้า 102–112.
  6. Tegg, Thomas (1829), "Binary logarithms", สารานุกรมลอนดอน; หรือ พจนานุกรมวิทยาศาสตร์ ศิลปะ วรรณกรรม และกลศาสตร์เชิงปฏิบัติสากล: ประกอบด้วยมุมมองที่ได้รับความนิยมเกี่ยวกับสภาวะความรู้ปัจจุบัน เล่ม 4 หน้า 142–143.
  7. Batschelet, E. (2012), Introduction to Mathematics for Life Scientists, สปริงเกอร์, p. 128, ไอเอสบีเอ็น 978-3-642-96080-2.
  8. ตัวอย่างเช่นMicrosoft ExcelมีIMLOG2ฟังก์ชันสำหรับลอการิทึมไบนารีที่ซับซ้อน: ดูBourg, David M. (2006), Excel Scientific and Engineering Cookbook, O'Reilly Media, p. 232, ไอเอสบีเอ็น 978-0-596-55317-3.
  9. โคลมาน, เบอร์นาร์ด; Shapiro, Arnold (1982), "11.4 คุณสมบัติของลอการิทึม", พีชคณิตสำหรับนักศึกษาวิทยาลัย, สำนักพิมพ์วิชาการ, หน้า 334–335, ISBN 978-1-4832-7121-7.
  10. ตัวอย่างเช่น นี่คือสัญลักษณ์ที่ใช้ในสารานุกรมคณิตศาสตร์และThe Princeton Companion to Mathematics
  11. ↑ อับ คอร์เมน, โธมัส เอช. ; ไลเซอร์สัน, ชาร์ลส์ อี. ; ริเวสท์, โรนัลด์ แอล. ; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press และ McGraw-Hill, หน้า 34, 53–54, ISBN 0-262-03293-7
  12. ↑ อับ เซดจ์วิก, โรเบิร์ต ; Wayne, Kevin Daniel (2011), อัลกอริทึม, Addison-Wesley Professional, p. 185, ไอเอสบีเอ็น 978-0-321-57351-3.
  13. The Chicago Manual of Style (ฉบับพิมพ์ครั้งที่ 25), สำนักพิมพ์มหาวิทยาลัยชิคาโก, 2003, p. 530.
  14. ↑ ab Knuth, Donald E. (1997), อัลกอริทึมพื้นฐาน , ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ , ฉบับ. 1 (ฉบับพิมพ์ครั้งที่ 3), Addison-Wesley Professional, ISBN 978-0-321-63574-7,หน้า. 11. สัญลักษณ์เดียวกันนี้อยู่ในหนังสือเล่มเดียวกันฉบับพิมพ์ครั้งที่ 2 ปี 1973 (หน้า 23) แต่ไม่มีการให้เครดิตกับ Reingold
  15. Trucco, Ernesto (1956), "หมายเหตุเกี่ยวกับเนื้อหาข้อมูลของกราฟ", Bull คณิตศาสตร์. ชีวฟิสิกส์ , 18 (2): 129–135, ดอย :10.1007/BF02477836, MR  0077919.
  16. Mitchell, John N. (1962), "การคูณและการหารคอมพิวเตอร์โดยใช้ลอการิทึมไบนารี", ธุรกรรม IRE บนคอมพิวเตอร์อิเล็กทรอนิกส์ , EC-11 (4): 512–517, doi :10.1109/TEC.1962.5219391.
  17. ฟิเช, จอร์จส; Hebuterne, Gerard (2013), คณิตศาสตร์สำหรับวิศวกร, John Wiley & Sons, p. 152, ไอเอสบีเอ็น 978-1-118-62333-6ต่อไปนี้และเว้นแต่จะระบุไว้เป็นอย่างอื่น บันทึกสัญลักษณ์ x จะหมายถึงลอการิทึมของฐาน2ของx เสมอ.
  18. ปก, โธมัส เอ็ม. ; Thomas, Joy A. (2012), องค์ประกอบของทฤษฎีสารสนเทศ (ฉบับพิมพ์ครั้งที่ 2), John Wiley & Sons , p. 33 ไอเอสบีเอ็น 978-1-118-58577-1เรา จะนำลอการิทึมทั้งหมดไปที่ฐาน 2เว้นแต่จะระบุไว้เป็นอย่างอื่น.
  19. ↑ แอบ กู๊ดริช, ไมเคิล ที. ; Tamassia, Roberto (2002), การออกแบบอัลกอริทึม: รากฐาน, การวิเคราะห์ และตัวอย่างอินเทอร์เน็ต , John Wiley & Sons, p. 23 หนึ่งในแง่มุมที่น่าสนใจและบางครั้งก็น่าประหลาดใจในการวิเคราะห์โครงสร้างข้อมูลและอัลกอริธึมคือการมีอยู่ของลอการิทึมอยู่ทุกหนทุกแห่ง ... ตามธรรมเนียมในวรรณคดีด้านคอมพิวเตอร์ เราละเว้นการเขียนฐานbของลอการิทึมเมื่อb  = 2 .
  20. ↑ abc Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [ Introduction to digital informationprocessing ] (ในภาษาเยอรมัน), Munich: Carl Hanser Verlag , หน้า 20–21, ISBN 3-446-10569-7
  21. ทิเอตเซ, อุลริช; Schenk, Christoph (1999), Halbleiter-Schaltungstechnik (ในภาษาเยอรมัน) (พิมพ์ซ้ำแก้ไขครั้งที่ 1, ฉบับพิมพ์ครั้งที่ 11), Springer Verlag , p. 1370 ไอเอสบีเอ็น 3-540-64192-0
  22. Bauer, Friedrich L. (2009), ต้นกำเนิดและรากฐานของคอมพิวเตอร์: ในความร่วมมือกับ Heinz Nixdorf MuseumsForum, Springer Science & Business Media , p. 54, ไอเอสบีเอ็น 978-3-642-02991-2.
  23. สำหรับ DIN 1302 ดูที่Brockhaus Enzyklopädie ใน zwanzig Bänden [ Brockhaus Encyclopedia in Twenty Volumes ] (ในภาษาเยอรมัน), เล่ม. วีสบาเดิน 11/11: FA Brockhaus, 1970, p. 554, ไอเอสบีเอ็น 978-3-7653-0000-4.
  24. สำหรับ ISO 31-11 ดูที่ทอมป์สัน, แอมเบลอร์; Taylor, Barry M (มีนาคม 2551), คำแนะนำสำหรับการใช้ระบบหน่วยสากล (SI) — NIST Special Publication 811, 2008 Edition — Second Printing (PDF) , NIST , p. 33.
  25. สำหรับ ISO 80000-2 ดู "ปริมาณและหน่วย – ส่วนที่ 2: เครื่องหมายและสัญลักษณ์ทาง คณิตศาสตร์ที่จะใช้ในวิทยาศาสตร์ธรรมชาติและเทคโนโลยี" (PDF) มาตรฐานสากล ISO 80000-2 (ฉบับพิมพ์ครั้งที่ 1) 1 ธันวาคม 2552 ส่วนที่ 12 ฟังก์ชันเลขชี้กำลังและลอการิทึม หน้า 12 18.
  26. Van der Lubbe, Jan CA (1997), ทฤษฎีสารสนเทศ, สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, p. 3, ไอเอสบีเอ็น 978-0-521-46760-5.
  27. Stewart, Ian (2015), Taming the Infinite, Quercus, p. 120, ไอเอสบีเอ็น 9781623654733ในคณิตศาสตร์และวิทยาศาสตร์ขั้นสูง ลอการิทึมเดียวที่มีความสำคัญคือลอการิทึมธรรมชาติ.
  28. Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis, CRC Press, p. 28, ไอเอสบีเอ็น 978-1-4200-1170-8.
  29. เดฟรอย, แอล. ; Kruszewski, P. (1996), "บนหมายเลข Horton–Strahler สำหรับการสุ่มลอง", RAIRO Informatique Théorique et Applications , 30 (5): 443–456, doi : 10.1051/ita/1996300504431 , MR  1435732.
  30. ในทำนองเดียวกัน ตระกูลที่มี องค์ประกอบต่างกัน kมีเซตที่แตกต่างกันมากที่สุด2 kโดยมีความเท่าเทียมกันเมื่อเป็นเซตกำลัง
  31. Eppstein, David (2005), "The lattice dimensions of a graph", European Journal of Combinatorics , 26 (5): 585–592, arXiv : cs.DS/0402028 , doi :10.1016/j.ejc.2004.05.001 , นาย  2127682, S2CID  7482443.
  32. เกรแฮม, โรนัลด์ แอล. ; รอธไชลด์, บรูซ แอล . ; Spencer, Joel H. (1980), ทฤษฎีแรมซีย์ , Wiley-Interscience, p. 78.
  33. ไบเออร์, เดฟ ; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair", The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR  2959752, MR  1161056.
  34. เมห์ลฮอร์น, เคิร์ต ; Sanders, Peter (2008), "2.5 An example – binary search", Algorithms and Data Structures: The Basic Toolbox (PDF) , Springer, หน้า 34–36, ISBN 978-3-540-77977-3.
  35. โรเบิร์ตส์, เฟร็ด ; Tesman, Barry (2009), Applied Combinatorics (ฉบับพิมพ์ครั้งที่ 2), CRC Press, p. 206, ไอเอสบีเอ็น 978-1-4200-9983-6.
  36. Sipser, Michael (2012), "ตัวอย่าง 7.4", Introduction to the Theory of Computation (ฉบับพิมพ์ครั้งที่ 3), Cengage Learning, หน้า 277–278, ISBN 9781133187790.
  37. เซดจ์วิคและเวย์น (2011), p. 186.
  38. คอร์เมน และคณะ (2544) น. 156; Goodrich & Tamassia (2002), หน้า 238.
  39. คอร์เมน และคณะ (2544) น. 276; Goodrich & Tamassia (2002), หน้า 159.
  40. คอร์เมน และคณะ (2544) น. 879–880; Goodrich & Tamassia (2002), หน้า 464.
  41. เอ็ดมอนด์ส, เจฟฟ์ (2008), วิธีคิดเกี่ยวกับอัลกอริทึม, สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, พี. 302, ไอเอสบีเอ็น 978-1-139-47175-6.
  42. คอร์เมน และคณะ (2544) น. 844; Goodrich & Tamassia (2002), หน้า 279.
  43. คอร์เมน และคณะ (2544) มาตรา 28.2..
  44. คอสสตัน, เฮเลน; ควอเคนบุช, จอห์น; Brazma, Alvis (2009), การวิเคราะห์ข้อมูลการแสดงออกของยีน Microarray: คู่มือสำหรับผู้เริ่มต้น, John Wiley & Sons, หน้า 49–50, ISBN 978-1-4443-1156-3.
  45. ไอดามเมอร์, อิงวาร์; บาร์สเนส, ฮาราลด์; เอเด, เกอีร์ เอกิล; Martens, Lennart (2012), วิธีการคำนวณและสถิติสำหรับปริมาณโปรตีนโดย Mass Spectrometry, John Wiley & Sons, p. 105, ไอเอสบีเอ็น 978-1-118-49378-6.
  46. ↑ อับ แคมป์เบลล์, เมอร์เรย์; Greated, Clive (1994), คู่มือนักดนตรีด้านเสียง, สำนักพิมพ์มหาวิทยาลัยออกซฟอร์ด, พี. 78, ไอเอสบีเอ็น 978-0-19-159167-9.
  47. แรนเดล, ดอน ไมเคิล , เอ็ด. (2003), พจนานุกรมดนตรีฮาร์วาร์ด (ฉบับพิมพ์ครั้งที่ 4), The Belknap Press of Harvard University Press, p. 416 ไอเอสบีเอ็น 978-0-674-01163-2.
  48. ฝรั่งเศส, Robert (2008), Introduction to Physical Education and Sport Science, Cengage Learning, p. 282, ไอเอสบีเอ็น 978-1-4180-5529-5.
  49. อัลเลน, เอลิซาเบธ; Triantaphillidou, Sophie (2011), คู่มือการถ่ายภาพ, Taylor & Francis, p. 228, ไอเอสบีเอ็น 978-0-240-52037-7.
  50. ↑ ab Davis, Phil (1998), Beyond the Zone System, ซีอาร์ซี เพรส, พี. 17, ไอเอสบีเอ็น 978-1-136-09294-7.
  51. อัลเลน และ ไทรอันตาฟิลลิดู (2011), หน้า 1. 235.
  52. ซเวอร์มาน, ซูซาน; Okun, Jeffrey A. (2012), คู่มือ Visual Effects Society: ขั้นตอนการทำงานและเทคนิค, CRC Press, p. 205, ไอเอสบีเอ็น 978-1-136-13614-6.
  53. Bauer, Craig P. (2013), Secret History: The Story of Cryptology, CRC Press, p. 332, ไอเอสบีเอ็น 978-1-4665-6186-1.
  54. ↑ ab Warren Jr., Henry S. (2002), Hacker's Delight (ฉบับพิมพ์ครั้งที่ 1), Addison Wesley , p. 215, ไอเอสบีเอ็น 978-0-201-91465-8
  55. fls, Linux kernel API, kernel.orgดึงข้อมูลเมื่อ 2010-10-17
  56. ↑ abcd มาจิเธีย, เจซี; Levan, D. (1973), "หมายเหตุเกี่ยวกับการคำนวณลอการิทึมฐาน 2", Proceedings of the IEEE , 61 (10): 1519–1520, doi :10.1109/PROC.1973.9318.
  57. Stephenson, Ian (2005), "9.6 Fast Power, Log2, and Exp2 Functions", Production Rendering: Design and Implementation, Springer-Verlag, หน้า 270–273, ISBN 978-1-84628-085-6.
  58. Warren Jr., Henry S. (2013) [2002], "11-4: Integer Logarithm", Hacker's Delight (ฉบับพิมพ์ครั้งที่ 2), Addison WesleyPearson Education, Inc. , p. 291 ไอเอสบีเอ็น 978-0-321-84268-8, 0-321-84268-5.
  59. "7.12.6.10 ฟังก์ชัน log2", ข้อกำหนด ISO/IEC 9899:1999 (PDF) , หน้า 2 226.
  60. เรดเฟิร์น, ดาร์เรน; Campbell, Colin (1998), คู่มือ Matlab® 5, Springer-Verlag, p. 141, ไอเอสบีเอ็น 978-1-4612-2170-8.

ลิงค์ภายนอก

  • ไวส์สไตน์, เอริก ดับเบิลยู. , "ลอการิทึมไบนารี", MathWorld
  • Anderson, Sean Eron (12 ธันวาคม 2546), "Find the log base 2 of an N-bit integer in O(lg(N)) actions", Bit Twiddling Hacks , Stanford University , ดึงข้อมูลเมื่อ25-11-2558
  • ไฟน์แมนและเครื่องเชื่อมต่อ
Retrieved from "https://en.wikipedia.org/w/index.php?title=Binary_logarithm&oldid=1192455513"