ทำการคำนวณที่มีขนาดใหญ่มาก

ฉันต้องการคำนวณค่า

X =n!/2^r

where n<10^6 and r<10^6
and it's guarantee that value of X is between O to 10

วิธีคำนวณ X เนื่องจากฉันไม่สามารถหารค่าแฟกทอเรียลและค่ากำลังอย่างง่ายได้เนื่องจากมันล้นจำนวนเต็มยาว

แนวทางของฉัน
ทำด้วยความช่วยเหลือของโมดูลัส สมมุติว่าเป็นจำนวนเฉพาะที่มากกว่า 10 สมมุติว่า 101 

 X=  [(Factorial N%101)*inverse Modulo of(2^r)]%101;

โปรดทราบว่าโมดูโลผกผันสามารถคำนวณได้ง่ายและสามารถคำนวณ 2^r%101 ได้เช่นกัน

ปัญหา:
ไม่ได้รับประกันว่า X จะเป็นจำนวนเต็มเสมอ และสามารถ ลอยตัว ได้เช่นกัน วิธีการของฉันทำงานได้ดีเมื่อ X เป็นจำนวนเต็ม ? วิธีรับมือเมื่อ X เป็นตัวเลขทศนิยม


module algorithm numbers
person Narendra Modi    schedule 07.02.2017    source แหล่งที่มา
comment
แล้วบางอย่างเช่น 3/2.0*4/2.0*5/2.0*... ล่ะ?   -  person barak manos    schedule 07.02.2017

คำตอบ (4)


arrow_upward
1
arrow_downward

หากผลลัพธ์โดยประมาณใช้ได้ และคุณมีสิทธิ์เข้าถึงคลังคณิตศาสตร์ที่มีเลขชี้กำลังฐาน 2 (exp2 ใน C) แกมมาบันทึกธรรมชาติ (lgamma ใน C) และบันทึกธรรมชาติ (log ใน C) คุณก็สามารถทำได้

exp2(lgamma(n+1)/log(2) - r).
person David Eisenstat    schedule 07.02.2017

arrow_upward
0
arrow_downward

ค้นหาเลขยกกำลังที่ 2 ปรากฏใน n! นี่คือ:

P = n / 2 + n / 2^2 + n / 2^3 + ...

ใช้การหารจำนวนเต็มจนกว่าจะได้ผลลัพธ์ 0

ถ้า P >= r แสดงว่าคุณได้ผลลัพธ์เป็นจำนวนเต็ม คุณสามารถค้นหาผลลัพธ์นี้ได้โดยการคำนวณแฟคทอเรียล โดยที่คุณไม่ต้องสนใจ r กำลังของ 2 สิ่งที่ต้องการ:

factorial = 1
for i = 2 to n:

    factor = i
    while factor % 2 == 0 and r != 0:
        factor /= 2
        r -= 1

    factorial *= factor

ถ้า P < r ให้ตั้งค่า r = P ให้ใช้อัลกอริธึมเดียวกันและหารผลลัพธ์ด้วย 2^(initial_r - P) ในตอนท้าย

person IVlad    schedule 07.02.2017

arrow_upward
0
arrow_downward

ยกเว้นในบางกรณี (ที่มี n และ r เล็ก) X จะไม่เป็นจำนวนเต็ม เพราะถ้า n >= 11 แล้ว 11 จะหาร n! แต่ไม่ได้หารกำลังสอง ดังนั้นถ้า X เป็นอินทิกรัลก็ต้องมีค่าอย่างน้อย 11

วิธีหนึ่งคือ: เริ่มต้น X เป็นหนึ่ง; จากนั้นวนซ้ำ: ถ้า X > 10 หารด้วย 2 จนไม่หาร; ถ้า X ‹ 10 คูณด้วยตัวประกอบถัดไปจนไม่คูณ; จนกระทั่งตัวประกอบและกำลังของ 2 หมด

person dmuir    schedule 07.02.2017
comment
@Paul คุณสามารถลด X เหลือ 10 หรือต่ำกว่าโดยหารด้วย 2 วินาทีอย่างที่ฉันบอก เนื่องจากคำตอบไม่มากกว่า 10 จึงต้องมี 2 วินาทีเพียงพอ - person dmuir; 07.02.2017
comment
คำตอบคือค่า จุดลอยตัว ที่ต่ำกว่า 10 และดังที่ได้อธิบายไปแล้วในความคิดเห็นของฉัน ค่าสูงสุด n โดยที่ X จะลดเหลือค่าที่ต่ำกว่า 10 ในทุกขั้นตอนได้คือ 4 ลองดูสิ แนวทางของคุณด้วย 5! - person Paul; 07.02.2017

arrow_upward
0
arrow_downward

แนวทางที่จะปรับแต่งเพื่อความแม่นยำ/ประสิทธิภาพจะเป็นดังนี้:

เก็บแฟกทอเรียลเป็นจำนวนเต็มโดยมีจำนวนบิตคงที่ เราสามารถปล่อยตัวเลขสองสามหลักสุดท้ายได้หากตัวเลขมากเกินไป เนื่องจากจะไม่ส่งผลกระทบต่อผลลัพธ์โดยรวมมากนัก ด้วยการปรับขนาดจำนวนเต็มนี้ให้ใหญ่ขึ้น/เล็กลง อัลกอริธึมจะสามารถปรับแต่งประสิทธิภาพหรือความแม่นยำได้

เมื่อใดก็ตามที่จำนวนเต็มล้นเนื่องจากการคูณ ให้เลื่อนไปทางขวาสักสองสามตำแหน่งแล้วลบค่านั้นออกจาก r ท้ายที่สุดแล้ว ควรเหลือจำนวนเล็กน้อยไว้เป็น r และจำนวนเต็ม v โดยมีบิตที่สำคัญที่สุดของแฟกทอเรียล ขณะนี้ v สามารถตีความได้ว่าเป็นตัวเลขจุดคงที่ซึ่งมีเศษส่วนเป็น r หลัก

ขึ้นอยู่กับความแม่นยำที่ต้องการ วิธีการนี้อาจใช้ได้กับ long แม้ว่าฉันจะไม่มีเวลาทดสอบวิธีการนี้เลย นอกเหนือจากการทดลองกับเครื่องคิดเลขเล็กน้อย

person Paul    schedule 07.02.2017