การแนะนำอัลกอริทึมโมดูลัสพลังงานอย่างรวดเร็วถูกเสนอโดยข้อ จำกัด ของอัลกอริทึมที่ไร้เดียงสาที่ใช้โมดูลัสจากทศนิยมของจำนวนมาก ในวิธีที่ไร้เดียงสาเราคำนวณตัวเลขเช่น 5^1003%31 ซึ่งใช้ทรัพยากรการคำนวณของเราเป็นอย่างมาก สิ่งที่ลำบากที่สุดในกระบวนการคำนวณทั้งหมดคือกระบวนการ 5^1003 ของเรา
ข้อเสีย 1: ในกระบวนการคำนวณดัชนีในภายหลังตัวเลขที่คำนวณไม่ได้เพิ่มขึ้นทั้งหมดซึ่งใช้ทรัพยากรการคำนวณของเราจำนวนมาก (ส่วนใหญ่เวลาและพื้นที่)
ข้อเสีย 2: ตัวเลขในการคำนวณของเรามีขนาดใหญ่มากจนคอมพิวเตอร์ที่มีอยู่ของเราไม่สามารถบันทึกข้อมูลที่ยาวเช่นนี้ได้ดังนั้นเราต้องคิดถึงวิธีที่มีประสิทธิภาพมากขึ้นในการแก้ปัญหานี้
เมื่อเราคำนวณ AB%C วิธีที่สะดวกที่สุดคือเรียกใช้วิธี POW ในฟังก์ชันคณิตศาสตร์ อย่างไรก็ตามบางครั้งจำนวนของ A ถึงพลังของ B นั้นมีขนาดใหญ่เกินไปและแม้แต่ความแม่นยำสองเท่าก็จะล้น ในเวลานี้เพื่อให้ได้ผลลัพธ์ของ AB%C เราจะเลือกใช้อัลกอริทึมโมดูลัสพลังงานอย่างรวดเร็วเพื่อให้ได้ผลลัพธ์ที่เราต้องการอย่างง่ายดายและรวดเร็ว
เพื่อป้องกันไม่ให้ตัวเลขล้นและลดความซับซ้อนเราจำเป็นต้องใช้สูตรต่อไปนี้:
abmod c = (a mod c) bmod c
ความหมายของสูตรนี้คือ: ผลิตภัณฑ์ใช้เวลาส่วนที่เหลือเท่ากับผลิตภัณฑ์ที่เหลืออยู่ เป็นเรื่องง่ายที่จะเห็นว่าสูตรนี้เป็นสกรรมกริยาเพื่อให้เราสามารถทำให้เล็กลงและเล็กลงได้อย่างต่อเนื่องโดยการใช้ส่วนที่เหลืออย่างต่อเนื่องเพื่อป้องกันการล้น
ในทางทฤษฎีด้วยสูตรนี้เราสามารถเขียนโค้ดได้ โดยการโมดูโลอย่างต่อเนื่องเรามั่นใจว่าผลลัพธ์จะไม่ล้น สิ่งนี้สามารถคำนวณโมดูลัสของพลังงานไปสู่พลังงานที่ใหญ่กว่าได้ แต่ความซับซ้อนของวิธีนี้ยังคงเป็น o (n) และไม่เร็ว
ในการคำนวณโมดูลัสของพลังงานได้เร็วขึ้นเราจำเป็นต้องพึ่งพาสูตรต่อไปนี้:
ab mod c = (a2) b/2 mod c, b เป็นหมายเลขที่สม่ำเสมอ
ab mod c = ((a2) b/2 ・ a) mod c, b เป็นเลขคี่
สูตรนี้ง่ายมาก หลักการคือการแทนที่ B อย่างต่อเนื่องด้วยสแควร์ของ A และแทนที่ B ด้วยครึ่งเดิม เพราะเรารู้ผ่านสูตรแรกว่าโมดูลของตัวเลขมีพลังเท่ากัน (ประโยคนี้ค่อนข้างสับสนซึ่งหมายถึงสูตรหนึ่ง) จากนั้นผลของการใช้ผลลัพธ์ของ A*A%C แทน A จะเหมือนกัน
ดังนั้นตามสูตรข้างต้นเราได้รับวิธีการคำนวณพลังงานที่รวดเร็วด้วยความซับซ้อน o (logn):
นำเข้า java.util.scanner; คลาสสาธารณะหลัก {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สแกนเนอร์ใน = สแกนเนอร์ใหม่ (System.in); int a = in.nextint (), b = in.nextint (), c = in.nextint (); int res = 1; a %= c; สำหรับ (; b! = 0; b /= 2) {ถ้า (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } system.out.println (res); -อัลกอริทึมนี้เป็นแบบนี้ ขั้นตอนแรกคือการลด%= c เพื่อป้องกันไม่ให้จำนวนล้นเมื่อดำเนินการ A*A เป็นครั้งแรก ในการวนรอบสำหรับถ้า b เป็นตัวเลขคี่ให้ res = res*a จากนั้นคูณให้เป็นผลลัพธ์ก่อนแล้วประมวลผล เพื่อป้องกันไม่ให้หมายเลขล้นผลลัพธ์ mod c ของ res*a จะทำงานโดยตรง ในสิ่งนี้สำหรับลูปไม่ช้าก็เร็ว B จะเท่ากับ 1 ป้อนสาขา IF และในที่สุดก็คำนวณค่าของ RES และ MOD C ออกจากการวนรอบและผลลัพธ์สุดท้าย
สรุป
ข้างต้นเป็นคำอธิบายโดยละเอียดทั้งหมดของบทความนี้เกี่ยวกับการใช้อัลกอริทึมโมดูลัสพลังงานอย่างรวดเร็วของภาษา Java ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!